In computational complexity theory, the class IP (interactive proof) 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.)
&sq=Qlik&lang=&file=File:Interactive_proof_(complexity).svg)
- ^ Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N. (1990). "Algebraic methods for interactive proof systems". Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press. pp. 2–10. doi:10.1109/fscs.1990.89518. ISBN 0-8186-2082-X. S2CID 32614901.
- ^ Shamir, Adi. "Ip= pspace." Journal of the ACM 39.4 (1992): 869-877.
- ^ Chang Richard; et al. (1994). "The random oracle hypothesis is false". Journal of Computer and System Sciences. 49 (1): 24–39. doi:10.1016/s0022-0000(05)80084-4.