# Complexity Zoo:B

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

##### βP: Limited-Nondeterminism NP

βkP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(logkn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(logkn) that the answer is 'yes.'

Then βP is the union of βkP over all constant k.

There exist oracles relative to which basically any consistent inclusion structure among the βkP's can be realized [BG98].

β2P contains LOGNP and LOGSNP.

##### BH: Boolean Hierarchy Over NP

The smallest class that contains NP and is closed under union, intersection, and complement.

The levels are defined as follows:

• BH1 = NP.
• BH2i is the class of languages that are the intersection of a BH2i-1 language with a coNP language.
• BH2i+1 is the class of languages that are the union of a BH2i language with an NP language.

Then BH is the union over all i of BHi.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ2P and indeed in PNP[log].

If BH collapses at any level, then PH collapses to Σ3P [Kad88].

##### BPd(P): Polynomial Size d-Times-Only Branching Program

Defined in [Weg88].

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.

BPd(P) strictly contains BPd-1(P), for every d > 1 [Tha98].

Contained in PBP.

##### BPE: Bounded-Error Probabilistic E

Has the same relation to E as BPP does to P.

EE = BPE if and only if EXP = BPP [IKW01].

##### BPEE: Bounded-Error Probabilistic EE

Has the same relation to EE as BPP does to P.

##### BPHSPACE(f(n)): Bounded-Error Halting Probabilistic f(n)-Space

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 and every random tape setting.

Contains RHSPACE(f(n)).

Is contained in DSPACE(f(n)3/2) [SZ95].

##### BPL: Bounded-Error Probabilistic L

Has the same relation to L as BPP does to P. The Turing machine has to halt for every input and every randomness.

Contained in SC [Nis92] and in PL.

Equals AM.

##### BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ2PΠ2P [Lau83], and indeed in ZPPNP [GZ97].

If BPP contains NP, then RP = NP [Ko82,Gil77] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete problems. [Sip82], [HH86] give oracles relative to which BPP has no complete problems.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(nc) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

A zero-one law exists stating that BPP has p-measure zero unless BPP = EXP [Mel00].

Equals Almost-P.

##### BPPcc: Communication Complexity BPP

The analogue of Pcc for bounded-error probabilistic communication complexity.

Does not equal Pcc, and is not contained in NPcc, because of the EQUALITY problem.

Defined in [BFS86].

##### BPP$k$cc: BPPcc in NOF model, $k$ players

Has the same relation to BPPcc and BPP as P$k$cc does to Pcc and P.

NP$k$cc is not contained in BPP$k$cc for $k\le(1-\delta)\cdot\log n$ players, for any constant $\delta>0$ [DP08].

##### BPPKT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP with an oracle that, given a string x, returns the minimum over all programs P that output xi on input i, of the length of P plus the maximum time taken by P on any input.

A similar class was defined in [ABK+02], where it was also shown that in BPPKT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.

##### BPP/log: BPP With Logarithmic Karp-Lipton Advice

The class of problems solvable by a semantic 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 BQP/poly.

Contained in BPP/mlog.

##### BPP/mlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic 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.

Contained in BPP/rlog.

##### BPP//log: BPP With Logarithmic Randomness-Dependent Advice

The class of problems solvable by a 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.

Defined in [TV02], where it was also shown that if EXP is in BPP//log then EXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.

##### BPP/rlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic 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.

Contains BPP/mlog. The inclusion is strict, because BPP/rlog contains any finitely sparse language by fingerprinting; see the discussion for ALL.

Contained in BPP//log.

##### BPP-OBDD: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram

Same as P-OBDD, except that probabilistic transitions are allowed and the OBDD need only accept with probability at least 2/3.

Does not contain the integer multiplication problem [AK96].

Strictly contained in BQP-OBDD [NHK00].

##### BPPpath: Threshold BPP

Same as BPP, except that now the computation paths need not all have the same length.

Defined in [HHT97], where the following was also shown:

• BPPpath contains MA and PNP[log], and is contained in PP and BPPNP.
• BPPpath is closed under complementation, intersection, and union.
• If BPPpath = BPPpathBPPpath, then PH collapses to BPPpath.
• If BPPpath contains Σ2P, then PH collapses to BPPNP.

There exists an oracle relative to which BPPpath is not contained in Σ2P [BGM02].

An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages $L$ for which there exists a pair of polynomial-time Turing machines $A$ and $B$ such that the following conditions hold for all $x$:

• If $x\in L$, $\Pr_{r\in\{0,1\}^{\mathrm{poly}(\left\vert x\right\vert)}}\left[A(x,r)\mid B(x,r)\right]\ge \frac23$.
• If $x\notin L$, $\Pr_{r\in\{0,1\}^{\mathrm{poly}(\left\vert x\right\vert)}}\left[A(x,r)\mid B(x,r)\right]< \frac13$.
• $\Pr_{r\in\{0,1\}^{\mathrm{poly}(n)}}\left[B(x,r)\right]>0$.

We say that $B$ 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 ⊆ BPPpath nearly trivial.

##### BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2O((log n)^k)); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.

Defined in [CNS99], where the following was also shown:

If either (1) #P does not have a subexponential-time bounded-error algorithm, or (2) EXP does not have subexponential-size circuits, then the BPQP hierarchy is strict -- that is, for all a < b at least 1, BPTIME(2(log n)^a) is strictly contained in BPTIME(2(log n)^b).

##### BPSPACE(f(n)): Bounded-Error Probabilistic f(n)-Space

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.

Contains RSPACE(f(n)) and BPHSPACE(f(n)).

##### BPTIME(f(n)): Bounded-Error Probabilistic f(n)-Time

Same as BPP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [Gil77].

BPTIME(nlog n) does not equal BPTIME(2n^ε) for any ε>0 [KV88]. Proving a stronger time hierarchy theorem for BPTIME is a longstanding open problem; see [BH97] for details.

[Bar02] has shown the following:

• 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(nd)/(log n) does not equal BPTIME(nd+1)/(log n).
• In the uniform setting, if BPP has complete problems then BPTIME(nd) does not equal BPTIME(nd+1).
• BPTIME(n) does not equal NP.

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(nd)/1 does not equal BPTIME(nd+1)/1. They also proved a hierarchy theorem for HeurBPTIME.

For another bounded-error hierarchy result, see BPQP.

##### BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

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 [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 [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQPBQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

• BQP does not equal to BPP [BV97] (and by similar arguments, is not in P/poly).
• BQP is not contained in MA [Wat00].
• BQP is not contained in ModpP for prime p [GV02].
• NP, and indeed NP ∩ coNP, are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively [BBB+97].
• SZK is not contained in BQP [Aar02].
• BQP is not contained in SZK (follows easily using the quantum walk problem in [CCD+03]).
• PPAD is not contained in BQP [Li11].

##### BQP/log: BQP With Logarithmic-Size Karp-Lipton Advice

Same as BQP/poly except that the advice is O(log n) bits instead of a polynomial number.

Contained in BQP/mlog.

##### BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

Is to BQP/mpoly as ∃BPP is to MA. Namely, the BQP machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though BQP/mpoly is a more natural class, BQP/poly follows the standard definition of advice as a class operator [KL82].

Contained in BQP/mpoly and contains BQP/log.

##### BQP/mlog: BQP With Logarithmic-Size Deterministic Merlin-Like Advice

Same as BQP/mpoly except that the advice is O(log n) bits instead of a polynomial number.

Strictly contained in BQP/qlog [NY03].

##### BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

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.

Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomial-size classical circuits.

Referred to with a variety of other ad hoc names, including BQP/poly on occassion.

Contains BQP/qlog, and is contained in BQP/qpoly.

Does not contain ESPACE [NY03].

##### BQP/qlog: BQP With Logarithmic-Size Quantum Advice

Same as BQP/mlog except that the advice is quantum instead of classical.

Strictly contains BQP/mlog [NY03].

Contained in BQP/mpoly.

##### BQP/qpoly: BQP With Polynomial-Size Quantum Advice

The class of problems solvable by a BQP machine that receives a quantum state ψn as advice, which depends only on the input length n.

As with 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 [NY03] call BQP/*Qpoly.) Indeed, such a condition would make quantum advice unusable, by a continuity argument.

Does not contain EESPACE [NY03].

[Aar04b] shows the following:

• There exists an oracle relative to which BQP/qpoly does not contain NP.
• BQP/qpoly is contained in PP/poly.

A classical oracle separation between BQP/qpoly and BQP/mpoly is presently unknown, but there is a quantum oracle separation [AK06]. An unrelativized separation is too much to hope for, since it would imply that PP is not contained in P/poly.

Contains BQP/mpoly.

##### BQP-OBDD: Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram

Same as P-OBDD, except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.

Strictly contains BPP-OBDD [NHK00].

##### BQPSPACE: Bounded-Error Quantum PSPACE

Equals PSPACE and PPSPACE.

##### BQTIME(f(n)): Bounded-Error Quantum f(n)-Time

Same as BQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

##### BQPCTC: BQP With Closed Time Curves

Same as BQP with access to two sets of qubits: causality-respecting qubits and CTC qubits.

Defined in [Aar05c], where it was shown that PSPACE is contained in BQPCTC, which in turn is contained in SQG.

##### BQPtt/poly: BQP/mpoly With Truth-Table Queries

Same as BQP/mpoly, except that the machine only gets to make nonadaptive queries to whatever oracle it might have.

Defined in [NY03b], where it was also shown that P is not contained in BQPtt/poly relative to an oracle.

##### k-BWBP: Bounded-Width Branching Program

Alternate name for k-PBP.