I recently finished yet another semester of school and suddenly have time on my hands. As a new initiative on my part, I will be making a new blog post every day of this summer till about the time I go back to school. That’s 3 months and ~91 blog posts, each on something that I find cool, and I hope you’ll find cool too.
Here we go!
Given a statement that needs to be proved, traditional proofs often follow the structure of presenting a set of implications, each of which follows logically one after another. To check that the proof is correct, every step must be verified.
Probabilistically checkable proofs (PCP) offer a different proof format. Explained on a high level, many implications can lead to the same statement. Therefore, probabilistic checking is possible: one only needs to pick a certain random subset of implications that can lead to the statement and check that all the steps in the subset of implications are correct. The significance of probabilistically checkable proofs is that the verifier does not need to read and verify the entire proof to show with reasonable confidence that the proof is correct.
Therefore, the runtime of verification is significantly decreased.
Stating the process of verification more formally, given a PCP of bits represented by the binary string , a verifier only needs to query bits using an oracle to determine the validity of the proof. (The verifier is assumed to have oracle access, which means that the verifier can ask for the -th bit and an oracle would subsequently return .)
Then, we can move on to a few more definitions to describe a PCP verifier.
A gap is defined to be a decimal where .
A PCP verifier uses a probabilistic algorithm to make queries on a proof and decides whether to accept or reject the proof based on the queries, for a given assertion .
The completeness of a PCP verifier is given a true , there exists a proof such that every iteration of the PCP verifier algorithm will return “accept.”
The soundness of a PCP verifier is given a false and gap , for every proof the probability that the verifier algorithm returns “accept” is at most .
We will see in later blog posts the application of these definitions on a few example PCPs.
Now the logical question is whether any proof can be rewritten to be a probabilistically checkable proof. The PCP Theorem states that any decision problem in NP has a PCP. I will write more about the proof, its history, and its applications tomorrow.