Editing BPP (complexity) (section)

== Complexity-theoretic properties ==
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|BPP in relation to other probabilistic complexity classes ([[ZPP (complexity)|ZPP]], [[RP (complexity)|RP]], co-RP, [[BQP]], [[PP (complexity)|PP]]), which generalise [[P (complexity)|P]] within [[PSPACE]]. It is unknown if any of these containments are strict.]]
[[File:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], BPP, [[P/poly]], [[PH (complexity)|PH]], and [[PSPACE]]]]

It is known that '''BPP''' is closed under [[Complement (complexity)|complement]]; that is, '''BPP''' = '''co-BPP'''. '''BPP''' is [[low (complexity)|low]] for itself, meaning that a '''BPP''' machine with the power to solve '''BPP''' problems instantly (a '''BPP''' [[oracle machine]]) is not any more powerful than the machine without this extra power. In symbols, '''BPP'''<sup>'''BPP'''</sup> = '''BPP'''.

The relationship between '''BPP''' and '''[[NP (complexity)|NP]]''' is unknown: it is not known whether '''BPP''' is a [[subset]] of '''[[NP (complexity)|NP]]''', '''NP''' is a subset of '''BPP''' or neither. If '''NP''' is contained in '''BPP''', which is considered unlikely since it would imply practical solutions for [[NP-complete]] problems, then '''NP''' = '''RP''' and '''[[PH (complexity)|PH]]''' ⊆ '''BPP'''.<ref>Lance Fortnow, [http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html Pulling Out The Quantumness],  December 20, 2005</ref>

It is known that '''[[RP (complexity)|RP]]''' is a subset of '''BPP''', and '''BPP''' is a subset of '''[[PP (complexity)|PP]]'''.  It is not known whether those two are strict subsets, since we don't even know if '''P''' is a strict subset of '''PSPACE'''. '''BPP''' is contained in the second level of the [[polynomial hierarchy]] and therefore it is contained in '''PH'''. More precisely, the [[Sipser–Lautemann theorem]] states that <math>\mathsf{BPP} \subseteq \Sigma_2 \cap \Pi_2 </math>. As a result, '''P''' = '''NP''' leads to '''P''' = '''BPP''' since '''PH''' collapses to '''P''' in this case. Thus either '''P''' = '''BPP''' or '''P''' ≠ '''NP''' or both.

[[Adleman's theorem]] states that membership in any language in '''BPP''' can be determined by a family of polynomial-size [[Boolean circuit]]s, which means '''BPP''' is contained in '''[[P/poly]]'''.<ref>{{cite conference | author = Adleman, L. M. | author-link = Leonard Adleman | title = Two theorems on random polynomial time | book-title = Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing | year = 1978 | pages = 75–83}}</ref> Indeed, as a consequence of the proof of this fact, every '''BPP''' algorithm operating on inputs of bounded length can be derandomized into a deterministic algorithm using a fixed string of random bits. Finding this string may be expensive, however. Some weak separation results for Monte Carlo time classes were proven by {{harvtxt|Karpinski|Verbeek|1987a}}, see also {{harvtxt|Karpinski|Verbeek|1987b}}.

=== Closure properties ===
The class BPP is closed under complementation, union, intersection, and concatenation.

=== Relativization ===
Relative to oracles, we know that there exist oracles A and B, such that '''P'''<sup>A</sup> = '''BPP'''<sup>A</sup> and '''P'''<sup>B</sup> ≠ '''BPP'''<sup>B</sup>. Moreover, relative to a [[random oracle]] with probability 1,  '''P''' = '''BPP''' and '''BPP''' is strictly contained in '''NP''' and '''co-NP'''.<ref>{{Citation | last1=Bennett | first1=Charles H. | author1-link=Charles H. Bennett (computer scientist) | last2=Gill | first2=John | title=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1 | year=1981 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=10 | issue=1 | pages=96–113 | doi=10.1137/0210008}}</ref>

There is even an oracle in which {{tmath|1=\mathsf{BPP}=\mathsf{EXP}^\mathsf{NP} }} (and hence {{tmath|1=\mathsf{P<NP<BPP=EXP=NEXP} }}),<ref>{{Citation | last=Heller | first=Hans | title=On relativized exponential and probabilistic complexity classes | year=1986 | journal=Information and Control | volume=71 | issue=3 | pages=231–243 | doi=10.1016/S0019-9958(86)80012-2| doi-access=free }}</ref> which can be iteratively constructed as follows.  For a fixed [[E (complexity)|E]]<sup>NP</sup> (relativized) complete problem, the oracle will give correct answers with high probability if queried with the problem instance followed by a random string of length ''kn'' (''n'' is instance length; ''k'' is an appropriate small constant).  Start with ''n''=1.  For every instance of the problem of length ''n'' fix oracle answers (see lemma below) to fix the instance output.  Next, provide the instance outputs for queries consisting of the instance followed by ''kn''-length string, and then treat output for queries of length ≤(''k''+1)''n'' as fixed, and proceed with instances of length ''n''+1.

{{Math theorem |name=Lemma|Given a problem (specifically, an oracle machine code and time constraint) in relativized {{math|{{sans-serif|E<sup>NP</sup>}}}}, for every partially constructed oracle and input of length ''n'', the output can be fixed by specifying 2<sup>''O''(''n'')</sup> oracle answers.}}
{{Math proof|The machine is simulated, and the oracle answers (that are not already fixed) are fixed step-by-step.  There is at most one oracle query per deterministic computation step.  For the relativized NP oracle, if possible fix the output to be yes by choosing a computation path and fixing the answers of the base oracle; otherwise no fixing is necessary, and either way there is at most 1 answer of the base oracle per step.  Since there are 2<sup>''O''(''n'')</sup> steps, the lemma follows.}}

The lemma ensures that (for a large enough ''k''), it is possible to do the construction while leaving enough strings for the relativized {{math|{{sans-serif|E<sup>NP</sup>}}}} answers.  Also, we can ensure that for the relativized {{math|{{sans-serif|E<sup>NP</sup>}}}}, linear time suffices, even for function problems (if given a function oracle and linear output size) and with exponentially small (with linear exponent) error probability.  Also, this construction is effective in that given an arbitrary oracle A we can arrange the oracle B to have {{math|{{sans-serif|P}}<sup>A</sup>≤{{sans-serif|P}}<sup>B</sup>}} and {{math|1={{sans-serif|EXP}}<sup>{{sans-serif|NP}}<sup>A</sup></sup>={{sans-serif|EXP}}<sup>{{sans-serif|NP}}<sup>B</sup></sup>={{sans-serif|BPP}}<sup>B</sup>}}.  Also, for a {{math|{{sans-serif|1=[[ZPP (complexity)|ZPP]]=EXP}}}} oracle (and hence {{math|{{sans-serif|1=ZPP=BPP=EXP&lt;NEXP}}}}), one would fix the answers in the relativized E computation to a special nonanswer, thus ensuring that no fake answers are given.