<p>Kolmogorov and Uspenskii in this paper '<a href="http://epubs.siam.org/doi/pdf/10.1137/1132060" rel="nofollow noreferrer">http://epubs.siam.org/doi/pdf/10.1137/1132060</a>' 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.</p>

<ol>
<li><p>Is there a reference on P=BPP possibility earlier than this that goes into considerable depth?</p></li>
<li><p>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? </p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2017-07-23T19:52:29.793Z
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
CC BY-SA 3.0
2017-07-23T19:54:36.327Z
'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
CC BY-SA 3.0
2017-07-23T21:02:58.903Z
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
CC BY-SA 3.0
2017-07-23T21:08:38.843Z
@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
CC BY-SA 3.0
2017-07-24T02:08:56.837Z
Ok you convinced me :) BTW p 409 also gives their reasons for believing P = BPP: basically, Adleman's and Gac's theorems.
Sasho Nikolov
CC BY-SA 3.0
2017-07-24T02:15:36.273Z
@SashoNikolov it is not so clear and hence the query (it looks like they have more up their sleeve).
Turbo
<reference-request><big-picture><randomness><derandomization><polynomial-hierarchy>
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Turbo
# On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

(Asked by: username_0 on 2017-06-23)

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.

**Tags:** reference-request, big-picture, randomness, derandomization, polynomial-hierarchy
> **Comments:**
> **username_1**: 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.  
> **username_0**: '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.  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: Ok you convinced me :) BTW p 409 also gives their reasons for believing P = BPP: basically, Adleman's and Gac's theorems.  
> **username_0**: @SashoNikolov it is not so clear and hence the query (it looks like they have more up their sleeve).  

---

## 0 answers

