In
computational complexity theory, the class
IP (which stands for Interactive Polynomial time) is the class of problems solvable by an
interactive proof system. The concept of an interactive proof system was first introduced by
Shafi Goldwasser,
Silvio Micali, and
Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover,
P, which presents a proof that a given string
n is a member of some
language, and a verifier,
V, that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of
n. These two machines exchange a polynomial number,
p(
n), of messages and once the interaction is completed, the verifier must decide whether or not
n is in the language, with only a 1/3 chance of error. (So any language in
BPP is in
IP, since then the verifier could simply ignore the prover and make the decision on its own.)