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 intersection of NPC with {0,1}* (i.e. the set of binary strings).
Contains NP.
Is contained in PSPACE, and in AM assuming the Extended Riemann Hypothesis [Koi96].
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 decision problems solvable by an NP machine such that
Defined in [PZ83].
Contains Graph Isomorphism; indeed, Graph Isomorphism is low for ⊕P [AK02].
There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].
Equals Mod2^mP for every positive integer m.
Same as AC0, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)
If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC0[m] [Raz87] [Smo87]. It follows that, for any such m, AC0[m] is strictly contained in NC1.
However, if m is a product of distinct primes (e.g. 6), then it is not even known whether AC0[m] = NP!
See also: QAC0[m].
Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.
Contained in TC0.
Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].
According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.
There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].
The class of problems that are in NPA with probability 1, where A is an oracle chosen uniformly at random.
The class of problems that are in PSPACEA with probability 1, where A is an oracle chosen uniformly at random.
Almost-PSPACE is not known to equal PSPACE -- rather surprisingly, given the fact that PSPACE equals BPPSPACE and even PPSPACE.
What's known is that Almost-PSPACE = BPexp⋅PSPACE, where BPexp⋅ is like the BP⋅ operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXPNP ∩ coNEXPNP.
Whereas both BPexp⋅PSPACE and BPPSPACE machines are allowed exponentially many random bits, the former has a reusable record of all of these bits on a witness tape, while the latter can only preserve a fraction of them on the work tape.
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 solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,
Defined in [FFK94].
Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.
Basically has the same relation to W[SAT] as PSPACE does to NP.
The class of decision problems of the form (x,r,k1,...,kr) (r,k1,...,kr parameters), that are fixed-parameter reducible to the following problem, for some constant h:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contains AW[*], and is contained in AW[P].
Has the same relation to W[t] as PSPACE does to NP.
Same as AW[SAT], except that the formula F can have depth at most t.
Defined in [DF99].
Contained in AW[*].
[DFT98] show that for all t, AW[t] = AW[*].
βkP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(logkn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(logkn) that the answer is 'yes.'
Then βP is the union of βkP over all constant k.
Defined in [KF84]. See also the survey [GLM96].
There exist oracles relative to which basically any consistent inclusion structure among the βkP's can be realized [BG98].
β2P contains LOGNP and LOGSNP.
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.
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].
Equals AM.
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).
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 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].
The class of decision problems solvable by an NP machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'
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 #P function problems such that some underlying NP machine witnessing membership in #P has"clustered" accepting paths. That is:
Defined in [HHK+05].
A nondeterministic analog of CP. Defined in [SF98], which should be consulted for the definition (it has something to do with strange attractors, I think).
The authors raise the question of whether CP equals CNP.
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].
The class of decision problems L in NP such that, if the answer is "yes," then a proof can be constructed in polynomial time given access only to an oracle for L.
Contains NPC.
[BG94] show that compNP is contained in frIP, and that assuming NEE is not contained in BPEE, compNP does not equal NP.
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.
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.
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].
The class of pairs (A,B), where A and B are NP problems whose sets of "yes" instances are nonempty and disjoint.
If there exists an optimal propositional proof system, then DisNP has a complete pair [Raz94]. On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [GSS+03].
If P does not equal UP, then DisNP contains pairs not separated by any set in P [GS88]. On the other hand, there exists an oracle relative to which P does not equal NP but still DisNP does not contain any P-inseparable pairs [HS92].
(also called (NP,P-computable) or RNP)
A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.
(A,μ) is in DistNP if A is in NP, and μ is P-computable (meaning that its cumulative density function can be evaluated in polynomial time).
DistNP has complete problems [Lev86] (see also [Gur87]), although unlike for NP this is not immediate.
Any DistNP-complete problem is also complete for (NP,P-samplable) [IL90].
The class of decision problems solvable by a BQP machine with oracle access to a dynamical simulator. When given a polynomial-size quantum circuit, the simulator returns a sample from the distribution over "classical histories" induced by the circuit. The simulator can adversarially choose any history distribution that satisfies the axioms of "symmetry" and "locality" -- so that the DQP algorithm has to work for any distribution satisfying these axioms.
See [Aar05] for a full definition.
There it is also shown that SZK is contained in DQP.
Contains BQP, and is contained in EXP [Aar05].
There exists an oracle relative to which DQP does not contain NP [Aar05].
The class of decision problems solvable by a Turing machine in space O(f(n)).
The Space Hierarchy Theorem: For constructible f(n) greater than logn, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [HLS65].
For space constructible f(n), strictly contains DTIME(f(n)) [HPV77].
DSPACE(n) does not equal NP (though we have no idea if one contains the other)!
See also: NSPACE(f(n)).
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.
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].
The class of decision problems solvable by an NP machine such that
Contained in C=P, and in ModkP for any odd k. Contains UP.
Defined in [BHR00].
The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQPK. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.
Without loss of generality, the amplitudes in the gate set K are algebraic numbers [ADH97].
There is an oracle that separates EQP from NP [BV97], indeed from Δ2P [GP01]. There is also an oracle relative to which EQP is not in ModpP where p is prime [GV02]. On the other hand, EQP is in LWPP [FR98].
P||NP[2k] is contained in EQP||NP[k], where "||NP[k]" denotes k nonadaptive oracle queries to NP (queries that cannot depend on the results of previous queries) [BD99].
See also ZBQP.
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.
Contains NP and NISZK, and is contained in the third level of PH.
Equals the union of DTIME(2p(n)) over all polynomials p.
If EXP is in P/poly then EXP = MA [BFL91].
Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].
There exist oracles relative to which
[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.
[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MAPOLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.
[SU05] show that EXP NP/poly implies EXP P||NP/poly.
In descriptive complexity EXPTIME can be defined as SO() which is also SO(LFP)
Has the same relation to BPP as FNP does to NP. Equivalently, it is the randomised analogue of FP.
Has the same relation to BQP as FNP does to NP.
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
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 solvable by an NP machine such that
Also called FewPaths.
Defined in [CH89].
Contains FewP, and is contained in PFewP [Kob89] and in SPP [FFK94].
See also the survey [Tor90].
The class of decision problems solvable by an NEXP machine such that, given a "yes" instance, no more than an exponential number of computation paths accept.
Contained in MIP[NPFewEXP] (MIP where provers are not unbounded in computational power, but are limited to NPFewEXP) [AKS+94].
Alternatively, FewEXP can refer to the sparsity of accepting paths in a given instance. In [AKR+03], the authors show that the conjectures "FewEXP search instances are EXP-solvable" and "FewEXP decision instances are EXP/poly-solvable" are equivalent. That is, for all NEXP machines , the following conditions are equivalent:
The class of decision problems solvable by an NP machine such that
Defined in [AR88].
There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].
Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].
Contained in Few.
See also the survey [Tor90].
Has the same relation to NL as FNP does to NP.
Defined by [AJ93], who also showed that if NL = UL, then FNL is contained in #L.
The class of function problems of the following form:
FNP generalizes NP, which is defined in terms of decision problems only.
Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.
FP = FNP if and only if P = NP.
Contains TFNP.
A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.
Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)
However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.
FP = FNP if and only if P = NP.
If FPNP = FPNP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for PNP versus PNP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).
Given a graph, the problem of outputting the size of its maximum clique is complete for FPNP[log].
The class of problems for which the task is to output a quantum certificate for a QMA problem, when such a certificate exists. Thus, the desired output is a quantum state.
Defined in [JWB03], where it is also shown that state preparation for 3-local Hamiltonians is FQMA-complete. The authors also observe that, in contrast to the case of FNP versus NP, there is no obvious reduction of FQMA problems to QMA problems.
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 functions f(x) such that for some NP machine, f(x) is the number of accepting paths minus the number of rejecting paths.
Equivalently, the closure of the #P functions under subtraction.
Defined in [FFK94] and independently [Gup95].
The class of decision problems for which a "yes" answer can be verified by
For example, GC(p(n),P) = NP where p is a polynomial.
Defined in [CC93].
Umans [Uma98] has shown that given a DNF expression Φ, the Shortest Implicant problem is GC(log2n, coNP)-complete.
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 decision problems solvable by an NP machine such that
Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)
Contained in RP, EP, and ModkP for every odd k. Contained in EQP by the Deutsch-Jozsa algorithm.
Defined in [BB92], where it was called C==P[half] (C==P being an alternative name for WPP, that apparently didn't catch on or stick). The name used here is from [BS00]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.
Defined as HeurDTIME, but for non-deterministic heuristic algorithms.
NP is not contained in HeurNTIME() for any constants [Per07].
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.
The class of decision problems such that, for every n-bit string x, there exists a program A of size O(log n) that, given x as input, "correctly decides" the answer on x in time polynomial in n. This means:
Defined in [OKS+94]; see also [LV97].
If NP is contained in IC[log,poly], then P = NP [OKS+94]. Indeed, any self-reducible problem in IC[log,poly] is also in P.
Strictly contains P/log, and is strictly contained in P/poly.
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 class of decision problems expressible in logical form as
LOGNP0 is the subclass in which φ is a first-order predicate without quantifiers and x and y are bounded lists of indices of input bits. LOGNP is also the closure of LOGNP0 under polynomial-time many-one reductions.
The motivation is that the analogue of LOGNP0 without the logarithmic bound on |S| is SO-E, which by Fagin's theorem equals NP [Fag74].
Defined in [PY96], where it was also shown that the following problem is complete for LOGNP under many-one reductions:
Contains LOGSNP, and is contained in βP (indeed β2P).
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].
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 .
Has the same relation to NP as MaxSNP does to SNP.
Contains MaxPB.
The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].
A monoid is a set with an associative operation and an identity element (so it's like a group, except that it need not have inverses).
Then (Mk)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The ith computation path (under some lexicographic ordering) outputs an element mi of Mk. Then the machine accepts if and only if m1m2...ms is the identity (where s is the number of paths).
Defined by Hertrampf [Her97], who also showed the following (in the special case M is a group):
The class of decision problems for which a 'yes' answer can be verified in mP (that is, monotone polynomial-time). The monotonicity requirement applies only to the input bits, not to the bits that are guessed nondeterministically. So, in the corresponding circuit, one can have NOT gates so long as they depend only on the nondeterministic guess bits.
Defined in [GS90], where it was also shown that mNP is 'trivial': that is, it contains exactly the monotone problems in NP.
For any k>1: The class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."
Mod2P is more commonly known as ⊕P "parity-P."
For every k, ModkP contains graph isomorphism [AK02].
[Her90] and [BG92] showed that ModkP is the set of unions of languages in ModpP for each prime p that divides k. In particular, if p is prime, then ModpP = Modp^mP for all positive integers m. A further fact is that ModpP is closed under union, intersection, and complement, and low for itself, for p prime.
On the other hand, if k is not a prime power, then there exists an oracle relative to which ModkP is not closed under intersection or complement [BBR94].
For prime p, there exists an oracle relative to which ModpP does not contain EQP [GV02].
Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).
Contained in NEXP.
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].
NL is to L as NP is to P. Not known whether a particular relation (equality or inequality) between P and NP implies the same relation between L and NL.
In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)
Is contained in LOGCFL [Sud78], as well as NC2.
Is contained in UL/poly [RA00].
Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].
NL can be defined in a logical formalism as SO(krom) and also as FO(tc), reachability in directed graph is NL-Complete under FO-reduction.
Has the same relation to LIN as NP does to P.
The class of decision problems such that (1) they're in NP and (2) every problem in NP is reducible to them (under some notion of reduction). In other words, the hardest problems in NP.
Two notions of reduction from problem A to problem B are usually considered:
Some examples of NP-complete problems are discussed under the entry for NP.
The classic reference on NPC is [GJ79].
Unless P = NP, NPC does not contain any sparse problems: that is, problems such that the number of 'yes' instances of size n is upper-bounded by a polynomial in n [Mah82].
A famous conjecture [BH77] asserts that all NP-complete problems are polynomial-time isomorphic -- i.e. between any two problems, there is a one-to-one and onto Karp reduction. If that's true, the NP-complete problems could be interpreted as mere "relabelings" of one another.
NP-complete problems are p-superterse unless P = NP [BKS95]. This means that, given k Boolean formulas F1,...,Fk, if you can rule out even one of the 2k possibilities in polynomial time (e.g., "if F1,...,Fk-1 are all unsatisfiable then Fk is satisfiable"), then P = NP.
An analog of NP for Turing machines over a complex number field.
Defined in [BCS+97].
It is unknown whether PC = NPC, nor are implications known among this question, PR versus NPR, and P versus NP.
However, [CKK+95] show that if P/poly does not equal NP/poly then PC does not equal NPC.
[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {nk} of positive integers, t(nk k!) grows faster than polylogarithmically in k, then PC does not equal NPC.
See also VNPk.
The analogue of Pcc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.
Does not equal Pcc or coNPcc because of the EQUALITY problem. Also, does not contain BPPcc because of that problem.
Is not contained in BPPcc (first shown by [BFS86]).
SET-INTERSECTION, in which Alice's and Bob's strings are identified with characteristic vectors of sets and yes-inputs are intersecting while no-inputs are disjoint, is the canonical NPcc-complete problem. Sometimes SET-DISJOINTNESS also refers to this problem, but sometimes it refers to the complement of this problem.
The complexity measure corresponding to NPcc is equivalent to the log of the number of rectangles needed to cover exactly the set of 1-entries of the communication matrix.
Has the same relation to NPcc and NP as Pcc does to Pcc and P.
NPcc is not contained in BPPcc for players, for any constant . As a result, NPcc is not equal to RPcc under the same conditions [DP08].
Sometimes used to denote the set of decision problems in NP that are neither NP-complete (that is, in NPC) nor in P.
Is thought to contain (for example) decision versions of factoring and graph isomorphism.
Is nonempty if P does not equal NP [Lad75]. Indeed, under this assumption, it contains an infinite number of distinct polynomial-time equivalence classes.
The class of problems in both NP and coNP.
Contains graph isomorphism under the assumption 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.)
Equals PNP ∩ coNP [Bra79]. In particular, if a problem in NP ∩ coNP is NP-hard with Turing reduction, then NP = coNP.
Is not believed to contain complete problems.
Is equal to Low(NP)={L : NPL=NP} [Sch83].
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].
Same as NP/poly, except that now the advice string is logarithmic-size.
Shown in [FK05] that EXP ⊆ NP/log if and only if EXP = P||NP.
The class of all (possibly partial, possibly multivalued) functions computed by an NP machine as follows: ignore the rejecting paths, and consider any output of an accepting path to be "one of the outputs."
Defined in [BLS84].
Contrast with FNP.
The class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."
Defined in [ACG+99].
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].
See AvgP for basic notions of average-case complexity.
(NP,P-samplable) is the same as DistNP, except that the distribution μ only needs to be samplable in polynomial time. μ's cumulative density function does not need to be computable in polynomial time.
Any problem complete for DistNP is also complete for (NP,P-samplable) [IL90].
An analog of NP for Turing machines over a real number field.
Defined in [BCS+97].
It is unknown whether PR = NPR, nor are implications known among this question, PC versus NPC, and P versus NP.
Also, in contrast to the case of NPC, it is an open problem to show that P/poly distinct from NP/poly implies PR distinct from NPR. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.
See also VNPk.
The class of NPMV functions that are single-valued (i.e., such that every accepting path outputs the same value).
Defined in [BLS84].
Contains NPSVt.
P = NP if and only if FP = NPSV.
Same as NP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.
The Nondeterministic Time Hierarchy Theorem: If f and g are time-constructible and f(n+1)=o(g), then NTIME(f(n)) does not equal NTIME(g(n)) [SFM78] (this is actually stronger than the hierarchy theorem for DTIME).
NTIME(n) strictly contains DTIME(n) [PPS+83] (this result does not work for arbitrary f(n)).
For any constructible superpolynomial f, NTIME(f(n)) with NP oracle is not in P/poly [Kan82].
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 of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of NP.
L is in ONP if there exists a polynomial time verifier V taking an input and a witness, so that:
Defined in [FSW09], where it was shown NP has size nk circuits for some constant k if and only if ONP/1 has size nj circuits for some constant j.
ONP is contained in P/poly and NP [FSW09].
ONP = NP iff NP is in P/poly [FSW09].
If NE is not E then ONP is not P [GM15].
See also YP for an input oblivious analogue of NP ∩ coNP.
The class of functions computable by taking the maximum (or minimum) of the output values over all accepting paths of an NP machine. OptP[f(n)] restricts the size of the output to f(n) bits.
Defined in [Kre88].
Contrast with FNP.
MaxSat that returns the number of satisfied clauses, Clicque that returns the size of the clique, Chromatic Number are OptP[log n]-complete.
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 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].
Same as P/poly, except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.
Strictly contained in IC[log,poly].
If NP is contained in P/log then P = NP.
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.
The class of decision problems such that a "yes" answer can be verified by a probabilistically checkable proof, as follows.
The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a proof (which might be exponentially long), but can query only O(q(n)) bits of the proof.
Then we require the following:
Defined in [AS98].
By definition NP = PCP(0,poly(n)).
MIP = PCP(poly(n),poly(n)).
PCP(r(n),q(n)) is contained in NTIME(2O(r(n))q(n) + poly(n)).
NP = PCP(log n, log n) [AS98].
In fact, NP = PCP(log n, 1) [ALM+98]!
On the other hand, if NP is contained in PCP(o(log n), o(log n)), then P = NP [FGL+91].
Also, even though there exists an oracle relative to which NP = EXP [Hel84], if we could show there exists an oracle relative to which PCP(log n, 1) = EXP, then we'd have proved P not equal to NP [For94].
Another weird oracle fact: since NP does not equal NEXP [SFM78], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [HCC+92].
The class of decision problems solvable in time O(t(n)) by a nondeterministic Turing machine, as follows. The machine is given oracle access to a proof string of unbounded length.
Credited in [For94] to S. Arora, R. Impagliazzo, and U. Vazirani.
An interesting question is whether NP = PFCHK(log n) relative to all possible oracles. Fortnow [For94] observes that the answer depends on what oracle access mechanism is used.
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.
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].
See Δ2P.
Equals PNP[log] ([BH91] and [Hem89] independently).
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).
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.
Same as PNP[log], except that now log2 queries can be made.
The model-checking problem for a certain temporal logic is PNP[log^2]-complete [Sch03].
For all k ≥ 1, P with logk adaptive queries to NP coincides with P with logk−1 rounds of (polynomially many) nonadaptive queries [CS92].
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 promise problems solvable by an UP machine. I.e., the nondeterministic machine must have a unique accepting path for "yes" inputs, and no accepting paths "no" inputs, but could have any number of accepting paths for inputs that do not satisfy the promise.
Although not originally stated with this notation, the main result of [VV86] is that NP is contained in RPPromiseUP.
The class of decision problems for which there's a polynomial-time algorithm with the following property. Whenever it's given two instances, a "yes" and a "no" instance, the algorithm can always decide which is the "yes" instance.
Defined in [Sel79], where it was also shown that if NP is contained in P-Sel then P = NP.
There exist P-selective sets that are not recursive (i.e. not in R).
QHk is defined to be PNP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QHk over all nonnegative k.
QH = BH [Wag88]; thus, either both hierarchies are infinite or both collapse to some finite level.
The class of problems in NP whose witnesses are in FBQP. For example, the set of square-free numbers is in coRBQP using only the fact that factoring is in FBQP. (Even without a proof that the factors are prime, the factorization proves that there is a square divisor.)
Contains RP and ZBQP, and is contained in BQP and RQP. Defined here to clarify EQP; see also ZBQP.
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 (x,m) (where x is an input of length |x|=n and m is an integer parameter), that are solvable by a nondeterministic (i.e. NP) machine in poly(n+m) time and O(m+log n) space simultaneously.
Defined in [Mon80].
See also FPT.
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].
The union of NE, NPNE, NPNP^NE, and so on.
Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.
Note that we would get the same class if we replaced NE by NEXP.
There exists an oracle relative to which SEH is not contained in EH [Hem89].EH and SEH are incomparable for all anyone knows.
The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.
Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.
They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.
See also: PermUP.
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.)
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].
[Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic.
Then SNP is the class of decision problems reducible to a graph-theoretic predicate with only universal quantifiers over vertices, no existential quantifiers. As an example, k-SAT (CNF satisfiability with at most k literals per clause, for k a constant) is in SNP. But general SAT is not in SNP, basically because we're not allowed to say, "There exists a literal in this clause that satisfies the clause."
Contains MMSNP.
See also: MaxSNP.
We define second-order variable has got an arity and represent any proposition of arity . They are usually written in upper-case.
Second order logic is the set of FO formulae where we add quantification over second-order variables.
Every formuale is equivalent to a formulae in prenex normal form, where we first write quantification on variable on second order and then a FO-formulae in prenex normal form.
In Descriptive complexity we can see that SO is equal to PH, more precisely we have that formulae in prenex normal form where existential and universal of second order alternate times are the th level of the polynomial hierarchy.
This means that SO with only existential second-order quantification is equal to which is NP, and with only universal quantification is equal to which is Co-NP.
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NL machine.
Defined in [AJ93], where it is also shown that span-L is a hard class in the sense that span-L is contained in FP if and only if FP = #P.
Span-L is contained in #P, and if span-L = #P, then NL = NP [AJ93].
Span-L is contained in FPRAS [ACJ+21].
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.
Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.
The class of decision problems for which the number of 'yes' instances of size n is upper-bounded by a polynomial in n. If SPARSE intersects NPC then P = NP [Mah82].
Contains TALLY.
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.
The class of decision problems for which every 'yes' instance has the form 0n (i.e. inputs are encoded in unary). If TALLY intersects NPC then P = NP [Mah82].
Contained in SPARSE.
The class of function problems of the following form:
Can be considered as the functional analogue of NP ∩ coNP. Defined in [MP91].
Contained in FNP.
Subclasses include PPA, PPP, and PLS.
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 decision problems solvable by an NP machine such that
Defined by [Val76].
"Worst-case" one-way functions exist if and only if P does not equal UP ([GS88] and independently [Ko85]). "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [HT03]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.
There exists an oracle relative to which P is strictly contained in UP is strictly contained in NP [Rac82]; indeed, these classes are distinct with probability 1 relative to a random oracle [Bei89].
NP is contained in RPPromiseUP [VV86]. On the other hand, [BBF98] give an oracle relative to which P = UP but still P does not equal NP.
UP is not known or believed to contain complete problems. [Sip82], [HH86] give oracles relative to which UP has no complete problems.
The all-American counting class.
The class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.
In contrast to UP, a machine can legally have more than one accepting path - that just means that the corresponding input is not in the language.
Defined in [BG82].
Contains coNP.
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.
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:
A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.
Contains FPT.
Defined in [DF99], where the following is also shown:
W[1] can be generalized to W[t].
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.
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.
Same as ZPP, but with O(f(n))-time instead of polynomial-time.
For any constructible superpolynomial f, ZPTIME(f(n)) with NP oracle is not contained in P/poly [KW98].
![{\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)
