Same as IP, except that now the verifier can exchange messages with many provers, not just one. The provers cannot communicate with each other during the execution of the protocol, so the verifier can "cross-check" their assertions (as with suspects in separate interrogation rooms).
Defined in [BGK+88].
Let MIP[k] be the class of decision problems for which a "yes" answer can be verified with k provers. Then for all k>2, MIP[k] = MIP[2] = MIP [BGK+88].
MIP equals NEXP [BFL91]; this is a famous non-relativizing result.
The class of decision problems solvable by an NEXP machine such that, given a "yes" instance, no more than an exponential number of computation paths accept.
Contained in MIP[NPFewEXP] (MIP where provers are not unbounded in computational power, but are limited to NPFewEXP) [AKS+94].
Alternatively, FewEXP can refer to the sparsity of accepting paths in a given instance. In [AKR+03], the authors show that the conjectures "FewEXP search instances are EXP-solvable" and "FewEXP decision instances are EXP/poly-solvable" are equivalent. That is, for all NEXP machines , the following conditions are equivalent:
The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,
Contains compIP [BG94] and Check [BK89].
Contained in MIP = NEXP [FRS88].
Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].
The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.
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].
Same as MIP, except that the provers can have non-signaling strategies.
MIPns with two provers is equal to PSPACE [Ito10]. MIPns with polylogarithmically many provers is equal to EXP [KRR13].
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].
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 class of decision problems such that a "yes" answer can be verified by a probabilistically checkable proof, as follows.
The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a proof (which might be exponentially long), but can query only O(q(n)) bits of the proof.
Then we require the following:
Defined in [AS98].
By definition NP = PCP(0,poly(n)).
MIP = PCP(poly(n),poly(n)).
PCP(r(n),q(n)) is contained in NTIME(2O(r(n))q(n) + poly(n)).
NP = PCP(log n, log n) [AS98].
In fact, NP = PCP(log n, 1) [ALM+98]!
On the other hand, if NP is contained in PCP(o(log n), o(log n)), then P = NP [FGL+91].
Also, even though there exists an oracle relative to which NP = EXP [Hel84], if we could show there exists an oracle relative to which PCP(log n, 1) = EXP, then we'd have proved P not equal to NP [For94].
Another weird oracle fact: since NP does not equal NEXP [SFM78], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [HCC+92].
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.
