Class Description

E: Exponential Time With Linear Exponent

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.

Linked From

ACC0: AC0 With Arbitrary MOD Gates

Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.

Contained in TC0.

Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].

According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.

There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].

Contains 4-PBP [BT88].

See also: QACC0 and CC0.

More about...


AvgE: Average Exponential-Time With Linear Exponent

Has the same relation to E as AvgP does to P.

More about...


BPE: Bounded-Error Probabilistic E

Has the same relation to E as BPP does to P.

EE = BPE if and only if EXP = BPP [IKW01].

More about...


BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
  2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(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.

More about...


EH: Exponential-Time Hierarchy With Linear Exponent

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.

More about...


ESPACE: Exponential Space With Linear Exponent

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.

More about...


EXP: Exponential Time

Equals the union of DTIME(2p(n)) over all polynomials p.

Also equals P with E oracle.

If L = P then PSPACE = EXP.

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)

More about...


MA: Merlin-Arthur

The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that

  1. If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
  2. If the answer is "no," then for all proofs Arthur accepts with probability at most 1/3.

Defined in [Bab85].

An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).

Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.

Also contained in Σ2PΠ2P.

There exists an oracle relative to which BQP is not in MA [Wat00].

Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].

Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size for any . In the same paper, the result was used to show that MA/1 cannot be solved on more than a fraction of inputs having length by any circuit of size . Finally, it was shown that MA does not have arithmetic circuits of size .

See also: MAE, MAEXP, OMA.

More about...


MAE: Exponential-Time MA With Linear Exponent

Same as MA, except now Arthur is E instead of polynomial-time.

If MAE = NEE then MA = NEXPcoNEXP [IKW01].

More about...


NE: Nondeterministic E

Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).

PNE = NPNE [Hem89].

Contained in NEXP.

More about...


NT: Near-Testable

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.

More about...


ONP: Oblivious NP

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:

  1. There is a witness for each n of polynomial size, so that for any input of size n, if the input is in L, then the verifier accepts on that input and the witness.
  2. If the input is not in L, then for any witness, the verifier rejects on that input.

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.

More about...


P/poly: Nonuniform Polynomial-Time

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.

More about...


PermUP: Self-Permuting UP

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.

More about...


QPLIN: Linear Quasipolynomial-Time

Equals DTIME(nO(log n)).

Has the same relationship to QP that E does to EXP.

More about...


SelfNP: Self-Witnessing NP

The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.

Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.

They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.

See also: PermUP.

More about...


UE: Unambiguous Exponential-Time With Linear Exponent

Has the same relation to E as UP does to P.

More about...


ZPE: Zero-Error Probabilistic E

Same as ZPP, but with 2O(n)-time instead of polynomial-time.

ZPE = EE if and only if ZPP = EXP [IKW01].

More about...