A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Interactive proofs generalize NP verification by allowing multiple rounds of interaction between a computationally unbounded prover and a polynomial-time probabilistic verifier. The class IP (Interactive Polynomial-time) equals PSPACE (Shamir 1990), dramatically exceeding NP. Key results: IP contains problems like graph non-isomorphism (not known to be in NP). Arthur-Merlin protocols (public-coin) are equivalent in power to general interactive proofs. The Fiat-Shamir heuristic converts interactive proofs into non-interactive ones by replacing the verifier's random challenges with hash function outputs, enabling practical ZK proofs and signatures.
An interactive proof system is a protocol between two parties: a computationally unbounded prover trying to convince a polynomial-time probabilistic verifier that a statement is true. Unlike NP, where the prover sends a single static witness, interactive proofs allow multiple rounds of back-and-forth communication, with the verifier sending random challenges and the prover responding. Completeness requires an honest prover to convince the verifier; soundness requires that no cheating prover can convince the verifier of a false statement except with negligible probability.
The power of interaction far exceeds static witnesses. NP captures statements with short proofs ("this graph is 3-colorable" — here's a coloring). But some natural statements seem to lack short proofs — for instance, "these two graphs are NOT isomorphic" or "this formula has exactly 17 satisfying assignments." Interactive proofs handle these by letting the verifier probe the prover adaptively. The graph non-isomorphism protocol is a beautiful example: the verifier secretly picks one of the two graphs, randomly permutes it, and asks the prover to identify the source. If the graphs are truly different, the prover (being computationally unbounded) can always identify which graph was permuted. If they are isomorphic, no prover can distinguish them — every permutation of one is also a permutation of the other.
The culminating result is IP = PSPACE (Shamir, 1990): the class of problems with interactive proofs is exactly PSPACE, the class of problems solvable with polynomial memory. This is a massive expansion beyond NP — PSPACE contains all of NP, coNP, the polynomial hierarchy, and much more. The proof works by giving an interactive proof for QBF (quantified Boolean formulas, the canonical PSPACE-complete problem) using arithmetization (converting Boolean logic into polynomial algebra over finite fields) and the sum-check protocol (an interactive method for verifying that the sum of a multivariate polynomial over all binary inputs equals a claimed value).
The Fiat-Shamir heuristic bridges theory and practice by converting interactive proofs into non-interactive ones. The idea is simple: replace the verifier's random challenges with the output of a hash function applied to the transcript so far. Since the prover cannot control the hash output, it serves as a surrogate for verifier randomness. This transformation, proven secure in the random oracle model (where the hash is idealized as a truly random function), is the basis of Schnorr signatures, many zk-SNARKs, and the non-interactive ZK proofs used in blockchain systems. The practical importance is enormous: non-interactive proofs can be verified by anyone at any time, without real-time communication with the prover, enabling offline verification and public verifiability.