Interactive Proof System

A powerful notion 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 novel notion 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.