Complexity Zoo:E

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - EL_kP - EP - EPTAS - k-EQBP - EQP - EQP_K - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - ∃R - EXP - EXP/poly - EXPSPACE

E: Exponential Time With Linear Exponent

Equals DTIME(2^O(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 $A$ to be collapsing if $A\notin {\mathsf {P}}$ and if for all $B$ such that $A$ and $B$ are Turing reducible to each other, $A$ and $B$ are many-to-one reducible to each other.

Contrast with EXP.

---

EE: Double-Exponential Time With Linear Exponent

Equals DTIME(2^2O(n)) (though some authors alternatively define it as being equal to DTIME(2^O(2n))).

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

Contained in EEXP and NEE.

---

EEE: Triple-Exponential Time With Linear Exponent

Equals DTIME(2^22O(n)).

In contrast to the case of EE, it is not known whether EEE = BPEE implies EE = BPE [IKW01].

---

EESPACE: Double-Exponential Space With Linear Exponent

Equals DSPACE(2^2O(n)).

Is not contained in BQP/qpoly [NY03].

---

EEXP: Double-Exponential Time

Equals DTIME(2^2p(n)) for p a polynomial.

Also known as 2-EXP.

Contains EE, and is contained in NEEXP.

---

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, NE^NP, NE with Σ₂P oracle, and so on.

See [Har87] for more information.

If coNP is contained in AM[polylog], then EH collapses to S₂-EXP•P^NP [SS04] and indeed AM_EXP [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.

---

ELEMENTARY: Iterated Exponential Time

Equals the union of DTIME(2ⁿ), DTIME(2²ⁿ), DTIME(2²²ⁿ), and so on.

Contained in PR.

---

EL_kP: Extended Low Hierarchy

An extension of L_kP.

The class of problems A such that Σ_kP^A is contained in Σ_k-1P^A,NP.

Defined in [BBS86].

---

EP: NP with 2^k Accepting Paths

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

1. If the answer is 'no,' then all computation paths reject.
2. If the answer is 'yes,' then the number of accepting paths is a power of two.

Contained in C₌P, and in Mod_kP for any odd k. Contains UP.

Defined in [BHR00].

---

EPTAS: Efficient Polynomial-Time Approximation Scheme

The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.

Contains FPTAS and is contained in PTAS.

Defined in [CT97], where the following was also shown:

• If FPT = XP_uniform then EPTAS = PTAS.
• If EPTAS = PTAS then FPT = W[P].
• If FPT is strictly contained in W[1], then there is a natural problem that is in PTAS but not in EPTAS. (See [CT97] for the statement of the problem, since it's not that natural.)

---

k-EQBP: Width-k Polynomial-Time Exact Quantum Branching Programs

See k-PBP for the definition of a classical branching program.

A quantum branching program is the natural quantum generalization: we have a quantum state in a Hilbert space of dimension k. Each step t consists of applying a unitary matrix U^(t)(x_i): that is, U^(t) depends on a single bit x_i of the input. (So these are the quantum analogues of so-called oblivious branching programs.) In the end we measure to decide whether to accept; there must be zero probability of error.

Defined in [AMP02], where it was also shown that NC¹ is contained in 2-EQBP.

k-BQBP can be defined similarly.

---

EQP: Exact Quantum Polynomial-Time

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 EQP_K. 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 Δ₂P [GP01]. There is also an oracle relative to which EQP is not in Mod_pP 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.

---

EQP_K: Exact Quantum Polynomial-Time with Gate Set K

The set of problems that can be answered by a uniform family of polynomial-sized quantum circuits whose gates are drawn from a set K, and that return the correct answer with probability 1, and run in polynomial time with probability 1, and the allowed gates are drawn from a set K. K may be either finite or countable and enumerated. If S is a ring, the union of EQP_K over all finite gate sets K whose amplitudes are in the ring R can be written EQP_S.

Defined in [ADH97] in the special case of a finite set of 1-qubit gates controlled by a second qubit. It was shown there that transcendental gates may be replaced by algebraic gates without decreasing the size of EQP_K.

[FR98] show that EQP_Q is in LWPP. The proof can be generalized to any finite, algebraic gate set K.

The hidden shift problem for a vector space over Z/2 is in EQP_Q by Simon's algorithm. The discrete logarithm problem over Z/p is in EQP_Q-bar using infinitely many gates [MZ03].

---

EQTIME(f(n)): Exact Quantum f(n)-Time

Same as EQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

---

ESPACE: Exponential Space With Linear Exponent

Equals DSPACE(2^O(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.

---

∃BPP: BPP With Existential Operator

The class of problems for which there exists a BPP machine M such that, for all inputs x,

• If the answer is "yes" then there exists a y such that M(x,y) accepts.
• If the answer is "no" then for all y, M(x,y) rejects.

Alternatively defined as NP^BPP.

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.

---

∃NISZK: NISZK With Existential Operator

Contains NP and NISZK, and is contained in the third level of PH.

---

∃R: Existential theory of the reals

Problems reducible to the language of multivariate polynomials with integer coefficients that have a real solution. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. Defined in [Sha10].

Contains NP and is contained in PSPACE.

Many problems in discrete and computational geometry are contained in this class.

---

EXP: Exponential Time

Equals the union of DTIME(2^p(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

• EXP = NP = ZPP [Hel84a], [Hel84b], [Hel86],
• EXP = NEXP but still P does not equal NP [Dek76],
• EXP does not equal PSPACE [Dek76].

[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 MA_POLYLOG 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 $\not \subseteq$ NP/poly implies EXP $\not \subseteq$ P^||NP/poly.

In descriptive complexity EXPTIME can be defined as SO($2^{n^{O(1)}}$) which is also SO(LFP)

---

EXP/poly: Exponential Time With Polynomial-Size Advice

The class of decision problems solvable in EXP with the help of a polynomial-length advice string that depends only on the input length.

Contains BQP/qpoly [Aar04b].

---

EXPSPACE: Exponential Space

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

See also: ESPACE.

Given a first-order statement about real numbers, involving only addition and comparison (no multiplication), we can decide in EXPSPACE whether it's true or not [Ber80].