Intutive explanation of the PCP Theorem

Solution 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.