login/create account
P vs. BPP
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?
BPP has long been considered tractable. Many problems in BPP have been derandomized, showing that they are in fact in P. Is this true for all problems in BPP? All that is known at the moment is 
This problem has been shown to have deep connections to circuit complexity (see for example Impagliazzo & Wigderson). It is folklore that the existence of appropriate pseudorandom generators suffices to give P = BPP; Goldreich shows that their existence also follows from P = BPP.
Bibliography
Andrea E. F. Clement, Jose D. P. Rolim, and Luca Trevisan, Recent Advances Towards Proving P = BPP (1998).
Oded Goldreich, In a World of BPP=P, Studies in complexity and cryptography, Lecture Notes in Comput. Sci., 6650, Springer, Heidelberg, 2011, pp. 191-–232. See also the presentation.
Russell Impagliazzo and Avi Wigderson, P=BPP unless E has sub-exponential circuits: derandomizing the XOR Lemma, following STOC '97.
Ryan Williams, Towards NEXP versus BPP?, Computer Science---Theory and Applications, Lecture Notes in Computer Science Volume 7913 (2013), pp. 174--182.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University