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.
Has the same relation to #L as P/poly does to P.
Has the same relation to ⊕L as P/poly does to P.
The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.
Named in [Imp02], though it has been considered since the 1970's.
If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].
The class of decision problems solvable by an NP machine such that
(Here all computation paths have the same length.)
Often identified as the class of feasible problems for a computer with access to a genuine random-number source.
Defined in [Gil77].
Contained in Σ2P ∩ Π2P [Lau83], and indeed in ZPPNP [GZ97].
If BPP contains NP, then RP = NP [Ko82,Gil77] and PH is contained in BPP [Zac88].
If any problem in E requires circuits of size 2Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).
Contained in O2P since problems requiring exponential sized circuits can be verified in O2E [GLV24] [Li23] which can be used to derandomize [IW97].
Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].
BPP is not known to contain complete languages. [Sip82], [HH86] give oracles relative to which BPP has no complete languages.
There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].
In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(nc) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.
A zero-one law exists stating that BPP has p-measure zero unless BPP = EXP [Mel00].
Equals Almost-P.
See also: BPPpath.
The class of 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 a (nonuniform) family of Boolean circuits of size O(f(n)). Often denoted just SIZE(f(n)).
So for example, CSIZE(poly(n)) (the union of CSIZE(nk) over all k) equals P/poly.
Defined in [SM02] among other places.
A level of PH, the polynomial hierarchy.
One Δ2P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [Kre88]
Contains BH.
There exists an oracle relative to which Δ2P is not contained in PP [Bei94].
There exists another oracle relative to which Δ2P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].
There exists an oracle B for which BPPB is exponentially more powerful than Δ2PB [KV96].
If P = NP, then any polynomial-size circuit C can be learned in Δ2P with C oracle [Aar06].
The class of decision problems solvable by a Turing machine in time . Note that some authors choose to call this class TIME.
Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function greater than , DTIME() is strictly contained in DTIME() [HS65]. As a corollary, P ⊂ EXP.
For any space constructible , DTIME() is strictly contained in DSPACE() [HPV77].
Also, DTIME() is strictly contained in NTIME() [PPS+83] (this result does not work for arbitrary ).
For any constructible superpolynomial , DTIME() with PP oracle is not in P/poly (see [All96]).
Equals DSPACE(2O(n)).
If E = ESPACE then P = BPP [HY84].
Indeed if E has nonzero measure in ESPACE then P = BPP [Lut91].
ESPACE is not contained in P/poly [Kan82].
Is not contained in BQP/mpoly [NY03].
See also: EXPSPACE.
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 FNL as P/poly does to P.
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.
Has the same relation to L as P/poly does to P.
The subclass of MA such that for each input size n, there is a sparse set Sn that Merlin's proof string always belongs to (no matter what the input is).
Defined in [KST93], where it is also observed that if graph isomorphism is in P/poly, then the complement of graph isomorphism is in MA'.
The exponential-time analogue of MIP.
In the unrelativized world, equals NEEXP.
There exists an oracle relative to which MIPEXP equals the intersection of P/poly, PNP, and ⊕P [BFT98].
The class of decision problems solvable by a nonuniform family of polynomial-size Boolean circuits with only AND and OR gates, no NOT gates. (Or rather, following the definitions of [GS90], the entire input can be negated as long as there are no other negations.)
More straightforward to define than mP.
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].
Has the same relation to NL as P/poly does to P.
Is contained in ⊕L/poly [GW96], as well as SAC1.
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.
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.
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].
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.
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].
IP where only the input size is known during the interaction with the prover, and after that interaction, the verifier gets the specific input.
L is in OIP if there exists a randomized, polynomial time interrogator I which takes an input size and interacts with a prover to produce a witness, and polynomial time verifier V that takes an input and a witness so that
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 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 polynomial-time algorithm that outputs the wrong answer on only a sparse (that is, polynomially-bounded) set of instances.
Defined in [Yes83].
Contains Almost-P and is contained in P/poly [Sch86].
Has the same relation to EXP as PP does to P.
Is not contained in P/poly [BFT98].
If PP/poly = P/poly then PP is contained in P/poly. Indeed this is true with any syntactically defined class in place of PP. An implication is that any unrelativized separation of BQP/qpoly from BQP/mpoly would imply that PP does not have polynomial-size circuits.
Same as PromiseBPP, but for BQP instead of BPP.
If PromiseBQP = PromiseP then BQP/mpoly = P/poly.
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].
See TC for definition.
TC0 contains ACC0, and is contained in NC1.
TC0 circuits of depth 3 are strictly more powerful than TC0 circuits of depth 2 [HMP+93].
TC0 circuits of depth 3 and quasipolynomial size can simulate all of ACC0 [Yao90].
There is a function in AC0 (explicitly given in [She08]), whose computation with TC0 circuits of depth 2 requires an exponential number of gates.
[NR97] give a candidate pseudorandom function family computable in TC0, that is secure assuming a subexponential lower bound on the hardness of factoring. (See also [NRR01] for an improvement of this construction, as well as [Kha93].)
One implication is that, assuming such a bound, there is no natural proof in the sense of [RR97] separating TC0 from P/poly. (It is important for this that a function family, and not just a candidate pseudorandom generator, is computable in TC0.) Another implication is that functions in TC0 are likely to be difficult to learn.
The permanent of a 0-1 matrix cannot be computed in uniform TC0 [All99].
In a breakthrough result [Hes01] (building on [BCH86] and [CDL01]), integer division was shown to be in UD-uniform TC0. Indeed division is complete for this class under AC0 reductions.
Has the same relation to UL as P/poly does to P.
Equals NL/poly [RA00]. (A corollary is that UL/poly is closed under complement).
Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in BQP/mpoly) is a more natural definition, but this is a moot distinction here because [RA00] show that they both equal NL/poly.
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 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].
