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 exponential-time analogue of ⊕P.
There exists an oracle relative to which ⊕EXP = ZPP [BBF98].
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.
The class of decision problems for which both "yes" and "no" answers can be verified by an AM protocol.
If EXP requires exponential time even for AM protocols, then AM ∩ coAM = NP ∩ coNP [GST03].
There exists an oracle relative to which AM ∩ coAM is not contained in PP [Ver95].
APSPACE is the class of decision problems solvable with polynomial space by an alternating Turing machine. See also ASPACE.
A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.
A function f, from strings to integers, is polynomial on μ-average if there exists a constant ε>0 such that the expectation of fε(x) is finite, when x is drawn from μ.
Then (A,μ) is in AvgP if there is an algorithm for A whose running time is polynomial on μ-average.
This convoluted definition is due to Levin [Lev86], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [Gol97] for more information.
If AvgP = DistNP then EXP = NEXP [BCG+92].
Strictly contained in HeurP [NS05].
See also: (NP,P-samplable).
Has the same relation to E as BPP does to P.
EE = BPE if and only if EXP = BPP [IKW01].
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 problems solvable by a BPP machine that is given O(log n) advice bits, which can depend on both the machine's random coin flips and the input length n, but not on the input itself.
Defined in [TV02], where it was also shown that if EXP is in BPP//log thenEXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.
Equals BPTIME(2O((log n)^k)); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.
Defined in [CNS99], where the following was also shown:
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 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.
Equals DTIME(22O(n)) (though some authors alternatively define it as being equal to DTIME(2O(2n))).
EE = BPE if and only if EXP = BPP [IKW01].
The class of decision problems solvable in EXP with the help of a polynomial-length advice string that depends only on the input length.
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:
Same as MA, except now Arthur is EXP instead of polynomial-time, and the message from Merlin can be exponentially long.
There is a problem in MAEXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MAEXP does have polynomial-size circuits.
[MVW99] considered the best circuit lower bound obtainable for a problem in MAEXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2n. Such functions exist, but are not expressible using standard asymptotic notation.
Identical to MA except for that Arthur (the verifier) has random access to the proof string given by Merlin, and is limited to running times of order .
This class was used by [SM03] to show that if EXP has circuits of polynomial size, then EXP = MA.
Same as MIP, except that the provers can have non-signaling strategies.
MIPns with two provers is equal to PSPACE [Ito10]. MIPns with polylogarithmically many provers is equal to EXP [KRR13].
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].
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.
On the other hand, this result does not relativize if we allow strings of unbounded length to be written to the oracle tape. In particular, there exists an oracle relative to which NPSPACE is not contained in EXP [GTW+91].
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 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].
Has the same relation to EXP as PP does to P.
Is not contained in P/poly [BFT98].
(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")
The class of function problems, f:{0,1}n->{0,1}m, such that the kth output bit is computable in time polynomial in n and k.
Defined in [JY88].
Contained in PIO. This containment is strict, since if m=2n (say), then computing the first bit of f(x) might be EXP-complete.
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).
The class of decision problems such that a "yes" answer can be verified by a quantum interactive proof. Here the verifier is a BQP (i.e. quantum polynomial-time) algorithm, while the prover has unbounded computational resources (though cannot violate the linearity of quantum mechanics). The prover and verifier exchange a polynomial number of messages, which can be quantum states. Thus, the verifier's and prover's states may become entangled during the course of the protocol. Given the verifier's algorithm, we require that
Let QIP[k] be QIP where the prover and verifier are restricted to exchanging k messages (with the prover going last).
Defined in [Wat99], where it was also shown that PSPACE is in QIP[3].
Subsequently [KW00] showed that for all k>3, QIP[k] = QIP[3] = QIP.
QIP is contained in EXP [KW00].
QIP = IP = PSPACE [JJUW09]; thus quantum computing adds no power to single-prover interactive proofs.
QIP(1) is more commonly known as QMA.
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.
Same as RG, except that now the verifier is a BQP machine, and can exchange polynomially many quantum messages with the competing provers.
The two provers are computationally unbounded, but must obey the laws of quantum mechanics. Also, we can assume without loss of generality that the provers share no entanglement, because adversaries gain no advantage by sharing information.
Defined in [Gut05], where it was also shown that QRG is contained in NEXP ∩ coNEXP.
QRG trivially contains RG (and hence EXP), as well as SQG.
QRG is contained in EXP [GW07]. Hence QRG = RG = EXP and finding optimal strategies for zero-sum quantum games is no harder than finding optimal strategies for zero-sum classical games.
Same as QRG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. QRG(k) is the quantum version of RG(k). By definition, QRG(poly) = QRG. See also QRG(1) and QRG(2).
QRG(k) trivially contains RG(k) for each k (and hence PSPACE when ). QRG(4) trivially contains SQG.
QRG(k) is trivially contained in QRG for each k (and hence EXP).
Other than these trivial bounds, very little is known of QRG(k) for intermediate values of k. For example, does QRG(k) = RG(k) for each k?
The class of problems solvable by a probabilistic polynomial-time verifier who can exchange a polynomial number of messages with two competing, computationally-unbounded provers -- one trying to convince the verifier that the answer is "yes," the other that the answer is "no." Note that the verifier can hide information from the provers. Public-coin RG amounts to SAPTIME, which equals PSPACE [Pap83].
RG is in EXP relative to any oracle [KM92]; they are equal, unrelativized [FK97b].
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].
SO[LFP] is to SO what FO[LFP] is to FO. The LFP operator can now also take second-order variable as argument.
In Descriptive complexity we can see that SO[LFP] is equal to EXPTIME.
SO[] is to SO as FO[] is to FO. But we now also have second-order quantifier in the quantifier block.
In Descriptive complexity we can see that :
Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.
Defined in [GW05], where it was also shown that SQG contains QIP.
SQG is contained in EXP [Gut05].
SQG is trivially contained in QRG(4) (and hence EXP).
SQG trivially contains QRG(2) (and hence PSPACE).
SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.
Same as ZPP, but with 2O(n)-time instead of polynomial-time.
ZPE = EE if and only if ZPP = EXP [IKW01].
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].
