The class of decision problems solvable by an NP machine such that
(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).
Contained in O2P since problems requiring exponential sized circuits can be verified in O2E [GLV24] [Li23] which can be used to derandomize [IW97].
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 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(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.
See also: BPPpath.
The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.
The canonical #P-complete problem is #SAT.
Defined in [Val79], where it was also shown that #Perfect Matching (or equivalently, Permanent) is #P-complete. What makes that interesting is that the associated decision problem Perfect Matching is in P.
Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85]. Likewise, any problem in #P can be approximated to within a constant factor by a machine in FP||NP running in time [SU05].
The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.
Named in [Imp02], though it has been considered since the 1970's.
If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].
The class of problems that are in PA with probability 1, where A is an oracle chosen uniformly at random.
The class of decision problems for which a "yes" answer can be verified by an Arthur-Merlin protocol, as follows.
Arthur, a BPP (i.e. probabilistic polynomial-time) verifier, generates a "challenge" based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that
Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin [GS86]. So, Arthur never needs to hide information from Merlin.
Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM [BM88]. Also, the result of [GS86] can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).
AM contains graph nonisomorphism.
Contains NP, BPP, and SZK, and is contained in NP/poly.AM is also contained in Π2P and this proof relativizes so the containment holds relative to any oracle.
If AM contains coNP then PH collapses to Σ2P ∩ Π2P [BHZ87].
There exists an oracle relative to which AM is not contained in PP [Ver92].
AM = NP under a strong derandomization assumption: namely that some language in NE ∩ coNE requires nondeterministic circuits of size 2Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)
Defined in [OW93] to be the class of decision problems that have a good average-case BPP algorithm, whenever the input is chosen from an efficiently samplable distribution.
Note that this is not the same as the BPP version of AvgP.
Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.
The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.
Defined by [KRC00], who also show the following:
AxPP is recursively enumerable [Jeř07].
The class of decision problems solvable by an NP machine such that
(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.
Has the same relation to E as BPP does to P.
EE = BPE if and only if EXP = BPP [IKW01].
Has the same relation to EE as BPP does to P.
Has the same relation to L as BPP does to P. The Turing machine has to halt for every input and every randomness.
The randomness is read once. That is, each random bit is only given once and to be referenced again it must be stored in the working space. This in contrast to the two way randomness of BP•L.
Contained in SC [Nis92], PL, BP•L, ZP•L [Nis93], DET [Coo85], NC2 and P [BCP83].
Languages decided with two sided bounded error by a log space machine with a read only tape containing random bits. In contrast with BPL, the random bits can be read multiple times without storing them in working space.
For example, BP•L contains RNC1 since NC1 is contained in L. However, this reduction does not hold for BPL.
It is unknown if BP•L is contained in P [Nis93].
Contained in 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.
If the classes are defined in terms of partial functions, then BPPcc
Has the same relation to BPPcc and BPP as Pcc does to Pcc and P.
NPcc is not contained in BPPcc for players, for any constant [DP08].
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.
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.
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.
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 thenEXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.
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.
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:
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 for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :
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).
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:
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.
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:
If P=BQP relative to a random oracle then BQP=BPP [FR98].
The class of problems such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,
Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.
Check is contained in NEXP ∩ coNEXP [FRS88].
[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.
The class of problems L that are efficiently autoreducible, in the sense that given an input x and access to an oracle for L, a BPP machine can compute L(x) by querying L only on points that differ from x.
Defined in [Yao90b].
[BG94] show that, assuming NEE is not contained in BPEE, Coh ∩ NP is not contained in any of compNP, Check, or frIP.
Same as compNP but for interactive (IP) proofs instead of NP proofs.
More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.
Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in compIP [BG94].
If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.
If NP does not equal coNP, then P does not equal NP. But the other direction is not known.
See also: NP ∩ coNP.
Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP#P. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then EH collapses to the third level [SS04].
Co-NP is equal to SO-A, the second-order queries where the second-order quantifiers are only universals.
Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over the verifier's view of their interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)
Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)
Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).
On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].
A level of PH, the polynomial hierarchy.
One Δ2P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [Kre88]
Contains BH.
There exists an oracle relative to which Δ2P is not contained in PP [Bei94].
There exists another oracle relative to which Δ2P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].
There exists an oracle B for which BPPB is exponentially more powerful than Δ2PB [KV96].
If P = NP, then any polynomial-size circuit C can be learned in Δ2P with C oracle [Aar06].
Same as BPP, except that the random bit source is biased as follows. Each bit could depend on all the previous bits in arbitrarily complicated ways; the only promise is that the bit is 1 with probability in the range [δ,1-δ], conditioned on all previous bits.
So clearly 0-BPP = P and 1/2-BPP = BPP.
It turns out that, for any δ>0, δ-BPP = BPP [VV85], [Zuc91].
Same as δ-BPP, but for RP instead of BPP.
For any δ>0, δ-RP = RP [VV85].
Equals DTIME(2O(n)).
Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).
There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].
Problems hard for BPP under Turing reductions have measure 1 in E [AS94].
It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.
[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.
[BF03] gave a proof that if E = NE, then no sparse set is collapsing, where they defined a set to be collapsing if and if for all such that and are Turing reducible to each other, and are many-to-one reducible to each other.
Contrast with EXP.
Equals DTIME(22O(n)) (though some authors alternatively define it as being equal to DTIME(2O(2n))).
EE = BPE if and only if EXP = BPP [IKW01].
Equals DSPACE(2O(n)).
If E = ESPACE then P = BPP [HY84].
Indeed if E has nonzero measure in ESPACE then P = BPP [Lut91].
ESPACE is not contained in P/poly [Kan82].
Is not contained in BQP/mpoly [NY03].
See also: EXPSPACE.
The class of problems for which there exists a BPP machine M such that, for all inputs x,
Alternatively defined as NPBPP.
Contains NP and BPP, and is contained in MA and SBP.
∃BPP seems obviously equal to MA, yet [FFK+93] constructed an oracle relative to which they're unequal! Here is the difference: if the answer is "yes," MA requires only that there exist a y such that for at least 2/3 of random strings r, M(x,y,r) accepts (where M is a P predicate). For all other y's, the proportion of r's such that M(x,y,r) accepts can be arbitrary (say, 1/2). For ∃BPP, by contrast, the probability that M(x,y) accepts must always be either at most 1/3 or at least 2/3, for all y's.
Has the same relation to BPP as FNP does to NP. Equivalently, it is the randomised analogue of FP.
FERT and FPERT are parameterized classes. FERT formally defined as the class of decision problems of the form (x, k), decidable in polynomial time by a probabilistic Turing Machine such that
Here, f is an arbitrary function (from the reals to <0,1/2]).
Defined in [KW15]. Contains BPP and is contained in para-PP and in FPERT.
FHk is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis. (Conditional phase flip gates are fine, for example.) Thus
It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FHk is strictly contained in FHk+1).
Defined in [Shi03].
The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,
Contains compIP [BG94] and Check [BK89].
Contained in MIP = NEXP [FRS88].
Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].
The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPP machine.
[FS04] showed a strict hierarchy theorem for HeurBPP; thus, HeurBPP does not equal HeurBPTIME(nc) for any fixed c.
The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that
Defined in [Bab85].
An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.
There exists an oracle relative to which BQP is not in MA [Wat00].
Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].
Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size for any . In the same paper, the result was used to show that MA/1 cannot be solved on more than a fraction of inputs having length by any circuit of size . Finally, it was shown that MA does not have arithmetic circuits of size .
Nondeterministic exponential time (i.e. NTIME(2p(n)) for p a polynomial).
Equals MIP [BFL91] (but not relative to all oracles).
NEXP is in P/poly if and only if NEXP = MA [IKW01].
[KI02] show the following:
Does not equal EXP if and only if there is a sparse set in NP that is not in P.
There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].
The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].
Defined in [DDP+98].
Contained in SZK.
[GSV99] showed the following:
NIPZK can be defined similarly.
There is an oracle separating NISZK from PP [BCHTV17].
The class of dashed hopes and idle dreams.
More formally: an "NP machine" is a nondeterministic polynomial-time Turing machine.
Then NP is the class of decision problems solvable by an NP machine such that
Equivalently, NP is the class of decision problems such that, if the answer is "yes," then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is "no," then the algorithm must declare invalid any purported proof that the answer is "yes."
For example, the SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.
A decision problem is NP-complete if (1) it is in NP, and (2) any problem in NP can be reduced to it (under some notion of reduction). The class of NP-complete problems is sometimes called NPC.
That NP-complete problems exist is immediate from the definition. The seminal result of Cook [Coo71], Karp [Kar72], and Levin [Lev73] is that many natural problems (that have nothing to do with Turing machines) are NP-complete.
The first such problem to be shown NP-complete was SAT [Coo71]. Other classic NP-complete problems include:
For many, many more NP-complete problems, see [GJ79].
There exists an oracle relative to which P and NP are unequal [BGS75]. Indeed, P and NP are unequal relative to a random oracle with probability 1 [BG81] (see [AFM01] for a novel take on this result). Though random oracle results are not always indicative about the unrelativized case [CCG+94].
There even exists an oracle relative to which the P versus NP problem is outside the usual axioms of set theory [HH76].
If we restrict to monotone classes, mP is strictly contained in mNP [Raz85].
Perhaps the most important insight anyone has had into P versus NP is to be found in [RR97]. There the authors show that no 'natural proof' can separate P from NP (or more precisely, place NP outside of P/poly), unless secure pseudorandom generators do not exist. A proof is 'natural' if it satisfies two conditions called constructivity and largeness; essentially all lower bound techniques known to date satisfy these conditions. To obtain unnatural proof techniques, some people suspect we need to relate P versus NP to heavy-duty 'traditional' mathematics, for instance algebraic geometry. See [MS02] (and the survey article [Reg02]) for a development of this point of view.
For more on P versus NP (circa 1992) see [Sip92]. For an opinion poll, see [Gas02]. P vs NP is a "Millenium Prize" problem [CMI00].
If P equals NP, then NP equals its complement coNP. Whether NP equals coNP is also open. NP and coNP can be extended to the polynomial hierarchy PH.
The set of decision problems in NP, but not in P or NPC, is sometimes called NPI. If P does not equal NP then NPI is nonempty [Lad75].
Probabilistic generalizations of NP include MA and AM. If NP is in coAM (or BPP) then PH collapses to Σ2P [BHZ87].
PH also collapses to Σ2P if NP is in P/poly [KL82].
There exist oracles relative to which NP is not in BQP [BBB+97].
An alternate characterization is NP = PCP(log n, O(1)) [ALM+98].
Also, [Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic. This leads to the subclass SNP.
It is known that if any NP-complete language is sparse (contains no more than a polynomial number of strings of length ), then P = NP. [BH08] improved this result, showing that if any language in NP has an NP-hard set of subexponential density, then coNP is contained in NP/poly and thus, by [Yap82], PH collapses to the third level.
NP is equal to SO-E, the second-order queries where the second-order quantifiers are only existantials.
The class of functions computable in randomized polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of MA.
L is in OMA if there exists a randomized, polynomial time verifier V taking an input and a witness, so that:
NP is contained in OMA iff NP is in P/poly [FSW09].
EXP is contained in P/poly iff EXP = OMA [FSW09].
BPP is contained in OMA [GM15].
Implicit in [San07] that OMA/1 (that is, OMA with 1 bit of trusted advice) does not have circuits of size for any .
The class that started it all.
The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)
Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.
Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].
Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.
Important subclasses of P include L, NL, NC, and SC.
P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.
Efforts to generalize P resulted in BPP and BQP.
The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.
In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)
P queries are exactly the one that can be written in the While/cons languages.
P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.
P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].
The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be nonuniform; that is, there could be a completely different circuit for each input length.
Equivalently, P/poly is the class of decision problems solvable by a polynomial-time Turing machine that receives a trusted 'advice string,' that depends only on the size n of the input, and that itself has size upper-bounded by a polynomial in n.
Contains BPP by the progenitor of derandomization arguments [Adl78] [KL82]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which BPP/log does not equal BPP/mlog, while BPP/mlog and BPP/rlog are not equal relative to any oracle.)
[KL82] showed that, if P/poly contains NP, then PH collapses to the second level, Σ2P.
They also showed:
It was later shown that, if NP is contained in P/poly, then PH collapses to ZPPNP [KW98] and indeed to O2P [CR06] (which is unconditionally included in P/poly). This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to Δ2P [Wil85].
If NP is not contained in P/poly, then P does not equal NP. Much of the effort toward separating P from NP is based on this observation. However, a 'natural proof' as defined by [RR97] cannot be used to show NP is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2Ω(n^ε) for some ε>0.
If NP is contained in P/poly, then MA = AM [AKS+95]
The monotone version of P/poly is mP/poly.
P/poly has measure 0 in E with Σ2P oracle [May94b].
Strictly contains IC[log,poly] and P/log.
The complexity class of P with untrusted advice depending only on input size is ONP.
Let Δ0P = Σ0P = Π0P = P. Then for i>0, let
Then PH is the union of these classes for all nonnegative constants i.
PH can also be defined using alternating quantifiers: it's the class of problems of the form, "given an input x, does there exist a y such that for all z, there exists a w ... such that φ(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and φ is a polynomial-time computable predicate. It's not totally obvious that this is equivalent to the first definition, since the first one involves adaptive NP oracle queries and the second one doesn't, but it is.
Defined in [Sto76].
Contained in P with a PP oracle [Tod89].
Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].
Furthermore, there exist oracles separating any ΣiP from Σi+1P. In fact, relative to a random oracle, the hierarchy is infinite: each level is strictly contained in the next, with probability 1 [RST15] (this was an open problem for 29 years). Previously, it had been known that if it had collapsed relative to a random oracle, then it would have collapsed unrelativized [Boo94].
It was shown in [CPO7] that if the NP Machine Hypothesis holds, then.
For a compendium of problems complete for different classes of the Polynomial Hierarchy see [Sch02a] and [Sch02b].
PH is equal to the set of boolean queries recognizable by a concurent random acess machine using exponentially many processors and constant time[Imm89].
Since NP is the class of query expressible in second-order existantial logic, PH can also be defined as the query expressible in second-order logic.
Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.
For what it's worth, the present zookeeper has more qualms about admitting DTIME(n1000) into PhP than BQTIME(n2). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10k with k in the low hundreds.) In practice, less than 1050 bits and less than 1080 bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.
Alias for BPPpath.
The class of decision problems solvable by an NP machine such that
Defined in [Gil77].
PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, PPP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].
Contains PNP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ2P [Bei94].
BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PPBQP = PP.
APP is PP-low [Li93].
For a random oracle A, PPA is strictly contained in PSPACEA with probability 1 [ABF+94].
For any fixed k, there exists a language in PP that does not have circuits of size nk [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size nk with quantum advice [Aar06] and [Yir24].
By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].
PP can be generalized to the counting hierarchy CH.
The class of decision problems solvable in polynomial time by a quantum Turing machine, with less than 1/2 probability of error.Similar to BQP in definition, but without bounded error.
Defined in [Wat09], where it shown to be equivalent to PP.
Equals PP and therefore PPBPP [KST+89b] as well as PostBQP [Aar05b].
Same as PromiseRP, but for BPP instead of RP.
Defined in [BF99].
Same as PromiseBPP, but for BQP instead of BPP.
If PromiseBQP = PromiseP then BQP/mpoly = P/poly.
The class of promise problems solvable by an RP machine. I.e., the machine must accept with probability at least 1/2 for "yes" inputs, and with probability 0 for "no" inputs, but could have acceptance probability between 0 and 1/2 for inputs that do not satisfy the promise.
Defined in [BF99], where it was also shown that BPP is in RPPromiseRP[1] (i.e. with a single oracle query to PromiseRP).
Contained in PromiseBPP.
The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
Has the same relation to BPHSPACE(f(n)) as RP does to BPP.
The class of decision problems solvable by an NP machine such that
Defined in [Gil77] (implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2).
Contains the problem of testing whether an integer is prime [AH87], although this problem was subsequently shown to be in P [AKS02].
For other problems in RP, see the standard text on randomized algorithms, [MR95].
Has the same p-measure as ZPP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].
The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF2 contains both ⊕P and NP by using the counter as a witness.
Defined in [CF91], where it was also shown that SF5 = PSPACE.
The complexity of SF2, SF3, and SF4 was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:
(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)
The class of languages accepted by a BQP machine subject to the constraint that at every time step t, the machine's state is exponentially close to a tree state -- that is, a state expressible by a polynomial-size tree of additions and tensor products (together with complex constants and |0> and |1> leaf nodes).
More formally, a uniform classical polynomial-time algorithm generates a sequence of gates g(1), ... ,g(p(n)). Each g(t) can be either be selected from some finite universal basis of unitary gates (the choice turns out not to matter), or can be a 1-qubit measurement. When we perform a measurement, the state evolves to one of two possible pure states, with the usual probabilities, rather than to a mixed state. We require that the final gate g(p(n)) is a measurement of the first qubit. If at least one intermediate state was more than distance 2-Ω(n) away from the nearest state of tree size at most p(n), then the outcome of the final measurement is chosen adversarially; otherwise it is given by the usual Born probabilities. The measurement must return 1 with probability at least 2/3 if the input is in the language, and with probability at most 1/3 otherwise.
Contains BPP, and is contained in BQP.
Defined in [Aar03b], where it was also shown that TreeBQP iscontained in the third level of PH, which might provide weak evidence thatTreeBQP does not equal BQP.
The class of decision problems for which there exists a polynomial-time machine M such that:
Defined in a recent post of the blog Shtetl-Optimized. See there for an explanation of the class's name.
Contains ZPP by the same argument that places BPP in P/poly.
Also contains P with TALLY ∩ NP ∩ coNP oracle.
Is contained in NP ∩ coNP and YPP.
Is equal to ONP ∩ coONP.
The probabilistic analogue of YP; it is to YP what MA is to NP. Formally, the class of decision problems for which there exists a syntactic BPP machine M such that:
To amplify a YPP machine, one can run it multiple times, then accept if a majority of runs accept, reject if a majority reject, and otherwise output "I don't know."
Contains BPP and YP, and is contained in MA and P/poly.
Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.
Contains BQP and YPP, and is contained in QMA and BQP/qpoly.
Has the same relationship to BP•L as ZPP has to BPP. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:
1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.
2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.
Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.
Contained in BP•L.
Defined as the class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial, in [Gil77]. (Proposition 5.5(iii) in this paper shows that the two definitions above are equivalent.)
Contains the problem of testing whether an integer is prime [SS77] [AH87].
In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].
There exists an oracle relative to which ZPP = EXP [Hel84a], [Hel84b], [Kur85], [Hel86].
Has the same p-measure as RP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68f589f128ac94d15db09cab8923d093aeebf7a6)
![{\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]<{\frac {1}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa07825632386c5a2f15399d38ace554cadfc5fc)
![{\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (n)}}\left[B(x,r)\right]>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc73cfc4e16ce114e19abb95ae8f9a730408f04a)
![{\displaystyle {\mathsf {P}}^{\mathrm {SAT} [1]}={\mathsf {P}}^{\mathrm {SAT} [2]}\Rightarrow {\mathsf {PH}}\subseteq {\mathsf {NP}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d8cb3e8275ecee8473c27fa153879d889159b1d)