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

Contents

• The model
• An intuitive point of view
• Why $PCP(O(\log(n)),O(1))\subset NP$
• Why $PCP(O(\log(n)),O(1))\subset P$ is not trivial, and hopefully false

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

• if $x\in L$ , the answer is Yes with probability one, for at least one $P$ .
• if $x\not\in L$ , then for all $P$ , the answer is No with probability $>\frac12$ .

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

An intuitive point of view

I can solve a difficult problem¹ efficiently² if I have two friends:

• a logarithmic number of random bits;
• a polynomial-size oracle, from which I will only read finitely many bits;

and

• if my friend the oracle does a good job, I will accept all yes-entries;
• whenever he tries to make me wrong, I will never accept a no-entry with probability more than $\frac12$ .

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:

• Loop: try all possible random bits (polynomial number of possible vectors).
• In each iteration of the loop: non-deterministically try all possible proof bits (constant number of possible sequences of $K$ bits).

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:

• For each vector $v$ of $k$ bits:
  • Initialize $r_v=0$ .
  • For each vector $w$ of $c\log(n)$ bits
    • simulate the algorithm above on $x$ assuming that the random bits are $w$ and the answer to the $i^{th}$ (distinct) query is $v_i$ .
    • if the result is yes, then $r_{v}=r_v+1$
• Reply true if and only if there is one $v$ such that $r_v=2^{c\log(n)}$ .

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

... problem¹

NP-hard problem

... efficiently²

in polynomial time