Complexity Zoo:E - Revision history

Emil Jeřábek: /* ELEMENTARY: Iterated Exponential Time */ fix a confusing description

2024-11-06T08:15:34Z

ELEMENTARY: Iterated Exponential Time: fix a confusing description

Timeroot: /* ∃BPP: BPP With Existential Operator */ fix broken link to SBP

2024-09-30T19:42:01Z

∃BPP: BPP With Existential Operator: fix broken link to SBP

LikeWhaaaat: /* EXP: Exponential Time */ KUR85 does not exist (the link provided in the bibliography points to a paper made by Hans Heller), and the only paper he wrote in 85 is not related to the question of EXP = ZPP

2024-07-19T23:11:19Z

EXP: Exponential Time: KUR85 does not exist (the link provided in the bibliography points to a paper made by Hans Heller), and the only paper he wrote in 85 is not related to the question of EXP = ZPP

Emil Jeřábek: /* ∃R: Existential theory of the reals */

2023-06-22T11:06:14Z

∃R: Existential theory of the reals

Emil Jeřábek: /* ∃R: Existential theory of the reals */

2023-06-22T11:00:38Z

∃R: Existential theory of the reals

Emil Jeřábek: /* ∃Reals : Problems in ETR */ improve description

2023-06-22T10:54:13Z

∃Reals : Problems in ETR: improve description

Douglas at 07:33, 17 February 2022

2022-02-17T07:33:58Z

Admin: 1 revision: Complexity zoo import.

2012-11-18T03:10:30Z

1 revision: Complexity zoo import.

Cosenal: /* k-EQBP: Width-k Polynomial-Time Exact Quantum Branching Programs */

2011-08-23T15:36:32Z

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

New page

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

===== E: Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](2O(n)).

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

----

===== EE: Double-Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](22O(n)) (though some authors alternatively define it as being equal to [[Complexity Zoo:D#dtime|DTIME]](2O(2n))).

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

----

===== EEE: Triple-Exponential Time With Linear Exponent =====
Equals [[Complexity Zoo:D#dtime|DTIME]](222O(n)).

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

----

===== EESPACE: Double-Exponential Space With Linear Exponent =====
Equals [[Complexity Zoo:D#dspace|DSPACE]](22O(n)).

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

----

===== EEXP: Double-Exponential Time =====
Equals [[Complexity Zoo:D#dtime|DTIME]](22p(n)) 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]].

----

===== EH: 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]][[Complexity Zoo:N#np|NP]], [[Complexity Zoo:N#ne|NE]] with [[#sigma2p|Σ2P]] 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|S2-EXPPNP}} [[zooref#ss04|[SS04]]] and indeed [[#amexp|AMEXP]] [[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.

----

===== ELEMENTARY: Iterated Exponential Time =====
Equals the union of [[Complexity Zoo:D#dtime|DTIME]](2n), [[Complexity Zoo:D#dtime|DTIME]](22n), [[Complexity Zoo:D#dtime|DTIME]](222n), and so on.

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

----

===== ELkP: Extended Low Hierarchy =====
An extension of [[Complexity Zoo:L#lkp|LkP]].

The class of problems A such that [[Complexity Zoo:P#ph|ΣkP]]A is contained in [[Complexity Zoo:P#ph|Σk-1P]]A,[[Complexity Zoo:N#np|NP]].

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

----
===== EP: NP with 2k 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=P]], and in [[Complexity Zoo:M#modkp|ModkP]] for any odd k. Contains [[Complexity Zoo:U#up|UP]].

Defined in [[zooref#bhr00|[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 [[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|XPuniform]] 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 that natural.)</li>
</ul>

----
===== k-EQBP: 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(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 [[zooref#amp02|[AMP02]]], where it was also shown that [[Complexity Zoo:N#nc1|NC1]] is contained in 2-EQBP.

k-BQBP can be defined similarly.

----

===== EQP: 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|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 [[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|Δ2P]] [[zooref#gp01|[GP01]]]. There is also an oracle relative to which EQP is not in [[Complexity Zoo:M#modkp|ModpP]] 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]]||[[Complexity Zoo:N#np|NP]][2k] is contained in EQP||[[Complexity Zoo:N#np|NP]][k], 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]].

----

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

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

----

===== EQTIME(f(n)): 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]]].

----
===== ESPACE: Exponential Space With Linear Exponent =====
Equals [[Complexity Zoo:D#dspace|DSPACE]](2O(n)).

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

----
===== ∃BPP: [[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 NPBPP.

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

∃BPP seems obviously 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 ∃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: [[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]].

----
===== EXP: Exponential Time =====
Equals the union of [[Complexity Zoo:D#dtime|DTIME]](2p(n)) 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|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 &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||NP]]/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)]]
----

===== EXP/poly: 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]]].

----
===== EXPSPACE: Exponential Space =====
Equals the union of [[Complexity Zoo:D#dspace|DSPACE]](2p(n)) 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]]].

@@ Line 69: / Line 69: @@
 ----
-===== <span id="elementary" style="color:red">ELEMENTARY</span>: Iterated Exponential Time =====
+===== <span id="elementary" style="color:red">ELEMENTARY</span>: Finitely 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]].
+Contained in [[Complexity Zoo:P#pr|PR]] and in [[Complexity Zoo:T#tower|TOWER]].
 ----

@@ Line 172: / Line 172: @@
 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]].
+Contains [[Complexity Zoo:N#np|NP]] and [[Complexity Zoo:B#bpp|BPP]], and is contained in [[Complexity Zoo:M#ma|MA]] and [[Complexity Zoo:S#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.

@@ Line 184: / Line 184: @@
 ===== <span id="existsreals" style="color:red">&#8707;R</span>: 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.
+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 [[zooref#sha10|[Sha10]]].
 Contains NP and is contained in PSPACE.

@@ Line 183: / Line 183: @@
 ----
-===== <span id="exists" style="color:red">&#8707;R</span>: Existential theory of the reals =====
+===== <span id="existsreals" style="color:red">&#8707;R</span>: 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.

@@ Line 183: / Line 183: @@
 ----
-===== <span id="exists" style="color:red"></span>&#8707;Reals : Problems in ETR =====
+===== <span id="exists" style="color:red">&#8707;R</span>: Existential theory of the reals =====
-Contains NP and is contained in PSPACE. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. Many problems in discrete and computational geometry are contained in this class.
+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.
 ----
 ===== <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.

@@ Line 205: / Line 205: @@
 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#np|NP]] = [[Complexity Zoo:Z#zpp|ZPP]] [[zooref#hel84|[Hel84a]]], [[zooref#hel84b|[Hel84b]]], [[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>

@@ Line 180: / Line 180: @@
 ===== <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]].
 ----

← Older revision	Revision as of 03:10, 18 November 2012
(No difference)