Class Description

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

Linked From

NEEXP: Nondeterministic EEXP

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

Equals MIPEXP (unrelativized).

More about...