4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jul 23, 2017 at 19:52
  • $\begingroup$ '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. $\endgroup$
    – Turbo
    Commented Jul 23, 2017 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jul 23, 2017 at 21:02
  • $\begingroup$ @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. $\endgroup$
    – Turbo
    Commented Jul 23, 2017 at 21:08
  • $\begingroup$ Ok you convinced me :) BTW p 409 also gives their reasons for believing P = BPP: basically, Adleman's and Gac's theorems. $\endgroup$
    – Sasho Nikolov
    Commented Jul 24, 2017 at 2:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.