Interactive Proof System - MIP

MIP

One goal of IP's designers was to create the most powerful possible interactive proof system, and at first it seems like it cannot be made more powerful without making the verifier more powerful and so impractical. Goldwasser et al. overcame this in their 1988 "Multi prover interactive proofs: How to remove intractability assumptions", which defines a variant of IP called MIP in which there are two independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier into accepting a string not in the language if there is another prover it can double-check with.

In fact, this is so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. NEXPTIME contains PSPACE, and is believed to strictly contain PSPACE. Adding a constant number of additional provers beyond two does not enable recognition of any more languages. This result paved the way for the celebrated PCP theorem, which can be considered to be a "scaled-down" version of this theorem.

MIP also has the helpful property that zero-knowledge proofs for every language in NP can be described without the assumption of one-way functions that IP must make. This has bearing on the design of provably unbreakable cryptographic algorithms. Moreover, a MIP protocol can recognize all languages in IP in only a constant number of rounds, and if a third prover is added, it can recognize all languages in NEXPTIME in a constant number of rounds, showing again its power over IP.