PCP – Probabilistically Checkable Proofs
Overview
Imagine that Peggy has a long proof of some mathematical theorem, and Victor wants to verify it. A priori, this would require Victor to actually read every line of the proof. As anyone who has experience grading students knows, that’s a whole lot of work. A lazy grader might try to save time by only “spot checking” a small number of lines of the proof. However, it would be really easy to cheat such a grader: all you have to do is make a single wrong step somewhere and hope that particular step is not one of the ones examined by Victor.
A probabilistically checkable proof is a way to try to circumvent this issue. It provides a protocol where Peggy can format her proof such that Victor can get high-probability confidence of its confidence by only checking bits of the proof at random, for some absolute constant . This result is one part of the PCP theorem which is super famous.
The purpose of this post is to give a high level summary of the ideas that go into the protocol and convince you that the result is possible, because at first glance it seems absurd that a single universal constant is going to be enough. In fact, we won’t get all the way down to an absolute constant , but we will get down to a number of bits polylogarithmic in and , which is already very very surprising. The full PCP theorem does some more technical optimizations to get down to a constant, but those won’t be so important for us.
The post is divided into several sections.
-
Explanation of the general sum-check protocol, which is super powerful and used in many other contexts. (Quote from Justin Thaler: “when designing an efficient interactive proof system, there is only one hammer you need to have in your toolbox: the sum-check protocol of Lund, Fortnow, Karloff, and Nisan.”)
-
A description of low-degree testing, which lets you take a giant table of values and verify whether it’s a multivariable polynomial.
-
Statement of the Quad-SAT problem, which is the NP-complete problem which we’ll be using for this post: an instance of Quad-SAT is a bunch of quadratic equations in multiple variables that one wants to find a solution to.
-
Staple together everything above to get a toy PCP protocol.
-
An improvement to reduce proof length using error-correcting codes.
The first three sections commute.
As this is a big picture overview, we will generally not prove things; detailed proofs are usually spelled out in textbooks, and this is not a textbook.