View source for Complexity Zoo:E

__NOTOC__
{{CZ-Letter-Menu|E}}


===== <span id="e" style="color:red">E</span>: Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](2<sup>O(n)</sup>).

Does not equal [[Complexity Zoo:N#np|NP]] [[zooref#boo72|[Boo72]]] or [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#boo74|[Boo74]]] relative to any oracle.  However, there is an oracle relative to which E is contained in [[Complexity Zoo:N#np|NP]] (see [[Complexity Zoo:Z#zpp|ZPP]]), and an oracle relative to [[Complexity Zoo:P#pspace|PSPACE]] is contained in E (by equating the former with [[Complexity Zoo:P#p|P]]).

There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [[zooref#wat87|[Wat87]]].

Problems hard for [[Complexity Zoo:B#bpp|BPP]] under Turing reductions have measure 1 in E [[zooref#as94|[AS94]]].

It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then [[Complexity Zoo:B#bpp|BPP]] does not equal [[#exp|EXP]].

[[zooref#it89|[IT89]]] gave an oracle relative to which E = [[Complexity Zoo:N#ne|NE]] but still there is an exponential-time binary predicate whose corresponding <i>search</i> problem is not in E.

{{zcite|BF03}} gave a proof that if E = {{zcls|n|ne}}, then no sparse set is ''collapsing'', where they defined a set <math>A</math> to be collapsing if <math>A\notin\mathsf{P}</math> and if for all <math>B</math> such that <math>A</math> and <math>B</math> are Turing reducible to each other, <math>A</math> and <math>B</math> are many-to-one reducible to each other.

Contrast with [[#exp|EXP]].

----

===== <span id="ee" style="color:red">EE</span>: Double-Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](2<sup>2<sup>O(n)</sup></sup>) (though some authors alternatively define it as being equal to [[Complexity Zoo:D#dtime|DTIME]](2<sup>O(2<sup>n</sup>)</sup>)).

EE = [[Complexity Zoo:B#bpe|BPE]] if and only if [[#exp|EXP]] = [[Complexity Zoo:B#bpp|BPP]] [[zooref#ikw01|[IKW01]]].

Contained in [[#eexp|EEXP]] and [[Complexity Zoo:N#nee|NEE]].

----

===== <span id="eee" style="color:red">EEE</span>: Triple-Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](2<sup>2<sup>2<sup>O(n)</sup></sup></sup>).

In contrast to the case of [[#ee|EE]], it is not known whether EEE = [[Complexity Zoo:B#bpee|BPEE]] implies [[#ee|EE]] = [[Complexity Zoo:B#bpe|BPE]] [[zooref#ikw01|[IKW01]]].

----

===== <span id="eespace" style="color:red">EESPACE</span>: Double-Exponential Space With Linear Exponent =====
Equals [[Complexity Zoo:D#dspace|DSPACE]](2<sup>2<sup>O(n)</sup></sup>).

Is not contained in [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] [[zooref#ny03|[NY03]]].

----

===== <span id="eexp" style="color:red">EEXP</span>: Double-Exponential Time =====
Equals [[Complexity Zoo:D#dtime|DTIME]](2<sup>2<sup>p(n)</sup></sup>) for p a polynomial.

Also known as [[Complexity Zoo:Symbols#2exp|2-EXP]].

Contains [[#ee|EE]], and is contained in [[Complexity Zoo:N#neexp|NEEXP]].

----

===== <span id="eh" style="color:red">EH</span>: Exponential-Time Hierarchy With Linear Exponent =====
Has roughly the same relationship to [[#e|E]] as [[Complexity Zoo:P#ph|PH]] does to [[Complexity Zoo:P#p|P]].

More formally, EH is defined as the union of [[#e|E]], [[Complexity Zoo:N#ne|NE]], [[Complexity Zoo:N#ne|NE]]<sup>[[Complexity Zoo:N#np|NP]]</sup>, [[Complexity Zoo:N#ne|NE]] with [[#sigma2p|&#931;<sub>2</sub>P]] oracle, and so on.

See [[zooref#har87|[Har87]]] for more information.

If [[Complexity Zoo:C#conp|coNP]] is contained in [[Complexity Zoo:A#ampolylog|AM[polylog]]], then EH collapses to {{zcls|s|s2exppnp|S<sub>2</sub>-EXP&#149;P<sup>NP</sup>}} [[zooref#ss04|[SS04]]] and indeed [[#amexp|AM<sub>EXP</sub>]] [[zooref#pv04|[PV04]]].

On the other hand, [[Complexity Zoo:C#cone|coNE]] is contained in [[Complexity Zoo:N#nepoly|NE/poly]], so perhaps it wouldn't be so surprising if NE collapses.

There exists an oracle relative to which EH does not contain [[Complexity Zoo:S#seh|SEH]] [[zooref#hem89|[Hem89]]]. EH and [[Complexity Zoo:S#seh|SEH]] are incomparable for all anyone knows.

----

===== <span id="elementary" style="color:red">ELEMENTARY</span>: Iterated Exponential Time =====
Equals the union of [[Complexity Zoo:D#dtime|DTIME]](2<sup>n</sup>), [[Complexity Zoo:D#dtime|DTIME]](2<sup>2<sup>n</sup></sup>), [[Complexity Zoo:D#dtime|DTIME]](2<sup>2<sup>2<sup>n</sup></sup></sup>), and so on.

Contained in [[Complexity Zoo:P#pr|PR]].

----

===== <span id="elkp" style="color:red">EL<sub>k</sub>P</span>: Extended Low Hierarchy =====
An extension of [[Complexity Zoo:L#lkp|L<sub>k</sub>P]].

The class of problems A such that [[Complexity Zoo:P#ph|&#931;<sub>k</sub>P]]<sup>A</sup> is contained in [[Complexity Zoo:P#ph|&#931;<sub>k-1</sub>P]]<sup>A,[[Complexity Zoo:N#np|NP]]</sup>.

Defined in [[zooref#bbs86|[BBS86]]].

----
===== <span id="ep" style="color:red">EP</span>: NP with 2<sup>k</sup> Accepting Paths =====
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that
<ol>
<li>If the answer is 'no,' then all computation paths reject.</li>
<li>If the answer is 'yes,' then the number of accepting paths is a power of two.</li>
</ol>
Contained in [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]], and in [[Complexity Zoo:M#modkp|Mod<sub>k</sub>P]] for any odd k.  Contains [[Complexity Zoo:U#up|UP]].

Defined in [[zooref#bhr00|[BHR00]]].

----

===== <span id="eptas" style="color:red">EPTAS</span>: 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+&epsilon; of the optimum in time f(&epsilon;)p(n), where p is a polynomial and f is arbitrary.

Contains [[Complexity Zoo:F#fptas|FPTAS]] and is contained in [[Complexity Zoo:P#ptas|PTAS]].

Defined in [[zooref#ct97|[CT97]]], where the following was also shown:
<ul>
<li>If [[Complexity Zoo:F#fpt|FPT]] = [[Complexity Zoo:X#xpuniform|XP<sub>uniform</sub>]] then EPTAS = [[Complexity Zoo:P#ptas|PTAS]].</li>
<li>If EPTAS = [[Complexity Zoo:P#ptas|PTAS]] then [[Complexity Zoo:F#fpt|FPT]] = [[Complexity Zoo:W#wp|W[P]]].</li>
<li>If [[Complexity Zoo:F#fpt|FPT]] is strictly contained in [[Complexity Zoo:W#w1|W[1]]], then there is a natural problem that is in [[Complexity Zoo:P#ptas|PTAS]] but not in EPTAS.  (See [[zooref#ct97|[CT97]]] for the statement of the problem, since it's not <i>that</i> natural.)</li>
</ul>

----
===== <span id="eqbp" style="color:red">k-EQBP</span>: Width-k Polynomial-Time Exact Quantum Branching Programs =====
See k-[[Complexity Zoo:P#kpbp|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<sup>(t)</sup>(x<sub>i</sub>): that is, U<sup>(t)</sup> depends on a single bit x<sub>i</sub> of the input.  (So these are the quantum analogues of so-called <i>oblivious</i> branching programs.)  In the end we measure to decide whether to accept; there must be zero probability of error.

Defined in [[zooref#amp02|[AMP02]]], where it was also shown that [[Complexity Zoo:N#nc1|NC<sup>1</sup>]] is contained in 2-EQBP.

k-BQBP can be defined similarly.

----

===== <span id="eqp" style="color:red">EQP</span>: Exact Quantum Polynomial-Time =====
The same as [[Complexity Zoo:B#bqp|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 [[zooref#bv97|[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|EQP<sub>K</sub>]].  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 [[zooref#adh97|[ADH97]]].

There is an oracle that separates EQP from [[Complexity Zoo:N#np|NP]] [[zooref#bv97|[BV97]]], indeed from [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#gp01|[GP01]]].  There is also an oracle relative to which EQP is not in [[Complexity Zoo:M#modkp|Mod<sub>p</sub>P]] where p is prime [[zooref#gv02|[GV02]]].  On the other hand, EQP is in [[Complexity Zoo:L#lwpp|LWPP]] [[zooref#fr98|[FR98]]].

[[Complexity Zoo:P#p|P]]<sup>||[[Complexity Zoo:N#np|NP]][2k]</sup> is contained in EQP<sup>||[[Complexity Zoo:N#np|NP]][k]</sup>, where "||[[Complexity Zoo:N#np|NP]][k]" denotes k nonadaptive oracle queries to [[Complexity Zoo:N#np|NP]] (queries that cannot depend on the results of previous queries) [[zooref#bd99|[BD99]]].

See also [[Complexity Zoo:Z#zbqp|ZBQP]].

----

===== <span id="eqpk" style="color:red">EQP<sub>K</sub></span>: 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<sub>K</sub> over all finite gate sets K whose amplitudes are in the ring R can be written EQP<sub>S</sub>.

Defined in [[zooref#adh97|[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<sub>K</sub>.

[[zooref#fr98|[FR98]]] show that EQP<sub>Q</sub> is in [[Complexity Zoo:L#lwpp|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<sub>Q</sub> by Simon's algorithm.  The [[Complexity_Garden#discrete_logarithm|discrete logarithm]] problem over Z/p is in EQP<sub>Q-bar</sub> using infinitely many gates [[zooref#mz03|[MZ03]]].

----

===== <span id="eqtime" style="color:red">EQTIME(f(n))</span>: Exact Quantum f(n)-Time =====
Same as [[#eqp|EQP]], but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [[zooref#bv97|[BV97]]].

----
===== <span id="espace" style="color:red">ESPACE</span>: Exponential Space With Linear Exponent =====
Equals [[Complexity Zoo:D#dspace|DSPACE]](2<sup>O(n)</sup>).

If [[#e|E]] = ESPACE then [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:B#bpp|BPP]] [[zooref#hy84|[HY84]]].

Indeed if [[#e|E]] has nonzero measure in ESPACE then [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:B#bpp|BPP]] [[zooref#lut91|[Lut91]]].

ESPACE is not contained in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#kan82|[Kan82]]].

Is not contained in [[#bqpmpoly|BQP/mpoly]] [[zooref#ny03|[NY03]]].

See also: [[#expspace|EXPSPACE]].

----
===== <span id="existsbpp" style="color:red">&#8707;BPP</span>: [[Complexity Zoo:B#bpp|BPP]] With Existential Operator =====
The class of problems for which there exists a [[Complexity Zoo:B#bpp|BPP]] machine M such that, for all inputs x,
<ul>
<li>If the answer is "yes" then there exists a y such that M(x,y) accepts.</li>
<li>If the answer is "no" then for all y, M(x,y) rejects.</li>
</ul>
Alternatively defined as NP<sup>BPP</sup>.

Contains [[Complexity Zoo:N#np|NP]] and [[Complexity Zoo:B#bpp|BPP]], and is contained in [[Complexity Zoo:M#ma|MA]] and [[#sbp|SBP]].

&#8707;BPP seems <i>obviously</i> equal to [[Complexity Zoo:M#ma|MA]], yet [[zooref#ffk93|[FFK+93]]] constructed an oracle relative to which they're unequal!  Here is the difference: if the answer is "yes," [[Complexity Zoo:M#ma|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 [[Complexity Zoo:P#p|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 &#8707;BPP, by contrast, the probability that M(x,y) accepts must <i>always</i> be either at most 1/3 or at least 2/3, for all y's.

----

===== <span id="existsniszk" style="color:red">&#8707;NISZK</span>: [[Complexity Zoo:N#niszk|NISZK]] With Existential Operator =====
Contains [[Complexity Zoo:N#np|NP]] and [[Complexity Zoo:N#niszk|NISZK]], and is contained in the third level of [[Complexity Zoo:P#ph|PH]].

----
===== <span id="exp" style="color:red">EXP</span>: Exponential Time =====
Equals the union of [[Complexity Zoo:D#dtime|DTIME]](2<sup>p(n)</sup>) over all polynomials p.

Also equals [[Complexity Zoo:P#p|P]] with [[#e|E]] oracle.

If [[Complexity Zoo:L#l|L]] = [[Complexity Zoo:P#p|P]] then [[Complexity Zoo:P#pspace|PSPACE]] = EXP.

If EXP is in [[Complexity Zoo:P#ppoly|P/poly]] then EXP = [[Complexity Zoo:M#ma|MA]] [[zooref#bfl91|[BFL91]]].

Problems complete for EXP under many-one reductions have measure 0 in EXP [[zooref#may94|[May94]]], [[zooref#jl95|[JL95]]].

There exist oracles relative to which
<ul>
<li>EXP = [[Complexity Zoo:N#np|NP]] = [[Complexity Zoo:Z#zpp|ZPP]] [[zooref#hel84|[Hel84a]]], [[zooref#hel84b|[Hel84b]]], [[zooref#kur85|[Kur85]]], [[zooref#hel86|[Hel86]]],</li>
<li>EXP = [[Complexity Zoo:N#nexp|NEXP]] but still [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:N#np|NP]] [[zooref#dek76|[Dek76]]],</li>
<li>EXP does not equal [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#dek76|[Dek76]]].</li>
</ul>
[[zooref#bt04|[BT04]]] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in [[Complexity Zoo:P#p|P]] of subexponential density.  Then A-S is Turing-complete for EXP.

{{zcite|SM03}} show that if EXP has circuits of polynomial size, then {{zcls|p|p}} can be simulated in {{zcls|m|mapolylog|MA<sub>POLYLOG</sub>}} 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 &sube; {{zcls|m|ma}} if EXP has circuits of polynomial size.

[[zooref#su05|[SU05]]] show that EXP <math>\not\subseteq</math> [[Complexity Zoo:N#nppoly|NP/poly]] implies EXP <math>\not\subseteq</math> [[Complexity Zoo:P#pparnp|P<sup>||NP</sup>]]/poly.

In descriptive complexity EXPTIME can be defined as [[#Complexity_Zoo:S#sot|SO(<math>2^{n^{O(1)}}</math>)]] which is also [[#Complexity_Zoo:F#solfp|SO(LFP)]]
----

===== <span id="exppoly" style="color:red">EXP/poly</span>: Exponential Time With Polynomial-Size Advice =====
The class of decision problems solvable in [[#exp|EXP]] with the help of a polynomial-length advice string that depends only on the input length.

Contains [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] [[zooref#aar04b|[Aar04b]]].

----
===== <span id="expspace" style="color:red">EXPSPACE</span>: Exponential Space =====
Equals the union of [[Complexity Zoo:D#dspace|DSPACE]](2<sup>p(n)</sup>) over all polynomials p.

See also: [[#espace|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 [[zooref#ber80|[Ber80]]].