# Difference between revisions of "Complexity Zoo:E"

(→k-EQBP: Width-k Polynomial-Time Exact Quantum Branching Programs) |
m (1 revision: Complexity zoo import.) |

## Latest revision as of 22:10, 17 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 -
k-EQBP -
EQP -
EQP_{K} -
EQTIME(f(n)) -
ESPACE -
∃BPP -
∃NISZK -
EXP -
EXP/poly -
EXPSPACE

##### [edit] 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 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.

##### [edit] 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].

##### [edit] 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].

##### [edit] EESPACE: Double-Exponential Space With Linear Exponent

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

Is not contained in BQP/qpoly [NY03].

##### [edit] 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.

##### [edit] 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 Σ_{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.

##### [edit] ELEMENTARY: Iterated Exponential Time

Equals the union of DTIME(2^{n}), DTIME(2^{2n}), DTIME(2^{22n}), and so on.

Contained in PR.

##### [edit] 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 Σ_{k-1}P^{A,NP}.

Defined in [BBS86].

##### [edit] 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].

##### [edit] 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.)

##### [edit] 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^{1} is contained in 2-EQBP.

k-BQBP can be defined similarly.

##### [edit] 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 Δ_{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.

##### [edit] 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].

##### [edit] 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].

##### [edit] 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.

##### [edit] ∃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.

##### [edit] ∃NISZK: NISZK With Existential Operator

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

##### [edit] 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 many-one 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 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 NP/poly implies EXP P^{||NP}/poly.

In descriptive complexity EXPTIME can be defined as SO() which is also SO(LFP)

##### [edit] 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.

##### [edit] 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].