Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.
Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP.
MIP* contains NEXP [IV12]. By contrast, MIP, the corresponding class without entanglement, equals NEXP (and even MIP[2,1] with two provers and one round equals NEXP).
Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].
MIP*[2,1] contains XOR-MIP*[2,1].
In 2012 it was shown that QMIP = MIP* [RUV12]
In 2020 it was shown that MIP* = RE [JNVWY20].
Nondeterministic exponential time (i.e. NTIME(2p(n)) for p a polynomial).
Equals MIP [BFL91] (but not relative to all oracles).
NEXP is in P/poly if and only if NEXP = MA [IKW01].
[KI02] show the following:
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].
The quantum generalization of MIP, and the multi-prover generalization of QIP.
A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.
Defined in [KM02].
Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].
QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.
Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.
Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.
XOR-MIP*[2,1] is contained in NEXP [CHT+04].
XOR-MIP*[2,1] is contained in QIP[2] [Weh06]