The PCP theorem states that:

Every decision problem in NP has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

Can anyone give an intuitive explanation of how this can be done?



1 Answer 1


A detailed explanation can be found in many places. I'll to provide an intuitive one.

By Cook-Levin theorem, the Boolean satisfiability problem is NP-complete - ie. every decision problem in NP can be reduced to it. We will ask of our prover to supply the input and output of every gate in the circuit and consider this as the proof that $x\in L$.

If we were to stop there, then the prover could cheat by changing a single bit in his proof, which would require us to check a large (non-constant) number of bits in it. So we must ask something more from the prover. This something more will be the encoding of his proof using some (special) error-correcting code. Intuitively, this "smudges" the false bits onto a large number of bits in the code-word.

The verifier receives a word from the prover, there are 2 ways in which the prover might try and cheat, this word might not be a code-word in the chosen code, or it might be the encoding of something which isn't a proof. We'll examine the (slightly different) separation of cases of the word either being far from every codeword (a large number of bits must be changed to reach a codeword) or that it is close to codeword which isn't an encoding of a proof.

To be able to detect these we demand that our code has the following 2 properties: 1) locally checkable - we can, by reading a constant number of bits, detect w.h.p if a word is far from any codeword. 2) locally decodable - we can, by reading a constant number of bits, decode w.h.p a bit from the encoded word. (finding such codes is hard, hadamard has this properties but the code-word's size is exponential, RM codes have these properties as well (to a lesser degree) and they are the ones generally used.

So the verifier checks if the word is close to being a code-word (using 1), and if the test succeeds, picks a random gate and decodes it's outputs and output (using 2). this is sufficient to achieve constant query complexity and logarithmic randomness.

It should be mentioned that (Dinur) has a combinatorial proof of PCP which is quite different from what i've discribed, but her version is (for me, at least) less intuitive.

  • $\begingroup$ What do you mean by code words (do you have a link)? What does w.h.p mean? $\endgroup$
    – Casebash
    Aug 5, 2010 at 12:52
  • $\begingroup$ w.h.p = with high probability by code-word i mean a member of the code. i.e. if a code is some $C\subset F^{n}$ then any member of $C$ is a code-word $\endgroup$ Aug 5, 2010 at 14:29
  • 1
    $\begingroup$ casebash, "code" (as in error-correcting code) means a set of words (e.g, on a binary alphabet, or as in yohay's reply, the alphabet $F$ consisting of the elements of a finite field) satisfying some condition, such as checksum = 0. Usually the code has a single length for all words, so here $F^n$ means strings of length $n$ over finite field F. To check if it's in the code you calculate the checksum, or whatever other condition defines the code (like ISBN numbers in books). $\endgroup$
    – T..
    Aug 5, 2010 at 20:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .