Class Description

ESPACE: Exponential Space With Linear Exponent

Equals DSPACE(2O(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.

Linked From

BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

The class of languages recognized by a syntactic BQP machine with deterministic polynomial advice that depends only on the input length, such that the output is correct with probability 2/3 when the advice is good.

Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomial-size classical circuits.

Referred to with a variety of other ad hoc names, including BQP/poly on occassion.

Contains BQP/qlog, and is contained in BQP/qpoly.

Does not contain ESPACE [NY03].

More about...


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

More about...