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
 E: Exponential Time With Linear Exponent
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].
[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
 EEE: Triple-Exponential Time With Linear Exponent
 EESPACE: Double-Exponential Space With Linear Exponent
 EEXP: Double-Exponential Time
Equals DTIME(22p(n)) for p a polynomial.
Also known as 2-EXP.
 EH: Exponential-Time Hierarchy With Linear Exponent
See [Har87] for more information.
 ELEMENTARY: Iterated Exponential Time
Contained in PR.
 ELkP: Extended Low Hierarchy
An extension of LkP.
Defined in [BBS86].
 EP: NP with 2k 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.
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.
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, 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.
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].
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.
 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
See also: EXPSPACE.
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.
∃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.
 EXP: Exponential Time
Equals the union of DTIME(2p(n)) over all polynomials p.
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].
[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.
 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.
 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].