|
The interactive proof system is a concept in computational complexity theory that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful, with unlimited computational resources while the verifier has bounded computation power. The verifier queries the prover a limited number of times and finds out whether the string belongs to the specified language or not.
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.
|
