Complexity Zoo:E

From Complexity Zoo
Revision as of 19:42, 30 September 2024 by Timeroot (talk | contribs) (→‎∃BPP: BPP With Existential Operator: fix broken link to SBP)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 - ELkP - EP - EPTAS - k-EQBP - EQP - EQPK - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - ∃R - EXP - EXP/poly - EXPSPACE


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.


EE: Double-Exponential Time With Linear Exponent

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

Contained in EEXP and NEE.


EEE: Triple-Exponential Time With Linear Exponent

Equals DTIME(222O(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(22O(n)).

Is not contained in BQP/qpoly [NY03].


EEXP: Double-Exponential Time

Equals DTIME(22p(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, 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.


ELEMENTARY: Iterated Exponential Time

Equals the union of DTIME(2n), DTIME(22n), DTIME(222n), and so on.

Contained in PR.


ELkP: Extended Low Hierarchy

An extension of LkP.

The class of problems A such that ΣkPA is contained in Σk-1PA,NP.

Defined in [BBS86].


EP: NP with 2k 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 ModkP 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 = XPuniform 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)(xi): that is, U(t) depends on a single bit xi 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 NC1 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 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.


EQPK: 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 EQPK over all finite gate sets K whose amplitudes are in the ring R can be written EQPS.

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

[FR98] show that EQPQ 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 EQPQ by Simon's algorithm. The discrete logarithm problem over Z/p is in EQPQ-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(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.


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


∃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(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)


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(2p(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].