P vs. BPP

Importance: High ✭✭✭
Author(s): Folklore
Recomm. for undergrads: no
Posted by: Charles R Great...
on: June 14th, 2013

\begin{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? \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

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 $P\subseteq BPP\subseteq NEXP.$

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.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

Andrea E. F. Clement, Jose D. P. Rolim, and Luca Trevisan, \href[Recent Advances Towards Proving P = BPP]{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=} (1998).

Oded Goldreich, \href[In a World of BPP=P]{http://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf}, Studies in complexity and cryptography, Lecture Notes in Comput. Sci., 6650, Springer, Heidelberg, 2011, pp. 191-–232. See also \href[the presentation]{http://www.wisdom.weizmann.ac.il/~oded/T/bpp.ppt}.

Russell Impagliazzo and Avi Wigderson, \href[P=BPP unless E has sub-exponential circuits: derandomizing the XOR Lemma]{http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf}, following STOC '97.

Ryan Williams, \href[Towards NEXP versus BPP?]{http://www.stanford.edu/~rrwill/nexp-v-bpp.pdf}, Computer Science---Theory and Applications, Lecture Notes in Computer Science Volume 7913 (2013), pp. 174--182.

* indicates original appearance(s) of problem.