PCP theorem

The PCP theorem, proven in the early 1990's, states that every NP problem has a very efficient probabilistically checkable proof system. This theorem has the following astonishing consequence: every proof for any statement in propositional logic can be formalized, so that one can check whether it is correct or not by only reading a constant number of letters from it! More precisely, one can choose which letters of the proof to look at using a certain random process, and then after reading them, one can declare the proof "correct" or "false". In this process a correct proof will always be declared as such, while any attempt to prove a wrong statement will be declared false with probability at least 1/2 (repeating this process several times can detect a false proof with arbitrarily high probability).

Theorem

The formal statement of the theorem is

NP=PCP(O(\log n),O(1)).\

Proof.

The proof is in two parts:

Lemma 1

PCP(O(\log n),O(1))\subseteq NP.\,

Let $L\in PCP(O(\log n),O(1))$ . By definition there exists a probabilistic verifier $V$ such that

If $x\in L$ then there is a proof $P$ for which the probability that $V$ accepts $x$ and $P$ is exactly $1$ .
If $x\not \in L$ then there is no proof $P$ for which the probability that $V$ accepts $x$ and $P$ is $\geq 1/2$ .

We need to show that $L\in NP$ . This can be proven by Derandomization since we can construct a deterministic verifier $V'$ for $L$ .

On input $x$ and $P$ , the verifier $V'$ works as follows.

For every possible random string $r$ $r$ of length at most $O(\log n)$ $O(\log n)$
1. $V'$ runs $V$ using $r$ as random string
$V'$ accepts if and only if all of $V$ s runs accepted

$V'$ runs in polynomial time since enumerating all such small random strings can be done in polynomial time and $V'$ runs in polynomial time. Furthermore, $V'$ has the properties

If $x\in L$ then there is a proof $P$ for which all runs of $V$ accept, so $V'$ accepts.
If $x\not \in L$ then there is no proof $P$ for which all runs of $V$ accept, so $V'$ rejects.

This means that $V'$ is a deterministic polynomial-time verifier for $L$ and therefore $L\in NP$ .

Lemma 2

NP\subseteq PCP(O(\log n),O(1))

.

This can be proven by proving a harder result: demonstrating that the language (SAT, ε-UNSAT), an NP-complete language, is in PCP (O(log n), O(1)) and that

L\in PCP(O(\log n),O(1))

if and only if

L

can be reduced to

(SAT,\epsilon -UNSAT).

For $(SAT,\epsilon -UNSAT)\in PCP(O(\log n),O(1))$ , let the proof that the PCP system reads be a satisfying assignment for the input 3-CNF, Φ. The system chooses $O(1/\epsilon )$ clauses of the proof to check if they are truly satisfied. Note that only $\log n$ random bits are needed to choose one of $n$ clauses, and thus only $O(\log n/\epsilon )=O(\log n)$ total random bits are needed. (Remember that ε is a constant.) For each clause to be checked, only 3 bits need to be read, and thus only $O(3/\epsilon )=O(1)$ (a constant number) of bits from the proof need to be read. The system rejects if any of the clauses are not satisfied. If Φ is satisfiable, then there exists a proof (a truly satisfying assignment) that the system will always accept. If Φ is not in (SAT, ε-UNSAT), this means that an ε fraction of the clauses is not satisfiable. The probability that this system will accept in this case is $(1-\epsilon )^{1/\epsilon }\leq 1/e<1/2$ . Therefore, $(SAT,\epsilon -UNSAT)\in PCP(O(\log n),O(1))$ .

Since (SAT, ε-UNSAT) is NP-complete, this is enough to conclude that $NP\subseteq PCP(O(\log n),O(1))$ .

Corollary 1

The PCP Theorem implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is NP-hard. Therefore no good approximation algorithm exists for this language unless P=NP.

Additional resources