# On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate $$P=BPP$$ in $$1986$$. They do this without getting into circuit lower bounds and from a different view which for people like me is more well grounded than basing on some other unknown and pure beliefs.

1. Is there a reference on $$P=BPP$$ possibility earlier than this that goes into considerable depth?

2. On page $$406$$ they state 'It should be clearly realized however that we have not seen a randomized algorithm which works faster than a deterministic one'.

a. Now $$FPTAS$$ for permanent came after this in $$1988$$

b. Toda's theorem came in $$1991$$.

c. Valiant-Vazirani uniqueSAT randomized reduction came as early as $$1984$$.

d. https://en.wikipedia.org/wiki/Isolation_lemma#cite_ref-3 came in mid $$1980$$s.

However these references are not in http://epubs.siam.org/doi/pdf/10.1137/1132060 and in http://www.mathnet.ru/links/e70b23dfb7d2952dfbc4c16dfcee9e4e/tvp1437.pdf). Is there a philosophical take on what Kolmogorov would have thought if he had seen these before he passed away in $$1987$$?

Note that our view of $$P=BPP$$ is framed from circuit lower bounds. Kolmogorov's view was likely different and could not have come from circuit lower bounds.