PCP theorem
- Their work
- Troy Lee wrote the proof of the PCP theorem in Lean, and a guide to reading it. His Lean follows the algebraic proof by Amireddy, Behera, Srinivasan, Sudan and Willumsgaard.
- My work
- With AI, I wrote three papers that explain his Lean proof: one through worked examples, one for specialists and one detailed account. In each paper, clicking a linked sentence opens the Lean lines it describes.
The PCP theorem says that any proof a computer can check quickly can be rewritten so that a checker reads only a fixed number of its bits, chosen at random. For a true claim the rewritten proof is always accepted, and every proof of a false claim is rejected at least half the time.
Limits: Lean compiled Lee’s proof. I made the three papers and their links to the Lean with AI. Neither Lee nor the authors of the algebraic proof have reviewed them, and nobody has compared each sentence with the Lean lines it links to.
Lean is a program that checks mathematical proofs.