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.
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].
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.
The analog of PH in computability theory.
Let Δ0 = Σ0 = Π0 = R. Then for i>0, let
Then AH is the union of these classes for all nonnegative constant i.
Each level of AH strictly contains the levels below it.
An equivalent definition is: is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and . A bounded quantifier is of the form or where is considered to be free in . Then is the sets of number validating a formula of the form with . The set Πi is the set of formula who are negation of formula. And Δi = Σi ∩ Πi.
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.)
Same as AM, except that we allow polylog(n) rounds of interaction between Arthur and Merlin instead of a constant number.
Not much is known about AM[polylog] -- for example, whether it sits in PH. However, [SS04] show that if AM[polylog] contains coNP, then EH collapses to S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)
The class of decision problems such that for some #P function f(x,0m),
Defined in [GKR+95].
Contains PH and ModPH. Contained in MP.
Similar to TreeBQP except that the quantum computer's state at each time step is restricted to being exponentially close to a state in AmpP (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).
Defined in [Aar03b], where it was also observed that AmpP-BQP is contained in the third level of PH, just as TreeBQP is.
The smallest class that contains NP and is closed under union, intersection, and complement.
The levels are defined as follows:
Then BH is the union over all i of BHi.
Defined in [WW85].
For more detail see [CGH+88].
Contained in Δ2P and indeed in PNP[log].
If BH collapses at any level, then PH collapses to Σ3P [Kad88].
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.
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].
If NP is contained in coNP/poly then PH collapses to S2PNP [CCH+01].
| NPNP^NP^(coNP/poly ∩ NP) = NPNP^NP [HNO+96] |
Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.
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].
Not to be confused with DistPH, as in DistNP.
A middle-ground between classical and quantum proofs. Provers send (independent) probability distributions, or mixed states. After all proofs are sent, the verifier draws one sample from each proof.
If the proofs are allowed to be correlated, then the hierarchy collapses to just two levels as for QEPH.
Defined in [GY24] and shown to collapse to the standard definition of PH.
Has roughly the same relationship to E as PH does to P.
More formally, EH is defined as the union of E, NE, NENP, NE with Σ2P oracle, and so on.
See [Har87] for more information.
If coNP is contained in AM[polylog], then EH collapses to S2-EXP•PNP [SS04] and indeed AMEXP [PV04].
On the other hand, coNE is contained in NE/poly, so perhaps it wouldn't be so surprising if NE collapses.
There exists an oracle relative to which EH does not contain SEH [Hem89]. EH and SEH are incomparable for all anyone knows.
An extension of LkP.
The class of problems A such that ΣkPA is contained in Σk-1PA,NP.
Defined in [BBS86].
Contains NP and NISZK, and is contained in the third level of PH.
Can be defined as the class of problems polynomial-time Turing reducible to the Graph Isomorphism problem.
Contains GA and is contained in Δ2P.
The Graph Isomorphism problem itself (as opposed to the set of problems Turing reducible to Graph Isomorphism) is contained in NP as well as coAM (and indeed SZK). So in particular, if Graph Isomorphism is NP-complete, then PH collapses.
Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the Wikipedia page. While many of these are GI for a restricted class of graphs, some surprising GI-complete problems are: isomorphism of finite automata, isomorphism of commutative class 3 nilpotent semigroups, isomorphism of algebras over a field whose radical squares to zero and whose radical quotient is abelian [Gri83], and isomorphism of context-free grammars (for all of these and further references see [ZKT85]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [Gro12].
See [KST93] for much more information about GI.
The class of problems A in NP such that ΣkPA = Σk+1P; that is, adding A as an oracle increases the power of the kth level of the polynomial hierarchy by a maximum amount.
For all k, Hk is contained in Hk+1.
H0 consists exactly of the problems complete for NP under Cook reductions.
H1 consists exactly of the problems complete for NP under strong non-deterministic Turing reductions [Sch83].
Defined in [Sch83].
See also LkP.
High order logic is an extension of Second order, First order where we add quantification over higher order variables.
We define a relation of order and arity to be a subset of -tuple of relation of order and arity . When it is by extension a first order variable. "The quantification of formula in HO is over a given order (which is a straightforward extension of SO where we add quantification over constants (first-order variables) and relations (second-order variables)). The atomic predicates now can be general application of relations of order and arity to relations of order and arity and test of equality between two relations of the same order and arity.
is the set of formulae with quantification up to order O. (resp. ) is defined as the set of formula in beginning by an existential (resp universal) quantifier followed by at most alternation of quantifiers.
This class was defined in [HT06], and it was proved that where is the th level of the polynomial hierarchy.
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].
The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.
The class of problems A such that ΣkPA = ΣkP; that is, adding A as an oracle does not increase the power of the kth level of the polynomial hierarchy.
L1P = NP ∩ coNP.
For all k, Lk is contained in Lk+1 and in NP.
Defined in [Sch83].
See also HkP.
The closure of P under the ∃, ∀, and Modk operators. Equivalently, the smallest class C such that NPC, coNPC, and ModkPC are included in C for each k. Introduced in [GKR+95].
Contains PH and ModkP for each k. Contained in, and low for, AmpMP and MP.
For a fixed m, the restriction of the class that only allows Modk for k = m is denoted ModPHm [Buss17]. Toda’s theorem [Tod89] implies that for prime m, ModPHm = BP·ModmP.
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.
Together with NP/poly ∩ coNP/poly, has the same relation to NP ∩ coNP as P/poly has to P. A language in (NP ∩ coNP)/poly is defined by a single language in NP ∩ coNP which is then modified by advice. A language in NP/poly ∩ coNP/poly comes from two possibly different languages in NP and coNP which become the same with good advice.
There is an oracle relative to which NP/poly ∩ coNP/poly, indeed NP/1 ∩ coNP/1, is not contained in (NP ∩ coNP)/poly [FFK+93]. Recently they improved this to NP/1 ∩ coNP [FF..].
If NP is contained in (NP ∩ coNP)/poly, then PH collapses to S2PNP ∩ coNP [CCH+01].
Has the same relation to NP as P/poly does to P.
Contains AM. On the other hand, if NP/poly contains coNP then PH collapses to the third level.
NP/poly-natural proofs cannot show that circuit families are outside P/poly, under a pseudorandomness assumption [Rud97].
The class of decision problems for which there is a polynomial-time predicate P such that, for each length n, there exists y* and z* of length poly(n) such that for all x of length n
Note that this differs from S2P in that the witnesses in each case must only depend on the length of the input, and not on the input itself. In particular, since the conditions imply that the answer is 'yes' iff P(x,y*,z*), the class O2P is included in P/poly.
Less formally, O2P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee, and furthermore, there is a single winning move the prover can make that works for all x of length n that are yes-instances, and there is a single winning move the disprover can make that works for all x of length n that are no-instances.
Defined in [CR06], where it was shown (among other properties) that O2P is self-low, and that the Karp–Lipton collapse goes all the way down to O2P: if NP is contained in P/poly then PH = O2P.
Contains ONP and coONP [GM15].
It follows [GLV24] from results of [Li23] that for each k, O2P contains a language that has circuit complexity at least nk. (Previously, this was known for NP ∪ O2P based on [CR06].)
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.
I decided this class is so important that it deserves an entry of its own, apart from #P.
Contains PH [Tod89], and is contained in CH and in PSPACE.
Equals PPP (exercise for the visitor).
Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].
The polynomial hierarchy for communication complexity, naturally built with NPcc and coNPcc forming the first level. Specifically, a cost-k protocol in the PHcc model corresponds to a constant-depth 2k-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.
It is unknown whether Σ2cc equals Π2cc.
Defined in [BFS86], where it was also shown (among other things) that BPPcc is contained in Σ2cc ∩ Π2cc.
Complement of Σ2P.
Along with Σ2P, comprises the second level of PH, the polynomial hierarchy. For any fixed k, there is a problem in Π2P ∩ Σ2P that cannot be solved by circuits of size nk [Kan82].
Equals P with 2k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
If PNP[1] = PNP[2], then PNP[1] = PNP[log] and indeed PH collapses to Δ3P (attributed in [Har87b] to J. Kadin).
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.
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 Turing machine in polynomial space.
Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].
Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].
Contains P#P (P with a #P oracle).
A canonical PSPACE-complete problem is QBF.
Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.
Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).
A bounded-error quantum generalization of PH in which all proofs are classical, and the verifier is a quantum circuit.
Defined in [GSSSY18].
Contained in PPPPP [GSSSY18].
Like QPH, but the provers may entangle their earlier proofs with their later proofs.
Defined in [GY24], and was shown to collapse to QRG(1).
The hierarchy collapses even with a polynomial number of rounds, whereas PH with polynomial rounds equals 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.
A bounded-error quantum generalization of PH in which all proofs are un-entangled mixed quantum states, and the verifier is a quantum circuit. Note the utilization of mixed states is non-trivial, due to the presence of alternating quantifiers.
Defined in [GSSSY18].
Contains QMA(2).
Its second and third levels, QΣ2 and QΣ3, are contained in EXP and NEXP, respectively [GSSSY18].
In contrast to PH, it is open whether QΣ2=QΠ2 collapses QPH to its second level.
The class of decision problems for which there is a polynomial-time predicate P such that, on input x,
Note that this differs from Σ2P in that the quantifiers in the second condition are reversed.
Less formally, S2P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee. In Σ2P, the prover moves first.
Defined in [RS98], where it was also shown that S2P contains MA and Δ2P. Defined independently in [Can96].
Contains (and contrast with) O2P. If NP is contained in P/poly then PH = S2P (attributed to Sengupta in [Cai01]), and even is equal to O2P [CR06].
Contains languages whose complements are in Π2P.
Along with Π2P, comprises the second level of PH, the polynomial hierarchy.
Note that this is equal to NP with a coNP oracle.
[Uma98] has shown that the following problems are complete for Σ2P:
The problem of deciding if a perfect graph is 2-clique-colorable (defined in [FMF16]) has been shown to be complete for Σ2P.
For any fixed k, there is a problem in Σ2P ∩ Π2P that cannot be solved by circuits of size nk [Kan82].
The class of problems that are polynomial-time Turing reducible to Tensor Isomorphism. Defined in [GQ19]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).
Over any field F, contains GI. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in NP as well as coAM (and indeed SZK; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is NP-complete, then PH collapses.
Many natural problems are TI-complete, such as isomorphism of d-tensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo-)isometry of alternating matrix spaces, isomorphism of matrix p-groups of class 2 and exponent p, and equivalence of cubic forms [GQ19]. This was extended to include p-groups of class c<p and exponent p [GQ21]. Analogous classes were also defined under other group actions such as unitary, orthogonal, and symplectic groups [CGQ+24].
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.
A superclass of VPk in Valiant's algebraic complexity theory, but not quite the analogue of NP.
A problem is in VNPk if there exists a polynomial p with the following properties:
Originated in [Val79b].
If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNPk-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).
A central conjecture is that for all k, VPk is not equal to VNPk. Bürgisser [Bur00] shows that if this were false then:
In both cases, PH collapses to Σ2P.
![{\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)
![{\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)
