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.
Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.
Defined in [Vya03], where the following was also shown:
Kuperberg ([Kup09]) showed that A0PP = SBQP.
Literally, the class of ALL languages.
ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.
First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).
Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.
Nor is it hard to show that MAEXP/rpoly = ALL.
Also, per [Aar18], PDQP/qpoly = ALL.
On the other hand, even though PSPACE contains PP, and EXPSPACE contains MAEXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.
So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)
It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MAEXP/rpoly means M(AEXP/rpoly), while (MAEXP)/rpoly equals MAEXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.
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.)
The class of decision problems for which both "yes" and "no" answers can be verified by an AM protocol.
If EXP requires exponential time even for AM protocols, then AM ∩ coAM = NP ∩ coNP [GST03].
There exists an oracle relative to which AM ∩ coAM is not contained in PP [Ver95].
Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,
Defined in [Li93], where the following was also shown:
The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.
Contains FewP [Li93] and contains YQP*, YMA*, and YP* [Yir24].
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).
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 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].
[AD14] showed that BQP/qpoly = YQP/poly.
There exists an oracle relative to which BQP/qpoly does not contain NP [Aar04b].
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.
Does not contain PP unless CH collapses [Aar06],[Yir24].
Defined as follows:
The union of the CkP's is called the counting hierarchy, CH.
Defined in [Wag86].
See [Tor91] or [AW90] for more information.
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].
The class of decision problems solvable by a Turing machine in time . Note that some authors choose to call this class TIME.
Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function greater than , DTIME() is strictly contained in DTIME() [HS65]. As a corollary, P ⊂ EXP.
For any space constructible , DTIME() is strictly contained in DSPACE() [HPV77].
Also, DTIME() is strictly contained in NTIME() [PPS+83] (this result does not work for arbitrary ).
For any constructible superpolynomial , DTIME() with PP oracle is not in P/poly (see [All96]).
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.
FERT and FPERT are parameterized classes. FPERT is formally defined as the class of decision problems of the form (x, k1, k2), decidable in time f1(k1) * p(|x|) by a probabilistic Turing Machine such that
Here, f1 and f2 are arbitrary functions (f2 from the reals to <0,1/2]) and p is a polynomial.
Defined in [KW15]. Contains FERT and FPT and is contained in para-NPPP.
The class of decision problems that have PZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).
Contained in PP [BHCTV17].There is an oracle where it is not closed under complement [BHCTV17].
The class of decision problems solvable by an NP machine such that
Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)
Contains SPP.
Also, contains the graph isomorphism problem [KST92].
Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].
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].
Has the same relation to EXP as PP does to P.
Is not contained in P/poly [BFT98].
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.
Has the same relation to L that PP has to P.
Contains BPL and contained in DET [Coo85].
PLPL = PL (see [HO02]).
Also known as Θ2P.
The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).
Equals P||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
PNP[log] is contained in PP [BHW89].
Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for PNP[log] [HHR97].
Contains PNP[k] for all constants k.
A class inspired by the proverb, "if at first you don't succeed, try, try again."
Formally, the class of decision problems solvable by a BQP machine such that
Defined in [Aar05b], where it is also shown that PostBQP equals PP.
[Aar05b] also gives the following alternate characterizations of PostBQP (and therefore of PP):
Defined in [BFS86], PPcc is one of two ways to define a communication complexity analogue of PP. In PPcc, we note that in an algorithm that uses an amount of random bits bounded by , the bias between the accept and reject probabilities can be no smaller than . Thus, in PPcc, the communication complexity is defined as the sum of the traditional communication complexity (the number of exchanged bits) and the log of the reciprocal of the worst-case (smallest) bias.
The difference between this class and UPPcc is discussed further in [BVW07], where it is shown that PPcc ⊂ UPPcc.
The complexity measure corresponding to PPcc is equivalent to the "discrepancy bound" [Kla07].
See also: UPPcc.
If PP/poly = P/poly then PP is contained in P/poly. Indeed this is true with any syntactically defined class in place of PP. An implication is that any unrelativized separation of BQP/qpoly from BQP/mpoly would imply that PP does not have polynomial-size circuits.
A level of the counting hierarchy CH.
It is not known whether there exists an oracle relative to which PPP does not equal PSPACE.
Equals P#P (exercise for the visitor).
Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.
The class of decision problems solvable by a P machine, that can make O(log n) queries to a QMA oracle (where n is the length of the input).
Defined in [Amb14].
Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is PQMA[log]-complete.
Estimating local observables remains PQMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].
PQMA[log] is contained in PP [GY16].
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].
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.
Contained in DSPACE(f(n)2) [BCP83].
Equals PrHSPACE(f(n)) [Jun85].
The class of decision problems for which a "yes" answer can be verified by a public-coin quantum AM protocol, as follows. Arthur generates a uniformly random (classical) string and sends it to Merlin. Merlin responds with a polynomial-size quantum certificate, on which Arthur can perform any BQP operation. The completeness and soundness requirements are the same as for AM.
Defined by Marriott and Watrous [MW05].
Contains QMA and is contained in QIP[2] and BP•PP (and therefore PSPACE).
The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that
QMA = QIP(1).
Defined in [Wat00], where it is also shown that group non-membership is in QMA.
Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.
Kitaev and Watrous (unpublished) showed QMA is contained in PP (see [MW05] for a proof). Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.
Kitaev ([KSV02], see also [AN02]) showed that the 5-Local Hamiltonians Problem is QMA-complete. Subsequently, Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.
Compare to NQP.
If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A0PP.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.
Has the same relation to PL as SPP does to PP.
Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].
Contains UL.
Equals the set of problems low for GapL.
The class of decision problems solvable by an NP machine such that
We may additionally require that all paths make the same number of binary nondeterministic choices, but then the second condition has to be modified so that if the answer is "yes", the number of accepting and rejecting paths differ by 2. (If the total number of paths is even then the numbers can't differ by 1.)
Defined in [FFK94], where it was also shown that SPP is low for PP, C=P, ModkP, and SPP itself. (I.e. adding SPP as an oracle does not increase the power of these classes.)
Independently defined in [OH93], who called the class XP.
Contained in LWPP, C=P, and WPP among other classes.
Contains FewP; indeed, FewP is low for SPP, so that SPPFewP = SPP [FFK94].
Contains the problem of deciding whether a graph has any nontrivial automorphisms [KST92].
Indeed, contains graph isomorphism [AK02].
Contains a whole gaggle of problems for solvable black-box groups: solvability testing, membership testing, subgroup testing, normality testing, order verification, nilpotetence testing, group isomorphism, and group intersection [Vin04]
[AK02] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in FPSPP.
Defined by [BFS86], UPPcc is one of two communication complexity analogues of PP.UPPcc is the class of all functions that are computable by polylogarithmic protocols using private (but no public) randomness, which accept with probability strictly greater than 1/2 when and accept with probably strictly less than 1/2 otherwise. No accounting is made for how many random bits are consulted during the protocol.
Does not contain ⊕Pcc [For02].
The complexity measure associated with UPPcc is equivalent to the log of the sign-rank of the communication matrix (assuming the latter has {1,-1} entries) [PS86].
See also: PPcc.
The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,
Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.
The class of decision problems solvable by an NP machine such that
Defined in [FFK94].
Contained in C=P ∩ coC=P, as well as AWPP.
Is to YQP as YP* is to YP [AD14].
Is contained in APP, and so is low for PP [Yir24].
![{\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)
