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.

Related posted: https://cstheory.stackexchange.com/questions/38467/on-earlier-references-for-p-bpp-and-kolmogorovs-possible-view-on-modern-break


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.