# IP (complexity)

## From Wikipedia, the free encyclopedia

In computational complexity theory, the class **IP** (**interactive polynomial time**) is the class of problems solvable by an interactive proof system. It is equal to the class **PSPACE**. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs;[1] and the second, by Shamir, employed their technique to establish that IP=PSPACE.[2] The result is a famous example where the proof does not relativize.[3]

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.)