Class Description

MIP: Multi-Prover Interactive Proof

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.

Linked From

FewEXP: NEXP With Few Witnesses

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:

  1. There exists an EXP machine such that if given a string , accepts and has exponentially bounded accepting paths, then produces one such path.
  2. There exists an EXP/poly machine which accepts a string if and only accepts.

More about...


frIP: Function-Restricted IP Proof Systems

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,

  1. If the answer is "yes" then DL(x) (D with oracle for L) accepts with probability at least 2/3.
  2. If the answer is "no" then DA(x) accepts with probability at most 1/3 for all oracles A.

Contains compIP [BG94] and Check [BK89].

Contained in MIP = NEXP [FRS88].

Assuming NEE is not contained in BPEE, NP (and indeed NPCoh) is not contained in frIP [BG94].

More about...


IP: Interactive Proof Systems

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:

  1. If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).
  2. If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.

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.

See also: MIP, QIP, MA, AM.

More about...


MIP*: MIP With Quantum Provers

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

More about...


MIPns: MIP with Non-Signaling Provers

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

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


NEXP: Nondeterministic EXP

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

Equals MIP [BFL91] (but not relative to all oracles).

NEXP is in MIP* [IV12].

NEXP is in P/poly if and only if NEXP = MA [IKW01].

[KI02] show the following:

Does not equal NP [SFM78].

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

More about...


PCP(r(n),q(n)): Probabilistically Checkable Proof

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:

  1. If the answer is "yes," there exists a proof such that the verifier accepts with certainty.
  2. If the answer is "no," then for all proofs the verifier rejects with probability at least 1/2 (over the choice of the O(r(n)) random bits).

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

More about...


QMIP: Quantum Multi-Prover Interactive Proofs

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.

More about...