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].
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 PSPACEA with probability 1, where A is an oracle chosen uniformly at random.
Almost-PSPACE is not known to equal PSPACE -- rather surprisingly, given the fact that PSPACE equals BPPSPACE and even PPSPACE.
What's known is that Almost-PSPACE = BPexpā PSPACE, where BPexpā is like the BPā operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXPNP ∩ coNEXPNP.
Whereas both BPexpā PSPACE and BPPSPACE machines are allowed exponentially many random bits, the former has a reusable record of all of these bits on a witness tape, while the latter can only preserve a fraction of them on the work tape.
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).
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 such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,
Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.
Check is contained in NEXP ∩ coNEXP [FRS88].
[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.
Contained in NEXP/poly (folklore result reported in [Fortnow's weblog]).
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 NEXP machine such that, given a "yes" instance, no more than an exponential number of computation paths accept.
Contained in MIP[NPFewEXP] (MIP where provers are not unbounded in computational power, but are limited to NPFewEXP) [AKS+94].
Alternatively, FewEXP can refer to the sparsity of accepting paths in a given instance. In [AKR+03], the authors show that the conjectures "FewEXP search instances are EXP-solvable" and "FewEXP decision instances are EXP/poly-solvable" are equivalent. That is, for all NEXP machines , the following conditions are equivalent:
The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,
Contains compIP [BG94] and Check [BK89].
Contained in MIP = NEXP [FRS88].
Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].
An interactive oracle proof (IOP) is a proof system that combines PCP and IP. An IOP allows both the prover and verifier to send messages like in the interactive proof model, but the verifier is given oracle access to the prover's messages. This is similar to a PCP, but instead of sending one fixed proof, the prover can send multiple proofs during the interaction, with the proofs' contents depending on the verifier messages. The verifier can then randomly query symbols from the received proofs.
The class of problems solved by IOP is NEXP, which is also the class of problems solved by PCP. Therefore IOPs are not more powerful than PCPs, but they can achieve better parameters such as total proof length, alphabet size, and query complexity. The parameters of an IOP are determined by simply summing up the parameters at each round. IOPs can be converted to IPs using Merkle trees via the BCS compiler, the same way PCPs are converted.
Same as MA, except now Arthur is E instead of polynomial-time.
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Same as IP, except that now the verifier can exchange messages with many provers, not just one. The provers cannot communicate with each other during the execution of the protocol, so the verifier can "cross-check" their assertions (as with suspects in separate interrogation rooms).
Defined in [BGK+88].
Let MIP[k] be the class of decision problems for which a "yes" answer can be verified with k provers. Then for all k>2, MIP[k] = MIP[2] = MIP [BGK+88].
MIP equals NEXP [BFL91]; this is a famous non-relativizing result.
Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.
Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP.
MIP* contains NEXP [IV12]. By contrast, MIP, the corresponding class without entanglement, equals NEXP (and even MIP[2,1] with two provers and one round equals NEXP).
Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].
MIP*[2,1] contains XOR-MIP*[2,1].
In 2012 it was shown that QMIP = MIP* [RUV12]
In 2020 it was shown that MIP* = RE [JNVWY20].
Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).
Contained in NEXP.
Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Contained in NEEXP.
Contains coNEXP (folklore result reported in Fortnow's weblog).
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].
Same as QMA, except that now the verifier is given two polynomial-size quantum certificates, which are guaranteed to be unentangled.
Defined in [KMY01].
In [BT09], the authored presented a QMAlog(2) (that is, the length of the certificates is logarithmic in the size of the problem -- see, e.g., QMAlog) protocol for 3-Coloring, with perfect completeness and 1-1/poly(n) soundness. Note that a similar construction for QMA is highly unlikely, since it would imply NP is contained in QMAlog=BQP. An analogous result, with constant soundness but with quadratic proof length was shown in [ABD+08]. It was shown shown there that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE. The authors also show that there exists no perfectly disentangler that can be used to simulate QMA(2) in QMA, though other approaches to showing QMA = QMA(2) may still exist.
It was shown in [HM13] that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. It was shown in [BCY11] that QMA(2) = QMA if the verifier is restricted to one-way LOCC protocols.
The best known unconditional upper bound is NEXP. If QMA(2)=NEXP, then QΣ2=QΠ2 (see QPH) (alternating quantifiers provide no additional power in the quantum setting) [GSSSY18]. If QCPH=QPH (quantum proofs provide no additional power in the presence of alternating quantifiers), then QMA(2) is in PPPPP [GSSSY18].
Approximating the minimal energy of a sparse Hamiltonian with respect to a separable state (which is known as the Separable Sparse Hamiltonian problem) is QMA(2)-complete [CS12]. This is in contrast to the Separable Local Hamiltonian problem which is in QMA [CS12].
The quantum generalization of MIP, and the multi-prover generalization of QIP.
A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.
Defined in [KM02].
Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].
QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.
Same as QMIP, except that now the provers share only a polynomial number of EPR pairs, instead of an unlimited number.
Defined in [KM02], where it was also shown that QMIPle is contained in NEXP = QMIPne.
Same as QMIP, except that now the provers have no prior entanglement.
Defined in [KM02], where it was also shown that QMIPne = NEXP. Thus, QMIPne contains QMIPle.
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.
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.
Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.
Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.
XOR-MIP*[2,1] is contained in NEXP [CHT+04].
XOR-MIP*[2,1] is contained in QIP[2] [Weh06]
