Incomputational complexity theory, aninteractive proof system is anabstract machine that modelscomputation as the exchange of messages between two parties: aprover and averifier. The parties interact by exchanging messages in order to ascertain whether a givenstring belongs to alanguage or not. The prover is assumed to possess unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

All interactive proof systems have two requirements:

• Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true.
• Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some smallprobability.

The specific nature of the system, and so thecomplexity class of languages it can recognize, depends on what sort of bounds are put on the verifier, as well as what abilities it is given—for example, most interactive proof systems depend critically on the verifier's ability to make random choices. It also depends on the nature of the messages exchanged—how many and what they can contain. Interactive proof systems have been found to have some important implications for traditional complexity classes defined using only one machine. The main complexity classes describing interactive proof systems areAM andIP.

Every interactive proof system defines aformal language of strings. Often an interactive proof system is designed with theintention of being a system for a particular language${\displaystyle L}$.Soundness of the proof system refers to the property that no prover can make the verifier accept a string${\displaystyle y}$ when in fact${\displaystyle y\notin L}$ except with some small probability. The upper bound of this probability is referred to as thesoundness error of a proof system. More formally, for every prover${\displaystyle (\tilde{\mathcal{P}})}$, and every${\displaystyle y\notin L}$:

for some${\displaystyle ϵ\ll 1}$.As long as the soundness error is bounded by a polynomial fraction of the potential running time of the verifier (i.e.${\displaystyle ϵ\le 1/\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(|y|)}$), it is always possible to amplify soundness until the soundness error becomes anegligible function of the running time of the verifier. This is achieved by repeating the proof and accepting only if all proofs verify. After${\displaystyle \ell }$ repetitions, a soundness error${\displaystyle ϵ}$ will be reduced to${\displaystyle {ϵ}^{\ell }}$.^[1]

The complexity classNP may be viewed as a very simple proof system. In this system, the verifier is a deterministic, polynomial-time machine (aP 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.

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, byLászló Babai, who published "Trading group theory for randomness",^[2] defined theArthur–Merlin (AM) class hierarchy. In this presentation, Arthur (the verifier) is aprobabilistic, polynomial-time machine, while Merlin (the prover) has unbounded resources.

The classMA 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 NPinteraction protocol, but the certificates are no less practical to verify, sinceBPP algorithms are considered as abstracting practical computation (seeBPP).

In apublic 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 forMA,Shafi Goldwasser,Silvio Micali andCharles Rackoff^[3] published a paper defining the interactive proof systemIP[f(n)]. This has the same machines as theMA protocol, except thatf(n)rounds are allowed for an input of sizen. 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 anIP[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 classAM[f(n)], which allowedf(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 apublic coin protocol, because the random bits ("coin flips") are visible to both machines. TheIP approach is called aprivate 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 that 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 theIP proof systems.

In 1986, Goldwasser andSipser^[4] 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 showed in 1988,AM[k]=AM for all constantk, so theIP[k] have no advantage overAM.^[5]

To demonstrate the power of these classes, consider thegraph 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 inNP, since the proof certificate is the permutation that makes the graphs equal. It turns out that thecomplement of the graph isomorphism problem, a co-NP problem not known to be inNP, has anAM algorithm and the best way to see it is via a private coins algorithm.^[6]

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 calledIP.In 1992,Adi Shamir revealed in one of the central results of complexity theory thatIP equalsPSPACE, the class of problems solvable by an ordinarydeterministic Turing machine in polynomial space.^[7]

If we allow the elements of the system to usequantum computation, the system is called aquantum interactive proof system, and the corresponding complexity class is calledQIP.^[8] A series of results culminated in a 2010 breakthrough thatQIP =PSPACE.^[9][10]

Not only can interactive proof systems solve problems not believed to be inNP, but under assumptions about the existence ofone-way functions, 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 aszero-knowledge proofs are in fact believed to exist for all problems inNP and are valuable incryptography. Zero-knowledge proofs were first mentioned in the original 1985 paper onIP by Goldwasser, Micali and Rackoff for specific number-theoretic languages. The extent of their power was however shown byOded Goldreich,Silvio Micali andAvi Wigderson for all ofNP,^[6] and this was first extended byRussell Impagliazzo andMoti Yung to all ofIP.^[11]

One goal ofIP'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 ofIP calledMIP in which there aretwo independent provers.^[12] 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 thatMIP =NEXPTIME, the class of all problems solvable by anondeterministic machine inexponential time, a very large class.^[13] 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 celebratedPCP 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 inNP can be described without the assumption of one-way functions thatIP must make. This has bearing on the design of provably unbreakable cryptographic algorithms.^[12] Moreover, anMIP protocol can recognize all languages inIP in only a constant number of rounds, and if a third prover is added, it can recognize all languages inNEXPTIME in a constant number of rounds, showing again its power overIP.

It is known that for any constantk, an MIP system withk provers and polynomially many rounds can be turned into an equivalent system with only 2 provers, and a constant number of rounds.^[14]

While the designers ofIP considered generalizations of Babai's interactive proof systems, others considered restrictions. A very useful interactive proof system isPCP(f(n),g(n)), which is a restriction ofMA where Arthur can only usef(n) random bits and can only examineg(n) bits of the proof certificate sent by Merlin (essentially usingrandom access).

There are a number of easy-to-prove results about variousPCP classes.⁠${\displaystyle \mathsf{P}\mathsf{C}\mathsf{P}(0,\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y})}$⁠, the class of polynomial-time machines with no randomness but access to a certificate, is justNP.⁠${\displaystyle \mathsf{P}\mathsf{C}\mathsf{P}(\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y},0)}$⁠, the class of polynomial-time machines with access to polynomially many random bits isco-RP. Arora and Safra's first major result was that⁠${\displaystyle \mathsf{P}\mathsf{C}\mathsf{P}(\log ,\log )=\mathsf{N}\mathsf{P}}$⁠; put another way, if the verifier in theNP protocol is constrained to choose only⁠${\displaystyle O(\log n)}$⁠ bits of the proof certificate to look at, this won't make any difference as long as it has⁠${\displaystyle O(\log n)}$⁠ random bits to use.^[15]

Furthermore, thePCP theorem asserts that the number of proof accesses can be brought all the way down to a constant. That is,⁠${\displaystyle \mathsf{N}\mathsf{P}=\mathsf{P}\mathsf{C}\mathsf{P}(\log ,O(1))}$⁠.^[16] They used this valuable characterization ofNP to prove thatapproximation algorithms do not exist for the optimization versions of certainNP-complete problems unlessP = NP. Such problems are now studied in the field known ashardness of approximation.

• Oracle machine
• Proof of knowledge

• Arora, Sanjeev; Barak, Boaz,"Complexity Theory: A Modern Approach", Cambridge University Press, March 2009.
• Michael Sipser (1997).Introduction to the Theory of Computation. PWS Publishing.ISBN 978-0-534-94728-6. Section 10.4: Interactive Proof Systems, pp. 354–366.
• Christos Papadimitriou (1993).Computational Complexity (1st ed.). Addison Wesley.ISBN 978-0-201-53082-7. Section 19.2: Games against nature and interactive protocols, pp. 469–480.

• Dexter Kozen.Interactive Proofs. CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
• Complexity Zoo:
  • MA,MA',MAEXP,MAE
  • AM,AMEXP,AM intersect co-AM,AM[polylog],coAM,BP•NP
  • QMA,QMA+,QMA(2),QMA_log,QMAM
  • IP,MIP,IPP,QIP,QIP(2),compIP,frIP
  • PCP(r(n),q(n))
• Larry Gonick. "Proof Positive?". A comic strip about interactive proof systems.

• Computational complexity theory

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata