Editing BPP (complexity) (section)

=== 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.