Difference between revisions of "Complexity Zoo:B"
(BQP_CTC = PSPACE) 
m (→BPP: BoundedError Probabilistic PolynomialTime) 

Line 113:  Line 113:  
Indeed, <i>any</i> proof that BPP = [[Complexity Zoo:P#pP]] requires showing either that [[Complexity Zoo:N#nexpNEXP]] is not in [[Complexity Zoo:P#ppolyP/poly]], or else that [[Complexity Zoo:Symbols#sharpp#P]] requires superpolynomialsize arithmetic circuits [[zooref#ki02[KI02]]].  Indeed, <i>any</i> proof that BPP = [[Complexity Zoo:P#pP]] requires showing either that [[Complexity Zoo:N#nexpNEXP]] is not in [[Complexity Zoo:P#ppolyP/poly]], or else that [[Complexity Zoo:Symbols#sharpp#P]] requires superpolynomialsize arithmetic circuits [[zooref#ki02[KI02]]].  
−  BPP is not known to contain complete  +  BPP is not known to contain complete languages. [[zooref#sip82[Sip82]]], [[zooref#hh86[HH86]]] give oracles relative to which BPP has no complete languages. 
There exist oracles relative to which [[Complexity Zoo:P#pP]] = [[Complexity Zoo:R#rpRP]] but still [[Complexity Zoo:P#pP]] is not equal to BPP [[zooref#bf99[BF99]]].  There exist oracles relative to which [[Complexity Zoo:P#pP]] = [[Complexity Zoo:R#rpRP]] but still [[Complexity Zoo:P#pP]] is not equal to BPP [[zooref#bf99[BF99]]]. 
Revision as of 07:45, 6 March 2018
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_{H}SPACE(f(n))  BPL  BP•NP  BPP  BPP^{cc}  BPP_{}^{cc}  BPP^{KT}  BPP/log  BPP/mlog  BPP//log  BPP/rlog  BPPOBDD  BPP_{path}  BPQP  BPSPACE(f(n))  BPTIME(f(n))  BQNC  BQNP  BQP  BQP/log  BQP/poly  BQP/mlog  BQP/mpoly  BQP/qlog  BQP/qpoly  BQPOBDD  BQPSPACE  BQP_{CTC}  BQP_{tt}/poly  BQTIME(f(n))  kBWBP
βP: LimitedNondeterminism NP
β_{k}P is the class of decision problems solvable by a polynomialtime Turing machine that makes O(log^{k}n) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(log^{k}n) that the answer is 'yes.'
Then βP is the union of β_{k}P 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 β_{k}P's can be realized [BG98].
β_{2}P contains LOGNP and LOGSNP.
BC_{=}P: BoundedError C_{=}P
The class of decision problems solvable by an NP machine such that
 If the answer is 'yes' then exactly 1/2 of the computation paths accept.
 If the answer is 'no' then either at most 1/4 or at least 3/4 of the computation paths accept.
(Here all computation paths have the same length.)
Defined in [Wat15], where it was shown that BC_{=}P admits efficient amplification and is closed under union, intersection, disjunction, and conjunction, and that coRP ⊆ BC_{=}P ⊆ BPP.
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_{1} = NP.
 BH_{2i} is the class of languages that are the intersection of a BH_{2i1} 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 Δ_{2}P and indeed in P^{NP[log]}.
If BH collapses at any level, then PH collapses to Σ_{3}P [Kad88].
BP_{d}(P): Polynomial Size dTimesOnly 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_{d1}(P), for every d > 1 [Tha98].
Contained in PBP.
BPE: BoundedError Probabilistic E
Has the same relation to E as BPP does to P.
EE = BPE if and only if EXP = BPP [IKW01].
BPEE: BoundedError Probabilistic EE
Has the same relation to EE as BPP does to P.
BP_{H}SPACE(f(n)): BoundedError 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_{H}SPACE(f(n)).
Is contained in DSPACE(f(n)^{3/2}) [SZ95].
BPL: BoundedError 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: BoundedError Probabilistic PolynomialTime
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 randomnumber source.
Defined in [Gil77].
Contained in Σ_{2}P ∩ Π_{2}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 superpolynomialsize arithmetic circuits [KI02].
BPP is not known to contain complete languages. [Sip82], [HH86] give oracles relative to which BPP has no complete languages.
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 zeroone law exists stating that BPP has pmeasure zero unless BPP = EXP [Mel00].
Equals AlmostP.
See also: BPP_{path}.
BPP^{cc}: Communication Complexity BPP
The analogue of P^{cc} for boundederror probabilistic communication complexity.
Does not equal P^{cc}, and is not contained in NP^{cc}, because of the EQUALITY problem.
If the classes are defined in terms of partial functions, then BPP^{cc}
BPP_{}^{cc}: BPP^{cc} in NOF model, players
Has the same relation to BPP^{cc} and BPP as P_{}^{cc} does to P^{cc} and P.
NP_{}^{cc} is not contained in BPP_{}^{cc} for players, for any constant [DP08].
BPP^{KT}: BPP With TimeBounded 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 oneway function on a nonnegligible fraction of inputs.
See also: P^{K}.
BPP/log: BPP With Logarithmic KarpLipton 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 MerlinLike 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 RandomnessDependent 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 MerlinLike 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.
BPPOBDD: PolynomialSize BoundedError Ordered Binary Decision Diagram
Same as POBDD, 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 BQPOBDD [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}^{BPPpath}, then PH collapses to BPP_{path}.
 If BPP_{path} contains Σ_{2}P, then PH collapses to BPP^{NP}.
There exists an oracle relative to which BPP_{path} is not contained in Σ_{2}P [BGM02].
An alternate characterization of BPP_{path} uses the idea of postselection. That is, BPP_{path} is the class of languages for which there exists a pair of polynomialtime Turing machines and such that the following conditions hold for all :
 If , .
 If , .
 .
We say that is the postselector. 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: BoundedError Probabilistic QP
Equals BPTIME(2^{O((log n)^k)}); that is, the class of problems solvable in quasipolynomialtime on a boundederror machine.
Defined in [CNS99], where the following was also shown:

If either (1) #P does not have a subexponentialtime boundederror algorithm, or (2) EXP does not have subexponentialsize 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)): BoundedError 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_{H}SPACE(f(n)).
BPTIME(f(n)): BoundedError Probabilistic f(n)Time
Same as BPP, but with f(n)time (for some constructible function f) rather than polynomialtime 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 boundederror hierarchy result, see BPQP.
BQNC: Alternate Name for QNC
BQNP: Alternate Name for QMA
BQP: BoundedError Quantum PolynomialTime
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 polynomialsize 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_{p}P 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 LogarithmicSize KarpLipton 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 PolynomialSize KarpLipton 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 LogarithmicSize Deterministic MerlinLike 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 PolynomialSize Deterministic MerlinLike 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 polynomialsize quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomialsize 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 LogarithmicSize 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 PolynomialSize 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.
BQPOBDD: PolynomialSize BoundedError Quantum Ordered Binary Decision Diagram
Same as POBDD, except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.
Strictly contains BPPOBDD [NHK00].
BQPSPACE: BoundedError Quantum PSPACE
BQTIME(f(n)): BoundedError Quantum f(n)Time
Same as BQP, but with f(n)time (for some constructible function f) rather than polynomialtime machines.
Defined in [BV97].
BQP_{CTC}: BQP With Closed Time Curves
Same as BQP with access to two sets of qubits: causalityrespecting 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 = PSPACE. Therefore, BQP_{CTC} = PSPACE; this was also shown in [AW09].
See also P_{CTC}.
BQP_{tt}/poly: BQP/mpoly With TruthTable 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.
kBWBP: BoundedWidth Branching Program
Alternate name for kPBP.