Difference between revisions of "Complexity Zoo:B"
m (→BQP: Bounded-Error Quantum Polynomial-Time)
m (1 revision: Complexity zoo import.)
Revision as of 22:10, 17 November 2012
β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].
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].
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
BPEE: Bounded-Error Probabilistic EE
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.
BPL: Bounded-Error Probabilistic L
BPNP: Probabilistic NP
BPP: Bounded-Error Probabilistic Polynomial-Time
The class of decision problems solvable by an NP machine such that
- If the answer is 'yes' then at least 2/3 of the computation paths accept.
- 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].
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.
See also: BPPpath.
BPPcc: Communication Complexity BPP
The analogue of Pcc for bounded-error probabilistic communication complexity.
Defined in [BFS86].
BPPcc: BPPcc in NOF model, players
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.
See also: PK.
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.
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.
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].
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.
An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :
- If , .
- If , .
We say that 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.
See Also: PostBQP (quantum analogue).
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.
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].
[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.
For another bounded-error hierarchy result, see BPQP.
BQNC: Alternate Name for QNC
BQNP: Alternate Name for QMA
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.
BQPBQP = BQP [BV97].
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 (in fact, this holds 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].
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.
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.
BQP/qlog: BQP With Logarithmic-Size Quantum Advice
Same as BQP/mlog except that the advice is quantum instead of classical.
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.
[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.
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.
BQPSPACE: Bounded-Error Quantum PSPACE
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.
See also PCTC.
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.
k-BWBP: Bounded-Width Branching Program
Alternate name for k-PBP.