Editing BPP (complexity) (section)

== Derandomization ==
The existence of certain strong [[pseudorandom number generators]] is [[conjecture]]d by most experts of the field. Such generators could replace true random numbers in any polynomial-time randomized algorithm, producing indistinguishable results. The conjecture that these generators exist implies that randomness does not give additional computational power to polynomial time computation, that is, '''P''' = '''RP''' = '''BPP'''. More strongly, the assumption that '''P''' = '''BPP''' is in some sense equivalent to the existence of strong pseudorandom number generators.<ref>{{cite book
 | last = Goldreich | first = Oded
 | editor-last = Goldreich | editor-first = Oded
 | contribution = In a World of P=BPP
 | contribution-url = https://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf
 | doi = 10.1007/978-3-642-22670-0_20
 | pages = 191–232
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman
 | volume = 6650
 | year = 2011}}</ref>

[[László Babai]], [[Lance Fortnow]], [[Noam Nisan]], and [[Avi Wigderson]] showed that unless '''[[EXPTIME]]''' collapses to '''[[MA (complexity)|MA]]''', '''BPP''' is contained in<ref name="Babai">{{cite journal | last1 = Babai | first1 = László | last2 = Fortnow | first2 = Lance | last3 = Nisan | first3 = Noam | last4 = Wigderson | first4 = Avi | year = 1993 | title = '''BPP''' has subexponential time simulations unless '''EXPTIME''' has publishable proofs | journal = Computational Complexity | volume = 3 | issue = 4 | pages = 307–318 | doi=10.1007/bf01275486| s2cid = 14802332 }}</ref> 
:<math>\textsf{i.o.-SUBEXP} = \bigcap\nolimits_{\varepsilon>0} \textsf{i.o.-DTIME} \left (2^{n^\varepsilon} \right).</math> 
The class '''i.o.-SUBEXP''', which stands for infinitely often '''SUBEXP''', contains problems which have [[sub-exponential time]] algorithms for infinitely many input sizes. They also showed that '''P''' = '''BPP''' if the exponential-time hierarchy, which is defined in terms of the [[polynomial hierarchy]] and '''E''' as '''E<sup>PH</sup>''', collapses to '''E'''; however, note that the exponential-time hierarchy is usually conjectured ''not'' to collapse.

[[Russell Impagliazzo]] and [[Avi Wigderson]] showed that if any problem in '''[[E (complexity)|E]]''', where 
:<math>\mathsf{E} = \mathsf{DTIME} \left( 2^{O(n)} \right),</math> 
has circuit complexity 2<sup>Ω(''n'')</sup> then '''P''' = '''BPP'''.<ref>Russell Impagliazzo and Avi Wigderson (1997). "'''P'''&nbsp;=&nbsp;'''BPP''' if E requires exponential circuits: Derandomizing the XOR Lemma". ''Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing'', pp. 220–229. {{doi|10.1145/258533.258590}}</ref>