Class Description

MIP_EXP: 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 MIP_EXP equals the intersection of P/poly, P^NP, and ⊕P [BFT98].

Linked From

NEEXP: Nondeterministic EEXP

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

Equals MIP_EXP (unrelativized).

More about...