IP = PSPACE

Picture two characters. Merlin is a wizard with unlimited power — he can compute anything, and he claims a certain statement is true. Arthur is an ordinary, suspicious king: he can flip coins and do a little arithmetic, nothing more. Merlin wants to convince Arthur. The catch is that Arthur does not trust Merlin one bit — the wizard might be lying to look clever.

The naive answer is "make Merlin write down the proof." But some true statements have no short proof Arthur can read — a complete proof might be astronomically large. So instead they talk. Arthur asks a question, Merlin answers, Arthur flips a coin and asks another, and so on for a few rounds. At the end Arthur must accept true claims and reject lies — and he is allowed a tiny chance of being fooled.

How much can a doubting king learn this way? The astonishing answer is: everything in PSPACE — the entire class of problems solvable with a reasonable amount of memory, even given unlimited time. Conversation plus a coin turns out to be shockingly powerful.

Here you are the verifier. A prover claims to know a secret degree-low polynomial and announces its total sum. You don't recompute the sum — you can't, it's too big. Instead you fold the claim into a single random point and force the prover to stay consistent. An honest prover always survives; a lying prover gets caught with high probability.

<p class="hint">{{hint}}</p>
<div class="rows">
  <div class="row"><span class="lbl">{{lbl_claim}}</span><b id="claim">&mdash;</b></div>
  <div class="row"><span class="lbl">{{lbl_challenge}}</span><b id="rval">&mdash;</b></div>
  <div class="row"><span class="lbl">{{lbl_eq}}</span><b id="eq">&mdash;</b></div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="honest" type="button">{{btn_honest}}</button>
  <button id="liar" type="button">{{btn_liar}}</button>
  <button id="batch" type="button" class="ghost">{{btn_batch}}</button>
</div>
<div class="tally" id="tally"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.rows { display: flex; flex-direction: column; gap: .35rem; margin: .4rem 0 .8rem; }
.row { display: flex; justify-content: space-between; align-items: center;
       background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .45rem .7rem; }
.lbl { font-size: .85rem; color: #1d3557; }
.row b { font: 700 15px ui-monospace, monospace; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.tally { font-size: .88rem; color: #444; margin-top: .6rem; line-height: 1.5; }

// Code not found

Notice the asymmetry. The prover does the heavy lifting; you only flip a coin and check one equation. Press Run honest prover and it always passes. Press Run lying prover — its first lie forces every later answer to be inconsistent, and your random point exposes it almost every time. Run it again and again: the cheat's success rate hugs the tiny theoretical bound, never your trust.

So what is the exact power of a coin-flipping verifier talking to an all-powerful prover?

• The class is called IP — interactive polynomial time: a probabilistic, polynomial-time verifier exchanges messages with an unbounded prover. True statements get accepted; false ones get rejected with high probability no matter how the prover cheats.
• The easy direction, IP ⊆ PSPACE, was known: a machine with polynomial memory can search over all the prover's possible strategies and compute Arthur's best acceptance probability.
• The hard direction, PSPACE ⊆ IP — solved. In 1990, Adi Shamir proved it (published 1992), finishing a line opened by Lund, Fortnow, Karloff and Nisan. The trick is arithmetization: rewrite a logical formula as a polynomial over a finite field, so a single random number can test a claim that ranges over exponentially many cases.
• Therefore IP = PSPACE — exactly. Interactive proofs are neither weaker nor stronger than polynomial space; they are the same class. This is a solved theorem, not an open question or a conjecture.

The punchline echoes P vs NP: a written proof you can re-read corresponds to NP, but a conversation with randomness reaches all the way to PSPACE — a class believed to be far larger. Talking, it turns out, beats writing.

"Convince a skeptic with a short conversation" turned out to be one of the most fertile ideas in modern computer science:

• Zero-knowledge proofs: the same interaction can convince you a statement is true while revealing nothing else — the foundation of privacy-preserving cryptography and many blockchain systems.
• Probabilistically checkable proofs (PCPs): the arithmetization toolkit grew into the PCP theorem, which underlies modern results on the hardness of approximation.
• Delegated and verifiable computation: a weak device (or a cloud customer) can have a powerful server do a computation and then check it with a tiny interactive proof — the heart of today's verifiable-computing and SNARK systems.
• Teaching the limits of proof: IP = PSPACE is the cleanest demonstration that randomness and interaction add real power over static, re-readable certificates.

Understand how Arthur catches Merlin and you've met the engine behind zero-knowledge cryptography and the whole verifiable-computation industry.

IP = PSPACE hides a beautiful surprise: a verifier who can do almost nothing — flip coins, check one equation — can be convinced of truths whose full proofs are too vast to ever read. The secret is not in the prover's power but in interaction plus randomness, and in arithmetization, which lets one random number stand in for a galaxy of cases.

So the next time you wonder whether a doubting skeptic could ever check a genius's work, remember Arthur and Merlin. With nothing but a coin and a few good questions, the skeptic verifies all of PSPACE — and never has to take the genius at his word. It is a settled theorem, and one of the most elegant in the field, sitting right beside P vs NP as a map of what proof can do.