Difference between revisions of "Complexity Zoo:E"
m (1 revision: Complexity zoo import.) 

(No difference)

Latest revision as of 03:10, 18 November 2012
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_{k}P  EP  EPTAS  kEQBP  EQP  EQP_{K}  EQTIME(f(n))  ESPACE  ∃BPP  ∃NISZK  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 polynomialtime Turing reductions but not polynomialtime truthtable 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 exponentialtime 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 manytoone reducible to each other.
Contrast with EXP.
EE: DoubleExponential 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].
EEE: TripleExponential 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: DoubleExponential Space With Linear Exponent
Equals DSPACE(2^{2O(n)}).
Is not contained in BQP/qpoly [NY03].
EEXP: DoubleExponential Time
Equals DTIME(2^{2p(n)}) for p a polynomial.
Also known as 2EXP.
Contains EE, and is contained in NEEXP.
EH: ExponentialTime 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 Σ_{2}P oracle, and so on.
See [Har87] for more information.
If coNP is contained in AM[polylog], then EH collapses to S_{2}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^{n}), DTIME(2^{2n}), DTIME(2^{22n}), and so on.
Contained in PR.
EL_{k}P: Extended Low Hierarchy
An extension of L_{k}P.
The class of problems A such that Σ_{k}P^{A} is contained in Σ_{k1}P^{A,NP}.
Defined in [BBS86].
EP: NP with 2^{k} Accepting Paths
The class of decision problems solvable by an NP machine such that
 If the answer is 'no,' then all computation paths reject.
 If the answer is 'yes,' then the number of accepting paths is a power of two.
Contained in C_{=}P, and in Mod_{k}P for any odd k. Contains UP.
Defined in [BHR00].
EPTAS: Efficient PolynomialTime 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.)
kEQBP: Widthk PolynomialTime Exact Quantum Branching Programs
See kPBP 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 socalled 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^{1} is contained in 2EQBP.
kBQBP can be defined similarly.
EQP: Exact Quantum PolynomialTime
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 boundederror 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 Δ_{2}P [GP01]. There is also an oracle relative to which EQP is not in Mod_{p}P 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 PolynomialTime with Gate Set K
The set of problems that can be answered by a uniform family of polynomialsized 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 1qubit 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_{Qbar} 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 polynomialtime 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.
EXP: Exponential Time
Equals the union of DTIME(2^{p(n)}) over all polynomials p.
If EXP is in P/poly then EXP = MA [BFL91].
Problems complete for EXP under manyone reductions have measure 0 in EXP [May94], [JL95].
There exist oracles relative to which
 EXP = NP = ZPP [Hel84a], [Hel84b], [Kur85], [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 manyone complete for EXP, and let S be any set in P of subexponential density. Then AS is Turingcomplete for EXP.
[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MA_{POLYLOG} such that no deterministic polynomialtime 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 PolynomialSize Advice
The class of decision problems solvable in EXP with the help of a polynomiallength advice string that depends only on the input length.
EXPSPACE: Exponential Space
Equals the union of DSPACE(2^{p(n)}) over all polynomials p.
See also: ESPACE.
Given a firstorder statement about real numbers, involving only addition and comparison (no multiplication), we can decide in EXPSPACE whether it's true or not [Ber80].