Home > Interactive proof system

This concept of computation as interaction between parties was suggested by Babai et al and Goldwasser et al. It has also been proven that the set of all languages recognizable by interaction (which is called IP) is equivalent to the set of all languages recognizable by a Turing machine using polynomial space.

Usually, in an interactive proof system, the verifier is allowed to use private coin tosses. When the verifier's coin tosses are constrained to be public (i.e., known to the prover too), the proof system is called an Arthur-Merlin protocol. This notion was introduced by Babai et al. Later, Goldwasser and Sipser proved that the set of languages that have interactive proofs with private coins also have interactive proofs with public coins.