The PCP theorem for dummies,
Let's see an algorithmic point of view on the PCP theorem.
Consider a NPcomplete decision problem (a language
). Then, there is an algorithm as follows:
 
 


random bits 


 
 


Instance 




 
 

(at most
times) 
query



Answer


 

 
 


 
 

 
 
 
 
 

where the algorithm works in polynomial time,
and
 if
, the answer is Yes with probability one, for at least one
.
 if
, then for all
, the answer is No with probability
.
is termed the proof. The algorithm is termed the verifier.
I can solve a difficult problem^{1} efficiently^{2}
if I have two friends:
 a logarithmic number of random bits;
 a polynomialsize oracle, from which I will only read finitely many bits;
and
 if my friend the oracle does a good job, I will accept all yesentries;
 whenever he tries to make me wrong, I will never accept a noentry with probability more than
.
More intuitively: I have only to check finitely many bits of a proof, if I have a random generator.
The fact that this algorithm can be simulated by a nondeterministic Turing machine
in polynomial time (without
) is as follows:
 Loop: try all possible random bits (polynomial number of possible vectors).
 In each iteration of the loop: nondeterministically try all possible proof bits (constant number of possible sequences of
bits).
The converse is very hard and is the main part of the PCPtheorem.
If it was true, then
would hold
For fun, let's try to prove the (false if
) statement according to which
.
For that, let's build a (dishonest) polynomialtime Turing machine which decides a given language in
.
Consider a language in
.
The natural machine for proving this (false) statement on input
is as follows:
 For each vector
of
bits:
 Initialize
.
 For each vector
of
bits
 simulate the algorithm above on
assuming that the random bits are
and the answer to the
(distinct) query is
.
 if the result is yes, then
 Reply true if and only if there is one
such that
.
This algorithm is polynomial.
Question: find why this reasonning is false.
Answer: in the machine above, we check that
With probability
, for at least one
the answer is yes.
whereas we are interested in
For at least one
, with probability
the answer is yes.
By choosing the vector
of answers to queries independently of the position, we move
the "for at least one
" from before "with probability 1" to after "with probability 1".
Our machine does not test if there is a
(a proof) which works with probability
; it tests if with probability
, an adversary which knows our random bits can choose a proof that will mislead the verifyer!
This shows the strong and nontrivial importance of the randomization in the PCP theorem; the reasonning above would be true for deterministic algorithms, leading to
! The
is therefore necessary in
(unless
!).
The PCP theorem for dummies,
This document was generated using the
LaTeX2HTML translator Version 200221 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html split 0 pcp.tex
The translation was initiated by Olivier Teytaud on 20071003
Footnotes
 ... problem^{1}
 NPhard problem
 ... efficiently^{2}
 in polynomial time
Olivier Teytaud
20071003