Class Description

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

Linked From

ALL: The Class of All Languages

Literally, the class of ALL languages.

ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.

First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).

Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.

Nor is it hard to show that MA_EXP/rpoly = ALL.

Also, per [Aar18], PDQP/qpoly = ALL.

On the other hand, even though PSPACE contains PP, and EXPSPACE contains MA_EXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.

So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)

It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MA_EXP/rpoly means M(A_EXP/rpoly), while (MA_EXP)/rpoly equals MA_EXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.

More about...

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.

More about...

NEXP: Nondeterministic EXP

Nondeterministic exponential time (i.e. NTIME(2^p(n)) for p a polynomial).

Equals MIP [BFL91] (but not relative to all oracles).

NEXP is in MIP* [IV12].

NEXP is in P/poly if and only if NEXP = MA [IKW01].

[KI02] show the following:

• If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
• If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then NEXP is not in P/poly.
• If NEXP is in P/poly, then NEXP is in P^Perm.

Does not equal NP [SFM78].

Does not equal EXP if and only if there is a sparse set in NP that is not in P.

There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].

The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].

More about...