# The PCP theorem for dummies,

## Contents

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

# The model

 random bits

 Instance

 Algorithm

 Yes or No

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.

# An intuitive point of view

I can solve a difficult problem1 efficiently2 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 .

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

# Why

The fact that this algorithm can be simulated by a non-deterministic 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: non-deterministically try all possible proof bits (constant number of possible sequences of bits).

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

# Why is not trivial, and hopefully false

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) polynomial-time 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 non-trivial 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 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

Olivier Teytaud 2007-10-03