Class Description

NEEXP: Nondeterministic EEXP

Nondeterministic double-exponential time (i.e. NTIME(22p(n)) for p a polynomial).

Equals MIPEXP (unrelativized).

Linked From

EEXP: Double-Exponential Time

Equals DTIME(22p(n)) for p a polynomial.

Also known as 2-EXP.

Contains EE, and is contained in NEEXP.

More about...


MIPEXP: Exponential-Time Multi-Prover Interactive Proof

The exponential-time analogue of MIP.

In the unrelativized world, equals NEEXP.

There exists an oracle relative to which MIPEXP equals the intersection of P/poly, PNP, and ⊕P [BFT98].

More about...


NEE: Nondeterministic EE

Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).

If MAE = NEE then MA = NEXPcoNEXP [IKW01].

Contained in NEEXP.

More about...