Editing Interactive proof system (section)

=== 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.<ref name="M. Ben-or, Shafi Goldwasser 1988">M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf Multi prover interactive proofs: How to remove intractability assumptions]. ''Proceedings of the 20th ACM Symposium on Theory of Computing'', pp. 113–121. 1988.</ref> 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 Turing machine|nondeterministic]] machine in ''exponential time'', a very large class.<ref>{{Cite web |author1=László Babai |author2=L. Fortnow |author3=C. Lund |url=http://citeseer.ist.psu.edu/15039.html |title=Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity |url-status=dead |archive-url=https://web.archive.org/web/20070208015711/https://citeseer.ist.psu.edu/15039.html |archive-date=8 February 2007 |volume=1 |pages=3–40 |year=1991}}</ref> 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.<ref name="M. Ben-or, Shafi Goldwasser 1988"/> 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'''.

It is known that for any constant ''k'', a MIP system with ''k'' provers and polynomially many rounds can be turned into an equivalent system with only 2 provers, and a constant number of rounds.<ref>{{cite book |last1=Ben-Or |first1=Michael |last2=Goldwasser |first2=Shafi |last3=Kilian |first3=Joe |last4=Widgerson |first4=Avi |title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 |chapter=Multi-prover interactive proofs: How to remove intractability |date=1988 |pages=113–131 |doi=10.1145/62212.62223 |isbn=0897912640 |s2cid=11008365 |chapter-url=http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf |access-date=17 November 2022 |language=en|archive-date=13 July 2010|archive-url=https://web.archive.org/web/20100713035025/http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf}}</ref>