Interactive proof system
The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not.
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 are AM and IP.
Soundness of the proof system refers to the property that no prover can make the verifier accept for the wrong statement
The upper bound of this probability is referred to as the soundness error of a proof system.
As long as the soundness error is bounded by a polynomial fraction of the potential running time of the verifier (i.e.
One approach, by László Babai, who published "Trading group theory for randomness",[2] defined the Arthur–Merlin (AM) class hierarchy.
In this presentation, Arthur (the verifier) is a 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.
In the same conference where Babai defined his proof system for MA, Shafi Goldwasser, Silvio Micali and Charles Rackoff[3] 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.
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 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 problem is in NP, since the proof certificate is the permutation which makes the graphs equal.
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.
[9][10] Not only can interactive proof systems solve problems not believed to be in NP, but under assumptions about the existence of one-way functions, a prover can convince the verifier of the solution without ever giving the verifier information about the solution.
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.
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.
Adding a constant number of additional provers beyond two does not enable recognition of any more languages.
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.
[12] 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.
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).
, the class of polynomial-time machines with access to polynomially many random bits is co-RP.
bits of the proof certificate to look at, this won't make any difference as long as it has
[15] Furthermore, the PCP theorem asserts that the number of proof accesses can be brought all the way down to a constant.
