an interactive proof

An ordinary NP proof is a static document: a powerful prover writes down a certificate, and a quick verifier reads it and checks it once. An interactive proof replaces the one-way letter with a conversation. A computationally limited but skeptical verifier (allowed to flip coins) questions an all-powerful but untrusted prover back and forth, and at the end decides whether to be convinced. The magic is that this dialogue, with randomness, can establish far more than any static certificate could.

Here is how it works and what it guarantees. The prover is infinitely powerful but possibly lying; the verifier runs in polynomial time and asks random challenge questions. Two properties are required. Completeness: if the claim is true, an honest prover can always make the verifier accept. Soundness: if the claim is false, then no prover, however clever or adversarial, can fool the verifier into accepting except with tiny probability. Randomness is essential — the verifier's questions must be unpredictable, so a cheating prover cannot prepare answers in advance. The class IP is the set of statements provable this way.

The landmark theorem, one of the jewels of the field, is IP = PSPACE: interactive proofs can verify exactly the problems solvable with polynomial memory, an astonishingly large class far beyond NP. The intuition is that the verifier's unpredictable challenges force the prover to be consistent across an exponential space of possibilities it cannot precompute. This idea seeded two enormous offspring: zero-knowledge proofs (convince someone a statement is true while revealing nothing else) and the PCP theorem (proofs you can check by reading only a few random bits) — both reshaping modern cryptography and complexity.