# 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'. Now FPTAS for permanent came after this in 1988 and Toda's theorem came in 1991. 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.

• Having skimmed the relevant sections of this paper, I don't buy the premise of the question. I don't see where in the paper the authors speculate that P = BPP. If you see the sentence you quote in context, it seems to just refer to the fact that it is possible that a polytime deterministic primality testing algorithm exists. – Sasho Nikolov Jul 23 '17 at 19:52
• 'It should be clearly realized however that we have not seen a randomized algorithm which works faster than a deterministic one' is a reasonable hint I think. – Turbo Jul 23 '17 at 19:54
• Again, in the context in which this sentence appears, they just seem to be emphasizing that the P vs BPP problem is open. I don't see that they suggest P=BPP as the likely solution. The next paragraph they also talk about advantages of randomized algorithms. – Sasho Nikolov Jul 23 '17 at 21:02
• @SashoNikolov page $409$ 'Although the question "Is the class BPP equal to the class P?" is still open, there are a number of theorems furnishing a partial answer in the affirmative direction.'. I think we should take $406$ statement as a general one. – Turbo Jul 23 '17 at 21:08
• Ok you convinced me :) BTW p 409 also gives their reasons for believing P = BPP: basically, Adleman's and Gac's theorems. – Sasho Nikolov Jul 24 '17 at 2:08