Probabilistically Checkable Proof (PCP)

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  b bits represented by the binary string  \pi = \langle \pi[1] ... \pi[l] \rangle \in \left\{0,1\right\}^l , a verifier only needs to query  q 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  i -th bit and an oracle would subsequently return  \pi[i] .)

Then, we can move on to a few more definitions to describe a PCP verifier.

A gap  \epsilon(n) is defined to be a decimal where  0 \leq \epsilon(n) \leq 1 .

A PCP verifier uses a probabilistic algorithm to make  q queries on a proof  \pi and decides whether to accept or reject the proof based on the queries, for a given assertion  A .

The completeness of a PCP verifier is given a true  A , there exists a proof  \pi such that every iteration of the PCP verifier algorithm will return “accept.”

The soundness of a PCP verifier is given a false  A and gap  \epsilon(n) , for every proof  \pi the probability that the verifier algorithm returns “accept” is at most  1 - \epsilon(n) .

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.

This entry was posted in Complexity and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s