Complexity Zoo:B

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

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 - BC₌P - BH - BP_d(P) - BPE - BPEE - BP_HSPACE(f(n)) - BPL - BP•L - BP•NP - BPP - BPP^cc - BPP_$k$^cc - BPP^KT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPP_path - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQP_CTC - BQP_tt/poly - BQTIME(f(n)) - k-BWBP

βP: Limited-Nondeterminism NP

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

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

Defined in [KF84]. See also the survey [GLM96].

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

β₂P 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:

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

Then BH is the union over all i of BH_i.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ₂P and indeed in P^NP[log].

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

See also: DP, QH.

---

BP_d(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.

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

Contained in PBP.

See also: P-OBDD, k-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.

---

BP_HSPACE(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 R_HSPACE(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.

---

BP•NP: Probabilistic NP

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 Σ₂P ∩ Π₂P [Lau83], and indeed in ZPP^NP [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(n^c) 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.

See also: BPP_path.

---

BPP^cc: Communication Complexity BPP

The analogue of P^cc for bounded-error probabilistic communication complexity.

Does not equal P^cc, and is not contained in NP^cc, because of the EQUALITY problem.

Defined in [BFS86].

---

BPP_$k$^cc: BPP^cc in NOF model, $k$ players

Has the same relation to BPP^cc and BPP as P_$k$^cc does to P^cc and P.

NP_$k$^cc is not contained in BPP_$k$^cc for $k\leq (1-\delta )\cdot \log n$ players, for any constant $\delta >0$ [DP08].

---

BPP^KT: 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 x_i 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 BPP^KT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.

See also: P^K.

---

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

---

BPP_path: 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:

• BPP_path contains MA and P^NP[log], and is contained in PP and BPP^NP.
• BPP_path is closed under complementation, intersection, and union.
• If BPP_path = BPP_path^BPP_path, then PH collapses to BPP_path.
• If BPP_path contains Σ₂P, then PH collapses to BPP^NP.

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

An alternate characterization of BPP_path uses the idea of post-selection. That is, BPP_path 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]\geq {\frac {2}{3}}$.
• 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]<{\frac {1}{3}}$.
• $\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 ⊆ BPP_path nearly trivial.

See Also: PostBQP (quantum analogue).

---

BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2^{O((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 BP_HSPACE(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(n^{log n}) does not equal BPTIME(2^{n^ε}) 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(n^d)/(log n) does not equal BPTIME(n^d+1)/(log n).
• In the uniform setting, if BPP has complete problems then BPTIME(n^d) does not equal BPTIME(n^d+1).
• BPTIME(n) does not equal NP.

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(n^d)/1 does not equal BPTIME(n^d+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.

BQP^BQP = 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 Mod_pP 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].

---

BQP_CTC: 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 BQP_CTC, which in turn is contained in SQG.

See also P_CTC.

---

BQP_tt/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 BQP_tt/poly relative to an oracle.

---

k-BWBP: Bounded-Width Branching Program

Alternate name for k-PBP.