Interactive Proof Systems (IP)
The class of decision problems for which a “yes” answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier’s algorithm, at the end:
- If the answer is “yes,” the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier’s random bits).
- If the answer is “no,” then however the prover behaves the verifier must reject with probability at least 2/3.
Known relationships
- IP = PSPACE — TODO citation