next_inactive up previous


The PCP theorem for dummies,
$ NP= PCP(O(\log(n)),O(1))$



Contents

Let's see an algorithmic point of view on the PCP theorem. Consider a NP-complete decision problem (a language $ L\subset \{0,1\}*$ ). Then, there is an algorithm as follows:

The model

       
$ \log(\vert x\vert)$
random bits
$ \downarrow$
       
 
Instance
$ x$
 
 
 
$ \relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow $
 
 
 
Algorithm
 
 
 
(at most $ K$ times)
query $ q$
$ \relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow $
$ \leftarrow\joinrel\relbar\joinrel\relbar\joinrel\relbar $
Answer $ P(q)$
 
P
(read-only
tape)
 
 
        $ \downarrow$        
       
Yes or No
 
 
 
 
       

where the algorithm works in polynomial time, and

$ P$ is termed the proof. The algorithm is termed the verifier.

An intuitive point of view

I can solve a difficult problem1 efficiently2 if I have two friends:

and

More intuitively: I have only to check finitely many bits of a proof, if I have a random generator.

Why $ PCP(O(\log(n)),O(1))\subset NP$

The fact that this algorithm can be simulated by a non-deterministic Turing machine in polynomial time (without $ P$ ) is as follows:

The converse is very hard and is the main part of the PCP-theorem.

Why $ PCP(O(\log(n)),O(1))\subset P$ is not trivial, and hopefully false

If it was true, then $ P=NP$ would hold For fun, let's try to prove the (false if $ P\neq NP$ ) statement according to which $ PCP(O(\log(n)),O(1))\subset P$ .

For that, let's build a (dishonest) polynomial-time Turing machine which decides a given language in $ PCP(O(\log(n)),O(1))$ .

Consider a language in $ PCP(c\log(n),k)$ . The natural machine for proving this (false) statement on input $ x$ is as follows:

This algorithm is polynomial.

Question: find why this reasonning is false.

Answer: in the machine above, we check that

With probability $ 1$ , for at least one $ P$ the answer is yes.
whereas we are interested in
For at least one $ P$ , with probability $ 1$ the answer is yes.
By choosing the vector $ v$ of answers to queries independently of the position, we move the "for at least one $ P$ " from before "with probability 1" to after "with probability 1". Our machine does not test if there is a $ P$ (a proof) which works with probability $ 1$ ; it tests if with probability $ 1$ , an adversary which knows our random bits can choose a proof that will mislead the verifyer!

This shows the strong and non-trivial importance of the randomization in the PCP theorem; the reasonning above would be true for deterministic algorithms, leading to $ P=NP$ ! The $ \log(n)$ is therefore necessary in $ NP= PCP(O(\log(n)),O(1))$ (unless $ P=NP$ !).

About this document ...

The PCP theorem for dummies,
$ NP= PCP(O(\log(n)),O(1))$

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (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 2007-10-03


Footnotes

... problem1
NP-hard problem
... efficiently2
in polynomial time

next_inactive up previous
Olivier Teytaud 2007-10-03