Editing Interactive proof system (section)

== Classes of interactive proofs ==

=== NP ===

The complexity class [[NP (complexity)|NP]] may be viewed as a very simple proof system. In this system, the verifier is a deterministic, polynomial-time machine (a [[P (complexity)|P]] machine). The protocol is:
* The prover looks at the input and computes the solution using its unlimited power and returns a polynomial-size proof certificate.
* The verifier verifies that the certificate is valid in deterministic polynomial time. If it is valid, it accepts; otherwise, it rejects.

In the case where a valid proof certificate exists, the prover is always able to make the verifier accept by giving it that certificate. In the case where there is no valid proof certificate, however, the input is not in the language, and no prover, however malicious it is, can convince the verifier otherwise, because any proof certificate will be rejected.

=== Arthur–Merlin and Merlin–Arthur protocols ===
{{main|Arthur–Merlin protocol}}
Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived (in the context of complexity theory) by two independent groups of researchers. One approach, by  [[László Babai]], who published "Trading group theory for randomness",<ref>László Babai. [http://portal.acm.org/citation.cfm?id=22192 Trading group theory for randomness]. ''Proceedings of the Seventeenth Annual Symposium on the Theory of Computing'', ACM. 1985.</ref> defined the ''Arthur–Merlin'' ('''AM''') class hierarchy. In this presentation, Arthur (the verifier) is a [[probabilistic Turing machine|probabilistic]], polynomial-time machine, while Merlin (the prover) has unbounded resources.

The class '''MA''' in particular is a simple generalization of the NP interaction above in which the verifier is probabilistic instead of deterministic. Also, instead of requiring that the verifier always accept valid certificates and reject invalid certificates, it is more lenient:
* '''Completeness:''' if the string is in the language, the prover must be able to give a certificate such that the verifier will accept with probability at least 2/3 (depending on the verifier's random choices).
* '''Soundness:''' if the string is not in the language, no prover, however malicious, will be able to convince the verifier to accept the string with probability exceeding 1/3.

This machine is potentially more powerful than an ordinary NP [[interaction protocol]], and the certificates are no less practical to verify, since '''BPP''' algorithms are considered as abstracting practical computation (see [[Bounded-error probabilistic polynomial|BPP]]).

=== Public coin protocol versus private coin protocol ===

In a ''public coin'' protocol, the random choices made by the verifier are made public. They remain private in a private coin protocol.

In the same conference where Babai defined his proof system for '''MA''', [[Shafi Goldwasser]], [[Silvio Micali]] and [[Charles Rackoff]]<ref>{{Cite journal | last1=Goldwasser | first1=S. | last2=Micali | first2=S. | last3=Rackoff | first3=C. | title=The knowledge complexity of interactive proof systems | url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf | year=1989 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=18 | issue=1 | pages=186–208 | doi=10.1137/0218012 }} [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract] {{Webarchive|url=https://web.archive.org/web/20060623020231/http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf |date=2006-06-23 }}</ref> published a paper defining the interactive proof system '''IP'''[''f''(''n'')]. This has the same machines as the '''MA''' protocol, except that ''f''(''n'') ''rounds'' are allowed for an input of size ''n''. In each round, the verifier performs computation and passes a message to the prover, and the prover performs computation and passes information back to the verifier. At the end the verifier must make its decision. For example, in an '''IP'''[3] protocol, the sequence would be VPVPVPV, where V is a verifier turn and P is a prover turn.

In Arthur–Merlin protocols, Babai defined a similar class '''AM'''[''f''(''n'')] which allowed ''f''(''n'') rounds, but he put one extra condition on the machine: the verifier must show the prover all the random bits it uses in its computation. The result is that the verifier cannot "hide" anything from the prover, because the prover is powerful enough to simulate everything the verifier does if it knows what random bits it used. This is called a ''public coin'' protocol, because the random bits ("coin flips") are visible to both machines. The '''IP''' approach is called a ''private coin'' protocol by contrast.

The essential problem with public coins is that if the prover wishes to maliciously convince the verifier to accept a string which is not in the language, it seems like the verifier might be able to thwart its plans if it can hide its internal state from it. This was a primary motivation in defining the '''IP''' proof systems.

In 1986, Goldwasser and [[Michael Sipser|Sipser]]<ref>Shafi Goldwasser and Michael Sipser. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf Private coins versus public coins in interactive proof systems] {{Webarchive|url=https://web.archive.org/web/20050127045423/http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf |date=2005-01-27 }}. ''Proceedings of ACM STOC'86'', pp. 58–68. 1986.</ref>  showed, perhaps surprisingly, that the verifier's ability to hide coin flips from the prover does it little good after all, in that an Arthur–Merlin public coin protocol with only two more rounds can recognize all the same languages. The result is that public-coin and private-coin protocols are roughly equivalent.  In fact, as Babai shows in 1988, '''AM'''[''k'']='''AM''' for all constant ''k'', so the '''IP'''[''k''] have no advantage over '''AM'''.<ref>László Babai and [[Shlomo Moran]]. [http://portal.acm.org/citation.cfm?id=49987 Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes]. ''Journal of Computer and System Sciences'', 36: p.254–276. 1988.</ref>

To demonstrate the power of these classes, consider the [[graph isomorphism problem]], the problem of determining whether it is possible to permute the vertices of one graph so that it is identical to another graph. This problem is in '''NP''', since the proof certificate is the permutation which makes the graphs equal. It turns out that the 
[[complement (complexity)|complement]] of the graph isomorphism problem, a co-'''NP''' problem not known to be in '''NP''', has an '''AM''' algorithm and the best way to see it is via a private coins algorithm.<ref name="O. Goldreich, S. Micali 1991">O. Goldreich, S. Micali, A. Wigderson. [http://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690–728. July 1991.</ref>

=== IP ===
{{main|IP (complexity)}}
Private coins may not be helpful, but more rounds of interaction are helpful. If we allow the probabilistic verifier machine and the all-powerful prover to interact for a polynomial number of rounds, we get the class of problems called '''IP'''.
In 1992, [[Adi Shamir]] revealed in one of the central results of complexity theory that '''IP''' equals '''[[PSPACE]]''', the class of problems solvable by an ordinary [[deterministic Turing machine]] in polynomial space.<ref>Adi Shamir. [http://portal.acm.org/citation.cfm?doid=146585.146609 IP = PSPACE]. ''Journal of the ACM'', volume 39, issue 4, p.869–877. October 1992.</ref>

=== QIP ===
{{main|QIP (complexity)}}
If we allow the elements of the system to use [[quantum computation]], the system is called a '''quantum interactive proof system''', and the corresponding complexity class is called '''QIP'''.<ref>{{cite arXiv|eprint=1012.4427v2|author1=Tsuyoshi Ito|author2=Hirotada Kobayashi|author3=John Watrous|title=Quantum interactive proofs with weak error bounds|class=quant-ph|year=2010}}</ref> A series of results culminated in a 2010 breakthrough that '''QIP''' = '''PSPACE'''.<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | title=STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing | publisher=ACM | isbn=978-1-4503-0050-6 | year=2010 | chapter=QIP = PSPACE | pages=573–582}}</ref><ref>{{Cite journal | last1 = Aaronson | first1 = S. | doi = 10.1145/1859204.1859230 | title = QIP = PSPACE breakthrough | journal = Communications of the ACM | volume = 53 | issue = 12 | pages = 101 | year = 2010 | s2cid = 34380788 }}</ref>

=== Zero knowledge ===
{{main|Zero-knowledge proof}}
Not only can interactive proof systems solve problems not believed to be in '''NP''', but under assumptions about the existence of [[one-way function]]s, a prover can convince the verifier of the solution without ever giving the verifier information about the solution. This is important when the verifier cannot be trusted with the full solution.  At first it seems impossible that the verifier could be convinced that there is a solution when the verifier has not seen a certificate, but such proofs, known as [[zero-knowledge proof]]s are in fact believed to exist for all problems in '''NP''' and are valuable in [[cryptography]]. Zero-knowledge proofs were first mentioned in the original 1985 paper on '''IP''' by Goldwasser, Micali and Rackoff for specific number theoretic languages. The extent of their power was however shown by [[Oded Goldreich]], [[Silvio Micali]] and [[Avi Wigderson]].<ref name="O. Goldreich, S. Micali 1991"/> for all of '''NP''', and this was first extended by [[Russell Impagliazzo]] and [[Moti Yung]] to all '''IP'''.<ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [https://link.springer.com/chapter/10.1007%2F3-540-48184-2_4]</ref>

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

=== PCP ===
{{main|Probabilistically checkable proof}}
While the designers of '''IP''' considered generalizations of Babai's interactive proof systems, others considered restrictions. A very useful interactive proof system is '''PCP'''(''f''(''n''), ''g''(''n'')), which is a restriction of '''MA''' where Arthur can only use ''f''(''n'') random bits and can only examine ''g''(''n'') bits of the proof certificate sent by Merlin (essentially using [[random access]]).

There are a number of easy-to-prove results about various '''PCP''' classes. {{tmath|1=\mathsf{PCP}(0,\mathsf{poly})}}, the class of polynomial-time machines with no randomness but access to a certificate,  is just '''NP'''. {{tmath|1=\mathsf{PCP}(\mathsf{poly},0)}}, the class of polynomial-time machines with access to polynomially many random bits is '''co-[[RP (complexity)|RP]]'''. Arora and Safra's first major result was that {{tmath|1= \mathsf{PCP}(\log, \log) = \mathsf{NP} }}; put another way, if the verifier in the '''NP''' protocol is constrained to choose only {{tmath|O(\log n)}} bits of the proof certificate to look at, this won't make any difference as long as it has {{tmath|O(\log n)}} random bits to use.<ref>Sanjeev Arora and [[Shmuel Safra]]. [http://citeseer.ist.psu.edu/arora92probabilistic.html Probabilistic Checking of Proofs: A New Characterization of NP]. ''Journal of the ACM'', volume 45, issue 1, pp. 70–122. January 1998.</ref>

Furthermore, the [[PCP theorem]] asserts that the number of proof accesses can be brought all the way down to a constant. That is, {{tmath|1=\mathsf{NP} = \mathsf{PCP}(\log, O(1))}}.<ref>Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. [http://citeseer.ist.psu.edu/376426.html Proof Verification and the Hardness of Approximation Problems]. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.</ref> They used this valuable characterization of '''NP''' to prove that [[approximation algorithm]]s do not exist for the optimization versions of certain [[NP-complete]] problems unless [[P = NP]]. Such problems are now studied in the field known as [[hardness of approximation]].