https://complexityzoo.net/api.php?action=feedcontributions&user=Jh&feedformat=atomComplexity Zoo - User contributions [en]2024-03-29T00:03:46ZUser contributionsMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:B&diff=6293Complexity Zoo:B2014-04-04T17:22:15Z<p>Jh: /* BPL: Bounded-Error Probabilistic L */</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|B}}<br />
<br />
<br />
===== <span id="betap" style="color:red">&#946;P</span>: Limited-Nondeterminism [[Complexity Zoo:N#np|NP]] =====<br />
&#946;<sub>k</sub>P is the class of decision problems solvable by a polynomial-time Turing machine that makes O(log<sup>k</sup>n) nondeterministic transitions, with the same acceptance mechanism as [[Complexity Zoo:N#np|NP]]. Equivalently, the machine receives a purported proof of size O(log<sup>k</sup>n) that the answer is 'yes.'<br />
<br />
Then &#946;P is the union of &#946;<sub>k</sub>P over all constant k.<br />
<br />
Defined in [[zooref#kf84|[KF84]]]. See also the survey [[zooref#glm96|[GLM96]]].<br />
<br />
There exist oracles relative to which basically any consistent inclusion structure among the &#946;<sub>k</sub>P's can be realized [[zooref#bg98|[BG98]]].<br />
<br />
&#946;<sub>2</sub>P contains [[Complexity Zoo:L#lognp|LOGNP]] and [[Complexity Zoo:L#logsnp|LOGSNP]].<br />
<br />
----<br />
===== <span id="bh" style="color:red">BH</span>: Boolean Hierarchy Over [[Complexity Zoo:N#np|NP]] =====<br />
The smallest class that contains [[Complexity Zoo:N#np|NP]] and is closed under union, intersection, and complement.<br />
<br />
The levels are defined as follows:<br />
<ul><br />
<li>BH<sub>1</sub> = [[Complexity Zoo:N#np|NP]].</li><br />
<li>BH<sub>2i</sub> is the class of languages that are the intersection of a BH<sub>2i-1</sub> language with a [[Complexity Zoo:C#conp|coNP]] language.</li><br />
<li>BH<sub>2i+1</sub> is the class of languages that are the union of a BH<sub>2i</sub> language with an [[Complexity Zoo:N#np|NP]] language.</li><br />
</ul><br />
Then BH is the union over all i of BH<sub>i</sub>.<br />
<br />
Defined in [[zooref#ww85|[WW85]]].<br />
<br />
For more detail see [[zooref#cgh88|[CGH+88]]].<br />
<br />
Contained in [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] and indeed in [[Complexity Zoo:P#pnplog|P<sup>NP[log]</sup>]].<br />
<br />
If BH collapses at any level, then [[Complexity Zoo:P#ph|PH]] collapses to &#931;<sub>3</sub>P [[zooref#kad88|[Kad88]]].<br />
<br />
''See also'': {{zcls|d|dp}}, [[Complexity Zoo:Q#qh|QH]].<br />
<br />
----<br />
<br />
===== <span id="bpdp" style="color:red">BP<sub>d</sub>(P)</span>: Polynomial Size d-Times-Only Branching Program =====<br />
Defined in [[zooref#weg88|[Weg88]]].<br />
<br />
The class of decision problems solvable by a family of polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times.<br />
<br />
BP<sub>d</sub>(P) strictly contains BP<sub>d-1</sub>(P), for every d &gt; 1 [[zooref#tha98|[Tha98]]].<br />
<br />
Contained in [[Complexity Zoo:P#pbp|PBP]].<br />
<br />
See also: [[Complexity Zoo:P#pobdd|P-OBDD]], [[Complexity Zoo:P#kpbp|k-PBP]].<br />
----<br />
<br />
===== <span id="bpe" style="color:red">BPE</span>: Bounded-Error Probabilistic [[Complexity Zoo:E#e|E]] =====<br />
Has the same relation to [[Complexity Zoo:E#e|E]] as [[#bpp|BPP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
[[Complexity Zoo:E#ee|EE]] = BPE if and only if [[Complexity Zoo:E#exp|EXP]] = [[#bpp|BPP]] [[zooref#ikw01|[IKW01]]].<br />
<br />
----<br />
===== <span id="bpee" style="color:red">BPEE</span>: Bounded-Error Probabilistic [[Complexity Zoo:E#ee|EE]] =====<br />
Has the same relation to [[Complexity Zoo:E#ee|EE]] as [[#bpp|BPP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
----<br />
===== <span id="bphspace" style="color:red">BP<sub>H</sub>SPACE(f(n))</span>: Bounded-Error Halting Probabilistic f(n)-Space =====<br />
The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts on every input <i>and</i> every random tape setting.<br />
<br />
Contains [[Complexity Zoo:R#rhspace|R<sub>H</sub>SPACE]](f(n)).<br />
<br />
Is contained in [[Complexity Zoo:D#dspace|DSPACE]](f(n)<sup>3/2</sup>) [[zooref#sz95|[SZ95]]].<br />
<br />
----<br />
===== <span id="bpl" style="color:red">BPL</span>: Bounded-Error Probabilistic [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[#bpp|BPP]] does to [[Complexity Zoo:P#p|P]]. The Turing machine has to halt for every input and every randomness.<br />
<br />
Contained in [[Complexity Zoo:S#sc|SC]] [[zooref#nis92|[Nis92]]] and in [[Complexity Zoo:P#pl|PL]].<br />
<br />
----<br />
<br />
===== <span id="bpnp" style="color:red">BP&#149;NP</span>: Probabilistic [[Complexity Zoo:N#np|NP]] =====<br />
Equals [[Complexity Zoo:A#am|AM]].<br />
<br />
----<br />
===== <span id="bpp" style="color:red">BPP</span>: Bounded-Error Probabilistic Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes' then at least 2/3 of the computation paths accept.</li><br />
<li>If the answer is 'no' then at most 1/3 of the computation paths accept.</li><br />
</ol><br />
(Here all computation paths have the same length.)<br />
<br />
Often identified as the class of feasible problems for a computer with access to a genuine random-number source.<br />
<br />
Defined in [[zooref#gil77|[Gil77]]].<br />
<br />
Contained in [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] &#8745; [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]] [[zooref#lau83|[Lau83]]], and indeed in [[Complexity Zoo:Z#zpp|ZPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup> [[zooref#gz97|[GZ97]]].<br />
<br />
If BPP contains [[Complexity Zoo:N#np|NP]], then [[Complexity Zoo:R#rp|RP]] = [[Complexity Zoo:N#np|NP]] [[zooref#ko82|[Ko82,]][[zooref#gil77|Gil77]]] and [[Complexity Zoo:P#ph|PH]] is contained in BPP [[zooref#zac88|[Zac88]]].<br />
<br />
If any problem in [[Complexity Zoo:E#e|E]] requires circuits of size 2<sup>&#937;(n)</sup>, then BPP = [[Complexity Zoo:P#p|P]] [[zooref#iw97|[IW97]]] (in other words, BPP can be derandomized).<br />
<br />
Indeed, <i>any</i> proof that BPP = [[Complexity Zoo:P#p|P]] requires showing either that [[Complexity Zoo:N#nexp|NEXP]] is not in [[Complexity Zoo:P#ppoly|P/poly]], or else that [[Complexity Zoo:Symbols#sharpp|#P]] requires superpolynomial-size arithmetic circuits [[zooref#ki02|[KI02]]].<br />
<br />
BPP is not known to contain complete problems. [[zooref#sip82|[Sip82]]], [[zooref#hh86|[HH86]]] give oracles relative to which BPP has no complete problems.<br />
<br />
There exist oracles relative to which [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:R#rp|RP]] but still [[Complexity Zoo:P#p|P]] is not equal to BPP [[zooref#bf99|[BF99]]].<br />
<br />
In contrast to the case of [[Complexity Zoo:P#p|P]], it is unknown whether BPP collapses to [[#bptime|BPTIME]](n<sup>c</sup>) for some fixed constant c. However, [[zooref#bar02|[Bar02]]] and [[zooref#fs04|[FS04]]] have shown hierarchy theorems for BPP with a small amount of advice.<br />
<br />
A [[Zoo Glossary#zeroone-law|zero-one law]] exists stating that BPP has [[Zoo Glossary#p-measure|p-measure]] zero unless BPP = {{zcls|e|exp}} {{zcite|Mel00}}.<br />
<br />
Equals [[Complexity Zoo:A#almostp|Almost-P]].<br />
<br />
See also: [[#bpppath|BPP<sub>path</sub>]].<br />
<br />
----<br />
<br />
===== <span id="bppcc" style="color:red">BPP<sup>cc</sup></span>: Communication Complexity [[#bpp|BPP]] =====<br />
The analogue of [[Complexity Zoo:P#pcc|P<sup>cc</sup>]] for bounded-error probabilistic communication complexity.<br />
<br />
Does not equal [[Complexity Zoo:P#pcc|P<sup>cc</sup>]], and is not contained in [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]], because of the EQUALITY problem.<br />
<br />
Defined in [[zooref#bfs86|[BFS86]]].<br />
<br />
----<br />
<br />
===== <span id="bppkcc" style="color:red">BPP<sub><math>k</math></sub><sup>cc</sup></span>: [[#bppcc|BPP<sup>cc</sup>]] in NOF model, <math>k</math> players =====<br />
<br />
Has the same relation to [[#bppcc|BPP<sup>cc</sup>]] and [[#bpp|BPP]] as {{zcls|p|pkcc|P<sub><math>k</math></sub><sup>cc</sup>}} does to {{zcls|p|pcc|P<sup>cc</sup>}} and {{zcls|p|p}}.<br />
<br />
{{zcls|n|npkcc|NP<sub><math>k</math></sub><sup>cc</sup>}} is not contained in {{zcls|b|bppkcc|BPP<sub><math>k</math></sub><sup>cc</sup>}} for <math>k\le(1-\delta)\cdot\log n</math> players, for any constant <math>\delta>0</math> {{zcite|DP08}}.<br />
----<br />
<br />
===== <span id="bppkt" style="color:red">BPP<sup>KT</sup></span>: [[#bpp|BPP]] With Time-Bounded Kolmogorov Complexity Oracle =====<br />
[[#bpp|BPP]] with an oracle that, given a string x, returns the minimum over all programs P that output x<sub>i</sub> on input i, of the length of P plus the maximum time taken by P on any input.<br />
<br />
A similar class was defined in [[zooref#abk02|[ABK+02]]], where it was also shown that in BPP<sup>KT</sup> one can [[Complexity_Garden#integer_factorization|factor]], compute [[Complexity_Garden#discrete_logarithm|discrete logarithms]], and more generally invert any one-way function on a non-negligible fraction of inputs.<br />
<br />
See also: [[Complexity Zoo:P#pk|P<sup>K</sup>]].<br />
<br />
----<br />
<br />
===== <span id="bpplog" style="color:red">BPP/log</span>: [[#bpp|BPP]] With Logarithmic Karp-Lipton Advice =====<br />
The class of problems solvable by a semantic [[#bpp|BPP]] machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, the machine must provide some answer with probability at least 2/3. See the discussion for [[#bqppoly|BQP/poly]].<br />
<br />
Contained in [[#bppmlog|BPP/mlog]].<br />
<br />
----<br />
===== <span id="bppmlog" style="color:red">BPP/mlog</span>: [[#bpp|BPP]] With Logarithmic Deterministic Merlin-Like Advice =====<br />
The class of problems solvable by a syntactic [[#bpp|BPP]] machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, it need not be.<br />
<br />
Contained in [[#bpprlog|BPP/rlog]].<br />
<br />
----<br />
===== <span id="bppsslog" style="color:red">BPP//log</span>: [[#bpp|BPP]] With Logarithmic Randomness-Dependent Advice =====<br />
The class of problems solvable by a [[#bpp|BPP]] machine that is given O(log n) advice bits, which can depend on both the machine's random coin flips and the input length n, but not on the input itself.<br />
<br />
Defined in [[zooref#tv02|[TV02]]], where it was also shown that if [[Complexity Zoo:E#exp|EXP]] is in BPP//log then<br />
[[Complexity Zoo:E#exp|EXP]] = [[#bpp|BPP]], and if [[Complexity Zoo:P#pspace|PSPACE]] is in BPP//log then [[Complexity Zoo:P#pspace|PSPACE]] = [[#bpp|BPP]].<br />
<br />
----<br />
===== <span id="bpprlog" style="color:red">BPP/rlog</span>: [[#bpp|BPP]] With Logarithmic Deterministic Merlin-Like Advice =====<br />
The class of problems solvable by a syntactic [[#bpp|BPP]] machine with O(log n) random advice bits whose probability distribution depends only on the input length n. For each n, there exists good advice such that the output is correct with probability at least 2/3.<br />
<br />
Contains [[#bppmlog|BPP/mlog]]. The inclusion is strict, because BPP/rlog contains any finitely sparse language by fingerprinting; see the discussion for [[Complexity Zoo:A#all|ALL]].<br />
<br />
Contained in [[#bppsslog|BPP//log]].<br />
<br />
----<br />
===== <span id="bppobdd" style="color:red">BPP-OBDD</span>: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram =====<br />
Same as [[Complexity Zoo:P#pobdd|P-OBDD]], except that probabilistic transitions are allowed and the OBDD need only accept with probability at least 2/3.<br />
<br />
Does not contain the integer multiplication problem [[zooref#ak96|[AK96]]].<br />
<br />
Strictly contained in [[#bqpobdd|BQP-OBDD]] [[zooref#nhk00|[NHK00]]].<br />
<br />
----<br />
===== <span id="bpppath" style="color:red">BPP<sub>path</sub></span>: Threshold [[#bpp|BPP]] =====<br />
Same as [[#bpp|BPP]], except that now the computation paths need not all have the same length.<br />
<br />
Defined in [[zooref#hht97|[HHT97]]], where the following was also shown:<br />
<ul><br />
<li>BPP<sub>path</sub> contains [[Complexity Zoo:M#ma|MA]] and [[Complexity Zoo:P#pnplog|P<sup>NP[log]</sup>]], and is contained in [[Complexity Zoo:P#pp|PP]] and [[#bpp|BPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup>.</li><br />
<li>BPP<sub>path</sub> is closed under complementation, intersection, and union.</li><br />
<li>If BPP<sub>path</sub> = BPP<sub>path</sub><sup>BPP<sub>path</sub></sup>, then [[Complexity Zoo:P#ph|PH]] collapses to BPP<sub>path</sub>.</li><br />
<li>If BPP<sub>path</sub> contains [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]], then [[Complexity Zoo:P#ph|PH]] collapses to [[#bpp|BPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup>.</li><br />
</ul><br />
There exists an oracle relative to which BPP<sub>path</sub> is not contained in [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] [[zooref#bgm02|[BGM02]]].<br />
<br />
An alternate characterization of BPP<sub>path</sub> uses the idea of post-selection. That is, BPP<sub>path</sub> is the class of languages <math>L</math> for which there exists a pair of polynomial-time Turing machines <math>A</math> and <math>B</math> such that the following conditions hold for all <math>x</math>:<br />
* If <math>x\in L</math>, <math>\Pr_{r\in\{0,1\}^{\mathrm{poly}(\left\vert x\right\vert)}}\left[A(x,r)\mid B(x,r)\right]\ge \frac23</math>.<br />
* If <math>x\notin L</math>, <math>\Pr_{r\in\{0,1\}^{\mathrm{poly}(\left\vert x\right\vert)}}\left[A(x,r)\mid B(x,r)\right]< \frac13</math>.<br />
* <math>\Pr_{r\in\{0,1\}^{\mathrm{poly}(n)}}\left[B(x,r)\right]>0</math>.<br />
We say that <math>B</math> is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP &sube; BPP<sub>path</sub> nearly trivial.<br />
<br />
''See Also'': {{zcls|p|postbqp|PostBQP}} (quantum analogue).<br />
<br />
----<br />
<br />
===== <span id="bpqp" style="color:red">BPQP</span>: Bounded-Error Probabilistic [[Complexity Zoo:Q#qp|QP]] =====<br />
Equals [[#bptime|BPTIME]](2<sup>O((log n)^k)</sup>); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.<br />
<br />
Defined in [[zooref#cns99|[CNS99]]], where the following was also shown:<br />
<ul><br />
If either (1) [[Complexity Zoo:Symbols#sharpp|#P]] does not have a subexponential-time bounded-error algorithm, or (2) [[Complexity Zoo:E#exp|EXP]] does not have subexponential-size circuits, then the BPQP hierarchy is strict -- that is, for all a &lt; b at least 1, [[#bptime|BPTIME]](2<sup>(log n)^a</sup>) is strictly contained in [[#bptime|BPTIME]](2<sup>(log n)^b</sup>).<br />
</ul><br />
<br />
----<br />
===== <span id="bpspace" style="color:red">BPSPACE(f(n))</span>: Bounded-Error Probabilistic f(n)-Space =====<br />
The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts with probability 1 on every input.<br />
<br />
Contains [[Complexity Zoo:R#rspace|RSPACE(f(n))]] and [[#bphspace|BP<sub>H</sub>SPACE(f(n))]].<br />
<br />
----<br />
===== <span id="bptime" style="color:red">BPTIME(f(n))</span>: Bounded-Error Probabilistic f(n)-Time =====<br />
Same as [[#bpp|BPP]], but with f(n)-time (for some constructible function f) rather than polynomial-time machines.<br />
<br />
Defined in [[zooref#gil77|[Gil77]]].<br />
<br />
BPTIME(n<sup>log n</sup>) does not equal BPTIME(2<sup>n^&epsilon;</sup>) for any &epsilon;>0 [[zooref#kv88|[KV88]]]. Proving a stronger time hierarchy theorem for BPTIME is a longstanding open problem; see [[zooref#bh97|[BH97]]] for details.<br />
<br />
[[zooref#bar02|[Bar02]]] has shown the following:<br />
<ul><br />
<li>If we allow a small number of advice bits (say log n), then there is a strict hierarchy: for every d at least 1, BPTIME(n<sup>d</sup>)/(log n) does not equal BPTIME(n<sup>d+1</sup>)/(log n).</li><br />
<li>In the uniform setting, if [[#bpp|BPP]] has complete problems then BPTIME(n<sup>d</sup>) does not equal BPTIME(n<sup>d+1</sup>).</li><br />
<li>BPTIME(n) does not equal [[Complexity Zoo:N#np|NP]].</li><br />
</ul><br />
Subsequently, [[zooref#fs04|[FS04]]] managed to reduce the number of advice bits to only 1: BPTIME(n<sup>d</sup>)/1 does not equal BPTIME(n<sup>d+1</sup>)/1. They also proved a hierarchy theorem for [[#heurbptime|HeurBPTIME]].<br />
<br />
For another bounded-error hierarchy result, see [[#bpqp|BPQP]].<br />
<br />
----<br />
===== <span id="bqnc" style="color:red">BQNC</span>: Alternate Name for [[Complexity Zoo:Q#qnc|QNC]] =====<br />
<br />
----<br />
===== <span id="bqnp" style="color:red">BQNP</span>: Alternate Name for [[Complexity Zoo:Q#qma|QMA]] =====<br />
<br />
----<br />
===== <span id="bqp" style="color:red">BQP</span>: Bounded-Error Quantum Polynomial-Time =====<br />
The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.<br />
<br />
One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [[zooref#yao93|[Yao93]]]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [[zooref#adh97|[ADH97]]]).<br />
<br />
BQP is often identified as the class of feasible problems for quantum computers.<br />
<br />
Contains the [[Complexity_Garden#integer_factorization|factoring]] and [[Complexity_Garden#discrete_logarithm|discrete logarithm]] problems [[zooref#sho97|[Sho97]]], the hidden Legendre symbol problem [[zooref#dhi02|[DHI02]]], the Pell's equation and principal ideal problems [[zooref#hal02|[Hal02]]], and some other problems not thought to be in [[#bpp|BPP]].<br />
<br />
Defined in [[zooref#bv97|[BV97]]], where it is also shown that BQP contains [[#bpp|BPP]] and is contained in [[Complexity Zoo:P#p|P]] with a [[Complexity Zoo:Symbols#sharpp|#P]] oracle.<br />
<br />
BQP<sup>BQP</sup> = BQP [[zooref#bv97|[BV97]]].<br />
<br />
[[zooref#adh97|[ADH97]]] showed that BQP is contained in [[Complexity Zoo:P#pp|PP]], and [[zooref#fr98|[FR98]]] showed that BQP is contained in [[Complexity Zoo:A#awpp|AWPP]].<br />
<br />
There exist oracles relative to which:<br />
<ul><br />
<li>BQP does not equal to [[#bpp|BPP]] [[zooref#bv97|[BV97]]] (and by similar arguments, is not in [[Complexity Zoo:P#ppoly|P/poly]]).</li><br />
<li>BQP is not contained in [[Complexity Zoo:M#ma|MA]] [[zooref#wat00|[Wat00]]].</li><br />
<li>BQP is not contained in [[Complexity Zoo:M#modkp|Mod<sub>p</sub>P]] for prime p [[zooref#gv02|[GV02]]].</li><br />
<li>[[Complexity Zoo:N#np|NP]], and indeed [[Complexity Zoo:N#npiconp|NP &#8745; coNP]], are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively [[zooref#bbb97|[BBB+97]]].</li><br />
<li>[[Complexity Zoo:S#szk|SZK]] is not contained in BQP [[zooref#aar02|[Aar02]]].</li><br />
<li>BQP is not contained in [[Complexity Zoo:S#szk|SZK]] (follows easily using the quantum walk problem in [[zooref#ccd03|[CCD+03]]]).</li><br />
<li>[[Complexity Zoo:P#ppad|PPAD]] is not contained in BQP [[zooref#li11|[Li11]]].</li><br />
</ul><br />
<br />
----<br />
<br />
===== <span id="bqplog" style="color:red">BQP/log</span>: [[#bqp|BQP]] With Logarithmic-Size Karp-Lipton Advice =====<br />
Same as [[#bqppoly|BQP/poly]] except that the advice is O(log n) bits instead of a polynomial number.<br />
<br />
Contained in [[#bqpmlog|BQP/mlog]].<br />
<br />
----<br />
===== <span id="bqppoly" style="color:red">BQP/poly</span>: [[#bqp|BQP]] With Polynomial-Size Karp-Lipton Advice =====<br />
Is to [[#bqpmpoly|BQP/mpoly]] as [[#existsbpp|&#8707;BPP]] is to [[Complexity Zoo:M#ma|MA]]. Namely, the [[#bqp|BQP]] machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though [[#bqpmpoly|BQP/mpoly]] is a more natural class, BQP/poly follows the standard definition of advice as a class operator [[zooref#kl82|[KL82]]].<br />
<br />
Contained in [[#bqpmpoly|BQP/mpoly]] and contains [[#bqplog|BQP/log]].<br />
<br />
----<br />
===== <span id="bqpmlog" style="color:red">BQP/mlog</span>: [[#bqp|BQP]] With Logarithmic-Size Deterministic Merlin-Like Advice =====<br />
Same as [[#bqpmpoly|BQP/mpoly]] except that the advice is O(log n) bits instead of a polynomial number.<br />
<br />
Strictly contained in [[#bqpqlog|BQP/qlog]] [[zooref#ny03|[NY03]]].<br />
<br />
----<br />
===== <span id="bqpmpoly" style="color:red">BQP/mpoly</span>: [[#bqp|BQP]] With Polynomial-Size Deterministic Merlin-Like Advice =====<br />
The class of languages recognized by a syntactic BQP machine with deterministic polynomial advice that depends only on the input length, such that the output is correct with probability 2/3 when the advice is good.<br />
<br />
Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as [[#ppoly|P/poly]] is the class solvable by a nonuniform family of polynomial-size classical circuits.<br />
<br />
Referred to with a variety of other ad hoc names, including [[#bqppoly|BQP/poly]] on occassion.<br />
<br />
Contains [[#bqpqlog|BQP/qlog]], and is contained in [[#bqpqpoly|BQP/qpoly]].<br />
<br />
Does not contain [[Complexity Zoo:E#espace|ESPACE]] [[zooref#ny03|[NY03]]].<br />
<br />
----<br />
===== <span id="bqpqlog" style="color:red">BQP/qlog</span>: [[#bqp|BQP]] With Logarithmic-Size Quantum Advice =====<br />
Same as [[#bqpmlog|BQP/mlog]] except that the advice is quantum instead of classical.<br />
<br />
Strictly contains [[#bqpmlog|BQP/mlog]] [[zooref#ny03|[NY03]]].<br />
<br />
Contained in [[#bqpmpoly|BQP/mpoly]].<br />
<br />
----<br />
===== <span id="bqpqpoly" style="color:red">BQP/qpoly</span>: [[#bqp|BQP]] With Polynomial-Size Quantum Advice =====<br />
The class of problems solvable by a [[#bqp|BQP]] machine that receives a quantum state &psi;<sub>n</sub> as advice, which depends only on the input length n.<br />
<br />
As with [[#bqpmpoly|BQP/mpoly]], the acceptance probability does not need to be bounded away from 1/2 if the machine is given bad advice. (Thus, we are discussing the class that [[zooref#ny03|[NY03]]] call BQP/*Qpoly.) Indeed, such a condition would make ''quantum'' advice unusable, by a continuity argument.<br />
<br />
Does not contain [[Complexity Zoo:E#eespace|EESPACE]] [[zooref#ny03|[NY03]]].<br />
<br />
[[zooref#aar04b|[Aar04b]]] shows the following:<br />
<ul><br />
<li>There exists an oracle relative to which BQP/qpoly does not contain [[Complexity Zoo:N#np|NP]].</li><br />
<li>BQP/qpoly is contained in [[Complexity Zoo:P#pppoly|PP/poly]].</li><br />
</ul><br />
A ''classical'' oracle separation between BQP/qpoly and [[#bqpmpoly|BQP/mpoly]] is presently unknown, but there is a ''quantum'' oracle separation [[zooref#ak06|[AK06]]]. An unrelativized separation is too much to hope for, since it would imply that [[Complexity Zoo:P#pp|PP]] is not contained in [[Complexity Zoo:P#ppoly|P/poly]].<br />
<br />
Contains [[#bqpmpoly|BQP/mpoly]].<br />
<br />
----<br />
<br />
===== <span id="bqpobdd" style="color:red">BQP-OBDD</span>: Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram =====<br />
Same as [[Complexity Zoo:P#pobdd|P-OBDD]], except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.<br />
<br />
Strictly contains [[#bppobdd|BPP-OBDD]] [[zooref#nhk00|[NHK00]]].<br />
<br />
----<br />
===== <span id="bqpspace" style="color:red">BQPSPACE</span>: Bounded-Error Quantum [[Complexity Zoo:P#pspace|PSPACE]] =====<br />
Equals [[Complexity Zoo:P#pspace|PSPACE]] and [[Complexity Zoo:P#ppspace|PPSPACE]].<br />
<br />
----<br />
===== <span id="bqtime" style="color:red">BQTIME(f(n))</span>: Bounded-Error Quantum f(n)-Time =====<br />
Same as [[#bqp|BQP]], but with f(n)-time (for some constructible function f) rather than polynomial-time machines.<br />
<br />
Defined in [[zooref#bv97|[BV97]]].<br />
<br />
----<br />
===== <span id="bqpctc" style="color: red">BQP<sub>CTC</sub></span>: [[#bqp|BQP]] With Closed Time Curves =====<br />
Same as [[#bqp|BQP]] with access to two sets of qubits: causality-respecting qubits and CTC qubits.<br />
<br />
Defined in [[zooref#aar05c|[Aar05c]]], where it was shown that [[Complexity Zoo:P#pspace|PSPACE]] is contained in BQP<sub>CTC</sub>, which in turn is contained in [[Complexity Zoo:S#sqg|SQG]].<br />
<br />
See also [[Complexity Zoo:P#pctc|P<sub>CTC</sub>]].<br />
<br />
----<br />
<br />
===== <span id="bqpttpoly" style="color:red">BQP<sub>tt</sub>/poly</span>: [[#bqpmpoly|BQP/mpoly]] With Truth-Table Queries =====<br />
Same as [[#bqpmpoly|BQP/mpoly]], except that the machine only gets to make <i>nonadaptive</i> queries to whatever oracle it might have.<br />
<br />
Defined in [[zooref#ny03b|[NY03b]]], where it was also shown that [[Complexity Zoo:P#p|P]] is not contained in BQP<sub>tt</sub>/poly relative to an oracle.<br />
<br />
----<br />
===== <span id="bwbp" style="color:red">k-BWBP</span>: Bounded-Width Branching Program =====<br />
Alternate name for k-[[Complexity Zoo:P#kpbp|PBP]].</div>Jh