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].
Has the same relation to L as #P does to P.
#L is contained in the function class version of DET [AJ93]. In fact, the determinant is GapL-complete (see refs at GapL), where GapL consists of functions that are the difference of two #L functions.
Has the same relation to #L as P/poly does to P.
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].
Has the same relation to L as ⊕P does to P.
Solving a linear system over Z2 is complete for ⊕L [Dam90].
The problem of simulating stabilizer circuits is complete for ⊕L [AG04].
Has the same relation to ⊕L as P/poly does to P.
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 AP, but for logarithmic-space instead of polynomial-time.
The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.
Named in [Imp02], though it has been considered since the 1970's.
If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].
The class of problems that are in PA with probability 1, where A is an oracle chosen uniformly at random.
An alternating Turing machine is a nondeterministic machine with two kinds of states, AND states and OR states. It accepts if and only if the tree of all computation paths, considered as an AND-OR tree, evaluates to 1. (Here 'Accept' corresponds to 1 and 'Reject' to 0.)
Then AP is the class of decision problems solvable in polynomial time by an alternating Turing machine.
The abbreviation AP is also used for Approximable in Polynomial Time, see AxP.
Equivalent to NAuxPDAp without the running-time restriction.
Has the same relation to E as AvgP does to P.
Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.
The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.
Defined by [KRC00], who also show the following:
AxPP is recursively enumerable [Jeř07].
Has the same relation to E as BPP does to P.
EE = BPE if and only if EXP = BPP [IKW01].
Has the same relation to EE as BPP does to P.
Has the same relation to L as BPP does to P. The Turing machine has to halt for every input and every randomness.
The randomness is read once. That is, each random bit is only given once and to be referenced again it must be stored in the working space. This in contrast to the two way randomness of BP•L.
Contained in SC [Nis92], PL, BP•L, ZP•L [Nis93], DET [Coo85], NC2 and P [BCP83].
Languages decided with two sided bounded error by a log space machine with a read only tape containing random bits. In contrast with BPL, the random bits can be read multiple times without storing them in working space.
For example, BP•L contains RNC1 since NC1 is contained in L. However, this reduction does not hold for BPL.
It is unknown if BP•L is contained in P [Nis93].
Contained in BPP.
The 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.
Has the same relation to BPPcc and BPP as Pcc does to Pcc and P.
NPcc is not contained in BPPcc for players, for any constant [DP08].
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].
Same as BQP/mpoly, except that the machine only gets to make nonadaptive queries to whatever oracle it might have.
Defined in [NY03b], where it was also shown that P is not contained in BQPtt/poly relative to an oracle.
Has the same relation to L as C=P does to P.
C=LC=L = LC=L [ABO99].
A comparator gate consists of two inputs and outputs the minimum of its two inputs on its first output wire and outputs the maximum of its two inputs on its second output wire. One important restriction is that each output of a comparator gate has fanout at most one. The Comparator Circuit Value Problem (CCVP) is defined as following. Given a circuit composed of comparator gates, the inputs to the circuit, and one output of the circuit, calculate the value of this output.
CC is defined as the class of problems log-space many-one reducible to CCVP [MS89]. At present it is only known that NLCCP [MS89]. CC is an example of a complexity class neither known to be in NC nor P-complete.
Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lex-first Maximal Matching [Sub94].
Defined as follows:
The union of the CkP's is called the counting hierarchy, CH.
Defined in [Wag86].
See [Tor91] or [AW90] for more information.
If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.
If NP does not equal coNP, then P does not equal NP. But the other direction is not known.
See also: NP ∩ coNP.
Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP#P. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then EH collapses to the third level [SS04].
Co-NP is equal to SO-A, the second-order queries where the second-order quantifiers are only universals.
Same as CLOG, except that the convergence time can be polynomial rather than logarithmic in the input size.
Defined in [BSF02] and [SF98].
Finding a maximum flow, which is P-complete, can be done in CP [BSF02]. Based on this the authors argue that "P is contained in CP," but this seems hard to formalize, since CP is not a complexity class in the usual sense. They also conjecture that "CP is contained in P" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.
Contained in CNP.
A level of PH, the polynomial hierarchy.
One Δ2P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [Kre88]
Contains BH.
There exists an oracle relative to which Δ2P is not contained in PP [Bei94].
There exists another oracle relative to which Δ2P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].
There exists an oracle B for which BPPB is exponentially more powerful than Δ2PB [KV96].
If P = NP, then any polynomial-size circuit C can be learned in Δ2P with C oracle [Aar06].
Same as BPP, except that the random bit source is biased as follows. Each bit could depend on all the previous bits in arbitrarily complicated ways; the only promise is that the bit is 1 with probability in the range [δ,1-δ], conditioned on all previous bits.
So clearly 0-BPP = P and 1/2-BPP = BPP.
It turns out that, for any δ>0, δ-BPP = BPP [VV85], [Zuc91].
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 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 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.
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.
Equals DSPACE(2O(n)).
If E = ESPACE then P = BPP [HY84].
Indeed if E has nonzero measure in ESPACE then P = BPP [Lut91].
ESPACE is not contained in P/poly [Kan82].
Is not contained in BQP/mpoly [NY03].
See also: EXPSPACE.
The class of problems for which there exists a BPP machine M such that, for all inputs x,
Alternatively defined as NPBPP.
Contains NP and BPP, and is contained in MA and SBP.
∃BPP seems obviously equal to MA, yet [FFK+93] constructed an oracle relative to which they're unequal! Here is the difference: if the answer is "yes," MA requires only that there exist a y such that for at least 2/3 of random strings r, M(x,y,r) accepts (where M is a P predicate). For all other y's, the proportion of r's such that M(x,y,r) accepts can be arbitrary (say, 1/2). For ∃BPP, by contrast, the probability that M(x,y) accepts must always be either at most 1/3 or at least 2/3, for all y's.
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)
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 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].
FHk is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis. (Conditional phase flip gates are fine, for example.) Thus
It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FHk is strictly contained in FHk+1).
Defined in [Shi03].
Has the same relation to FNL as P/poly does to P.
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.
Let be a function from integers to integers. abbreviates and abbreviates .
A quantifier block is a list where the s are quantifier free FO-formulae and each s is either or .If is a quantifier block then is the block consisting of iterated copies of . Note that there are quantifiers in the list, but only k variables; each variable is used times.
FO[] consists of the FO-formulae with quantifier blocks that are iterated times.
In Descriptive complexity we can see that :
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]).
Has the same relation to FPT as RP does to P.
Defined in [AR01], where it was shown that, if the Resolution proof system is automatizable (that is, if a refutation can always be found in time polynomial in the length of the shortest refutation), then W[P] is contained in FPR.
Can be defined as the class of problems polynomial-time Turing reducible to the Graph Automorphism problem.
Contains P and is contained in GI.
See [KST93] for much more information about GA.
The class of problems decidable by an O(f(n))-space Turing machine with two kinds of quantifiers: existential and randomized.
Contains NSPACE(f(n)) and BPSPACE(f(n)), and is contained in AUC-SPACE(f(n)).
By linear programming, GAN-SPACE(log n) is contained in P.
Has the same relation to L as GapP does to P. (And therefore, has the same relation to #L as GapP does to #P.)
The determinant is GapL-complete [Vin91] [Dam91] [Tod91] ([MV97] also gave a new, self-contained proof). See also the corresponding decision class DET
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.
The class of languages generated by context-sensitive grammars in which the right-hand side of each transformation is either strictly longer than the left-hand side or the left-hand side consists of the start symbol.
Defined in [DW86] and shown to be contained in LOGCFL (and therefore in P among others).
Shown to be equivalent to Acyclic CSL in [Nie02].
The class of distributional problems solvable by a P machine. Defined in [Imp95], though he calls the class HP.
Alternately, [BT06] define HeurP as being the set of tuples , where is a language and is a distribution of problem instances, such that there exists an algorithm satisfying two properties, for every :
The class of distributional problems solvable by a PP machine. Defined in [Ill95], though he calls the class HPP.
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 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 expressible in logical form as
LOGSNP0 is the subclass in which φ is a first-order predicate without quantifiers and x is a bounded lists of indices of input bits. LOGSNP is also the closure of LOGSNP0 under polynomial-time many-one reductions. See LOGNP and SNP for the motivation.
Defined in [PY96].
Contained in LOGNP, and therefore QPLIN.
If P = LOGSNP, then for every constructible f(n) > n, NTIME(f(n)) is contained in DTIME(g(n)sqrt(g(n))), where g(n) = O(f(n) logf(n)) [FK97].
Has the same relation to L as P/poly does to P.
Has the same relation to L as ModkP does to P.
For any prime k, ModkL contains SL [KW93].
For any prime k, ModkLModkL = ModkL [HRV00].
For any k>1, contains LogFew [BDH+92].
The definition of this class, due to [GS90], is not obvious. First, a monotone nondeterministic Turing machine is one such that, whenever it can make a transition with a 0 on its input tape, it can also make that same transition with a 1 on its input tape. (This restriction does not apply to the work tape.) A monotone alternating Turing machine is subject to the restriction that it can only reference an input bit x by, "there exists a z at most x," or "for all z at least x."
Then applying the result of [CKS81] that P = AL, mP is defined to be mAL: the class of decision problems solvable by a monotone alternating log-space Turing machine.
Actually there's a caveat: A monotone Turing machine or circuit can first negate the entire input, then perform a monotone computation. That way it becomes meaningful to talk about whether a monotone complexity class is closed under complement.
Strictly contained in mNP [Raz85].
Deciding whether a bipartite graph has a perfect matching, despite being both a monotone problem and in P, requires monotone circuits of superpolynomial size [Raz85b]. Letting MONO be the class of monotone problems, it follows that mP is strictly contained in MONO ∩ P.
See also: mNC1, mL, mNL, mcoNL.
The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
Defined in [GKR+95].
Contains AmpMP, and ModPH, which is low for both AmpMP and MP. Contained in P#P[1].
MP with ModP oracle equals MP with #P oracle [KT96].
By definition, a decision problem in NC0 can depend on only a constant number of bits of the input. Thus, NC0 usually refers to functions computable by constant-depth, bounded-fanin circuits.
There is a family of permutations computable by a uniform family of NC0 circuits that is P-hard to invert [Has88].
Recently [AIK04] solved a longstanding open problem by showing that there exist pseudorandom generators and one-way functions in NC0, based on (for example) the hardness of factoring. Specifically, in these generators every bit of the output depends on only 4 input bits. Whether the dependence can be reduced to 3 bits under the same cryptographic assumptions is open, but [AIK04] have some partial results in this direction. It is known that the dependence cannot be reduced to 2 bits.
Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).
Contained in NEXP.
The set of languages L such that for every k, there is a language L_k in P that differs from L on at most 2n/nk inputs of length n. Discussed in [NS05] and implicitly defined in [Yam99].
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 NL as P/poly does to P.
Is contained in ⊕L/poly [GW96], as well as SAC1.
Same as NL -- but if there's an oracle, then NLOG can make queries nondeterministically on a polynomial-size, one-way oracle tape. (NL, by contrast, can use nondeterministic transitions only on the worktape; oracle queries have to be deterministic.)
See [LL76] or [HCK+88] for more information.
Although NLOG is contained in P, there exists an oracle relative to which that is not the case. This illustrates that care is needed when defining oracle access mechanisms.
Has the same relation to LIN as NP does to P.
The class of dashed hopes and idle dreams.
More formally: an "NP machine" is a nondeterministic polynomial-time Turing machine.
Then NP is the class of decision problems solvable by an NP machine such that
Equivalently, NP is the class of decision problems such that, if the answer is "yes," then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is "no," then the algorithm must declare invalid any purported proof that the answer is "yes."
For example, the SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.
A decision problem is NP-complete if (1) it is in NP, and (2) any problem in NP can be reduced to it (under some notion of reduction). The class of NP-complete problems is sometimes called NPC.
That NP-complete problems exist is immediate from the definition. The seminal result of Cook [Coo71], Karp [Kar72], and Levin [Lev73] is that many natural problems (that have nothing to do with Turing machines) are NP-complete.
The first such problem to be shown NP-complete was SAT [Coo71]. Other classic NP-complete problems include:
For many, many more NP-complete problems, see [GJ79].
There exists an oracle relative to which P and NP are unequal [BGS75]. Indeed, P and NP are unequal relative to a random oracle with probability 1 [BG81] (see [AFM01] for a novel take on this result). Though random oracle results are not always indicative about the unrelativized case [CCG+94].
There even exists an oracle relative to which the P versus NP problem is outside the usual axioms of set theory [HH76].
If we restrict to monotone classes, mP is strictly contained in mNP [Raz85].
Perhaps the most important insight anyone has had into P versus NP is to be found in [RR97]. There the authors show that no 'natural proof' can separate P from NP (or more precisely, place NP outside of P/poly), unless secure pseudorandom generators do not exist. A proof is 'natural' if it satisfies two conditions called constructivity and largeness; essentially all lower bound techniques known to date satisfy these conditions. To obtain unnatural proof techniques, some people suspect we need to relate P versus NP to heavy-duty 'traditional' mathematics, for instance algebraic geometry. See [MS02] (and the survey article [Reg02]) for a development of this point of view.
For more on P versus NP (circa 1992) see [Sip92]. For an opinion poll, see [Gas02]. P vs NP is a "Millenium Prize" problem [CMI00].
If P equals NP, then NP equals its complement coNP. Whether NP equals coNP is also open. NP and coNP can be extended to the polynomial hierarchy PH.
The set of decision problems in NP, but not in P or NPC, is sometimes called NPI. If P does not equal NP then NPI is nonempty [Lad75].
Probabilistic generalizations of NP include MA and AM. If NP is in coAM (or BPP) then PH collapses to Σ2P [BHZ87].
PH also collapses to Σ2P if NP is in P/poly [KL82].
There exist oracles relative to which NP is not in BQP [BBB+97].
An alternate characterization is NP = PCP(log n, O(1)) [ALM+98].
Also, [Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic. This leads to the subclass SNP.
It is known that if any NP-complete language is sparse (contains no more than a polynomial number of strings of length ), then P = NP. [BH08] improved this result, showing that if any language in NP has an NP-hard set of subexponential density, then coNP is contained in NP/poly and thus, by [Yap82], PH collapses to the third level.
NP is equal to SO-E, the second-order queries where the second-order quantifiers are only existantials.
The class of 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.
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.
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 NPMV as P-Sel does to P.
Defined in [HHN+95].
Has the same relation to NPMVt as P-Sel does to P.
Defined in [HHN+95].
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.
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.
Has the same relation to NPSV as P-Sel does to P.
Defined in [HHN+95].
Has the same relation to NPSVt as P-Sel does to P.
Also known as NP-sel.
Defined in [HHN+95].
The class of decision problems such that whether the answer on input x agrees with the answer on input x-1 (that is, the lexicographic predecessor of x) is solvable in polynomial time. The Turing machine has to decide agreement or disagreement without access to the answer for x-1.
Is contained in E, NT*, and ⊕P. Defined in [GHJ+91] to study ⊕P-complete problems. They show that P, NT, NT*, and ⊕P are either all equal or strictly nested. In particular, they differ with probability 1 relative to a random oracle.
Defined like NT, but with a more general ordering on inputs. A problem L is in NT* if, first, there is a partially defined predecessor function pred(x) in FP that organizes the space of inputs into a forest. The size of the lineage of each x must also be bounded by 2poly(|x|). Second, if L(x) is the Boolean answer to L on input x, then L(x)+L(pred(x)) is computable in polynomial time; or if pred(x) does not exist, L(x) is computable in polynomial time.
Defined in [GHJ+91].
Contains NT and is contained in ⊕P. The inclusions are either both strict or both equalities (whence ⊕P = P as well).
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.
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.
I decided this class is so important that it deserves an entry of its own, apart from #P.
Contains PH [Tod89], and is contained in CH and in PSPACE.
Equals PPP (exercise for the visitor).
Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].
Same as P with access to bits along a closed time curve.
Implicitly defined in [Aar05c], where it was shown that PSPACE = PCTC.
See also BQPCTC.
An analog of P for Turing machines over a complex number field.
Defined in [BCS+97].
In a two-party communication complexity problem, Alice and Bob have n-bit strings x and y respectively, and they wish to evaluate some Boolean function f(x,y) using as few bits of communication as possible. Pcc is the class of (infinite families of) f's, such that the amount of communication needed is only O(polylog(n)), even if Alice and Bob are restricted to a deterministic protocol.
Note that all functions of the form above are solvable given bits of communication, since no bounds are placed on the computational abilities of Alice and Bob. Thus, when discussing this class, "polynomially" is sometimes used in place of "polylogarithmically."
Is strictly contained in NPcc and in BPPcc because of the EQUALITY problem.
If the classes are defined in terms of total functions, then Pcc = NPcc ∩ coNPcc = UPcc.
Defined in [BFS86].
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].
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 languages L in UP such that the mapping from an input x to the unique witness for x is a permutation of L.
Contains P.
Defined in [HT03], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is UP.
On the other hand, they show that if PermUP = UP then E = UE.
See also: SelfNP.
Has the same relation to EXP as PP does to P.
Is not contained in P/poly [BFT98].
Let Δ0P = Σ0P = Π0P = P. Then for i>0, let
Then PH is the union of these classes for all nonnegative constants i.
PH can also be defined using alternating quantifiers: it's the class of problems of the form, "given an input x, does there exist a y such that for all z, there exists a w ... such that φ(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and φ is a polynomial-time computable predicate. It's not totally obvious that this is equivalent to the first definition, since the first one involves adaptive NP oracle queries and the second one doesn't, but it is.
Defined in [Sto76].
Contained in P with a PP oracle [Tod89].
Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].
Furthermore, there exist oracles separating any ΣiP from Σi+1P. In fact, relative to a random oracle, the hierarchy is infinite: each level is strictly contained in the next, with probability 1 [RST15] (this was an open problem for 29 years). Previously, it had been known that if it had collapsed relative to a random oracle, then it would have collapsed unrelativized [Boo94].
It was shown in [CPO7] that if the NP Machine Hypothesis holds, then.
For a compendium of problems complete for different classes of the Polynomial Hierarchy see [Sch02a] and [Sch02b].
PH is equal to the set of boolean queries recognizable by a concurent random acess machine using exponentially many processors and constant time[Imm89].
Since NP is the class of query expressible in second-order existantial logic, PH can also be defined as the query expressible in second-order logic.
Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.
For what it's worth, the present zookeeper has more qualms about admitting DTIME(n1000) into PhP than BQTIME(n2). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10k with k in the low hundreds.) In practice, less than 1050 bits and less than 1080 bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.
P equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.
A similar class was defined in [ABK+02], where it was also shown that PK contains PSPACE. It is not known whether PK contains all of R, or even any recursive problem not in PSPACE.
See also: BPPKT.
Has the same relation to L that PP has to P.
Contains BPL and contained in DET [Coo85].
PLPL = PL (see [HO02]).
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."
More precisely, for each input, there's a finite set of solutions (i.e. strings), and a polynomial-time algorithm that computes a cost for each solution, and a neighboring solution of lower cost provided that one exists. Then the problem is to return any solution that has cost less than or equal to all of its neighbors. (In other words, a local optimum.)
(Note: In the Zookeeper's humble opinion, PLS should have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of all neighbors of a given solution, not just a single solution of lower cost. Of course we'd require that every solution has only polynomially many neighbors. The two definitions are not obviously equivalent, and it's conceivable that knowing all the neighbors would be helpful -- for example, in simulated annealing one sometimes makes uphill moves.)
(Note to Note: The equivalance of these classes was shown (though not stated explicitly) in Theorem 1 of [JPY88].)
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
Also, there exist oracles relative to which PLS is not contained in PPA [BM04] or PPP [GHJ+22], and PPA and PPP are not contained in PLS [Mor01].
[CT07] conjecture that if PPAD is in P, then PLS is in P.
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].
Equals DSPACE((log n)c).
In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa (or if none of the inclusions hold). On the other hand, we do know that polyL does not equal P, since (for example) polyL does not have complete problems under many-to-one logspace reductions.
A level of the counting hierarchy CH.
It is not known whether there exists an oracle relative to which PPP does not equal PSPACE.
Equals P#P (exercise for the visitor).
Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.
The class of decision problems solvable by a P machine, that can make O(log n) queries to a QMA oracle (where n is the length of the input).
Defined in [Amb14].
Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is PQMA[log]-complete.
Estimating local observables remains PQMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].
PQMA[log] is contained in PP [GY16].
The class of decision problems solvable by a P machine that can make a polynomial number of non-adaptive queries to a QMA oracle.
An analog of P for Turing machines over a real number field.
Defined in [BCS+97].
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.
The class of promise problems solvable by a P machine.
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.
Contained in DSPACE(f(n)2) [BCP83].
Equals PrHSPACE(f(n)) [Jun85].
The class of decision problems for which 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).
The class of decision problems solvable by a Turing machine in polynomial space.
Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].
Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].
Contains P#P (P with a #P oracle).
A canonical PSPACE-complete problem is QBF.
Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.
Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).
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.
Same as QMA except that for a "yes" instance, there exists a state that is accepted with probability 1.
Defined in [Bra06]. It was shown there that Quantum k-SAT is QMA1-complete for any . It was also shown there that Quantum 2-SAT is in P.
This result was later improved in [GN13] where it was shown that Quantum 3-SAT is QMA1-complete.
The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
The class of problems for which there exists a BQP machine M such that:
In other words, it's the same as QRG(k) for , the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).
Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .
QRG(1) trivially contains QMA (and indeed PQRG(1)).
QRG(1) is trivially contained in QRG(2) (and hence PSPACE).
Has the same relation to L as RP does to P. The randomized machine must halt for every input and every setting of the random tape.
Contains undirected reachability (is there a path from vertex u to vertex v in an undirected graph?) [AKL+79].
Contained in RL.
Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just getNL).
Contains RHL.
[RTV05] give strong evidence that RL = L.
Has the same relation to NC as RP does to P.
Contains the maximum matching problem for bipartite graphs [MVV87].
Contained in QNC.
See also: coRNC.
Has the same relation to RNC as NC1 does to NC. And the same relation to NC1 as RP does to P.
Contained in BP•L.
(Named in honor of Stephen Cook.)
The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.
Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.
Deterministic context-free languages (DCFLs) can be recognized in SC [Coo79].
SC contains RL and BPL [Nis92].
SC equals DTISP(poly,polylog) by definition.
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 decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF2 contains both ⊕P and NP by using the counter as a witness.
Defined in [CF91], where it was also shown that SF5 = PSPACE.
The complexity of SF2, SF3, and SF4 was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:
(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)
The parameterized version of PSPACE.
Same as FPT, except that now on input (x,k) (k a parameter), the space used must be f(k)p(|x|), where p is a polynomial.
If P = PSPACE, then FPT = SLICEWISE PSPACE.
Defined in [DF99].
SO(horn) is the set of boolean queries definable with second-order formulae in normal form such that the quantifier-free part of the formula is in conjunctive normal form with at most one positive instance of a quantified relation per clause. (Atomic queries to the database don't count.)
It was shown in [Grä92] that this class is equal to P.
Those formulae can be made in prenex form where the second order is existential and the first order universal without loss of generality.
The class of problems in P for which the best parallel algorithm (using a polynomial number of processors) is faster than the best serial algorithm by a factor of Ω(nε) for some ε>0.
Defined in [KRS90].
SP is also an alternate name for XPuniform
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 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.
Has the same relation to E as UP does to P.
Has the same relation to L as UP does to P.
The problem of reachability in directed planar graphs lies in UL [SES05].
If UL = NL, then FNL is contained in #L [AJ93].
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.
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.
Has the same relation to VPk as NC does to P.
More formally, the class of VPk problems computable by a straight-line program of depth polylogarithmic in n.
Surprisingly, VNCk = VPk for any k [VSB+83].
The class of efficiently-solvable problems in Valiant's algebraic complexity theory.
More formally, the input consists of constants c1,...,cm and indeterminates X1,...,Xn over a base field k (for instance, the complex numbers or Z2). The desired output is a collection of polynomials over the Xi's. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VPk is the class of problems whose complexity is polynomial in n. (Hence, VPk is a nonuniform class, in contrast to PC and PR.)
Originated in [Val79b]; see [Bur00] for more information.
Contained in VNPk and VQPk, and contains VNCk.
Has the same relation to VPk as QP does to P.
Originated in [Val79b].
The determinant of an n-by-n matrix of indeterminates is VQPk-complete under a type of reduction called qp-projections (see [Bur00] for example). It is an open problem whether the determinant is VPk-complete.
The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(f(k)*log(n)) for some function f. The algorithm used may depend on k.
Analogous to XP, as L is to P.
A natural XL complete problem is p-MDFA-ACCEPTANCE: Given a finite two-way deterministic automation A with k heads, and given a string x, does A accept x?
Reference: [1]
The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(f(k) log(n)), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k.
Analogous to XP, as NL is to P. Nondeterministic version of XL.
A natural XNL complete problem is p-MNFA-ACCEPTANCE: Given a finite two-way nondeterministic automation A with k heads, and given a string x, does A accept x?
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.
Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.
For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).
Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.
Contains ZPP and is contained in RBQP and ZQP. Also, ZBQPZBQP = ZBQP. Defined here to clarify EQP and ZQP.
Defined as the class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial, in [Gil77]. (Proposition 5.5(iii) in this paper shows that the two definitions above are equivalent.)
Contains the problem of testing whether an integer is prime [SS77] [AH87].
In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].
There exists an oracle relative to which ZPP = EXP [Hel84a], [Hel84b], [Kur85], [Hel86].
Has the same p-measure as RP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].
![{\displaystyle [Q]^{t(n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f080666e16126e0f8a3ccfd9fe880fa3b98710c)
![{\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)
