Computer science Randomized, circuit, counting and interactive complexity Theorem

PCP theorem

Builds on NP Probabilistic Turing machine Complexity class

Statement

Let $r, q \colon \N \to \N$ be functions. A probabilistically checkable proof verifier with randomness $r$ and query complexity $q$ for a language $L \subseteq \set{0,1}^*$ is a probabilistic polynomial-time algorithm $V$ with these properties. It gets an input $x$ of length $n$ and oracle access to a string $\pi$ , the proof. It uses at most $r(n)$ random bits, reads at most $q(n)$ bits of $\pi$ , and accepts or rejects.

Completeness: if $x \in L$ , there is a proof $\pi$ such that $V$ accepts $x$ with probability $1$ .
Soundness: if $x \notin L$ , then for every string $\pi$ , $V$ accepts $x$ with probability at most $1/2$ .

The class $\mathrm{PCP}(r, q)$ is the set of languages that have such a verifier.

Theorem. $\mathrm{NP} = \mathrm{PCP}(O(\log n), O(1)).$ That is, every language in NP has a verifier that uses $O(\log n)$ random bits and reads only a constant number of bits of the proof.

Remarks

The inclusion $\mathrm{PCP}(O(\log n), O(1)) \subseteq \mathrm{NP}$ is easy. With $O(\log n)$ random bits there are only polynomially many random strings. So a nondeterministic machine can guess the polynomially many proof bits that can ever be read, and then check all random strings. The hard inclusion was proved by Arora and Safra and by Arora, Lund, Motwani, Sudan and Szegedy, with algebraic tools such as low-degree tests. Dinur later gave a combinatorial proof by repeated gap amplification of constraint graphs.

The theorem is equivalent to a statement on approximation. There is a constant $\varepsilon > 0$ such that it is NP-hard to tell satisfiable 3-CNF formulas from those in which every assignment violates at least an $\varepsilon$ fraction of the clauses. So MAX-3SAT has no polynomial-time approximation scheme unless $\mathrm{P} = \mathrm{NP}$ .

The soundness constant $1/2$ is not essential: any constant in $(0, 1)$ gives the same class, by repeating the test a constant number of times.

Going deeper

For a student

The PCP theorem is the starting point of hardness of approximation. Its gap form says that approximating MAX-3SAT within some constant factor is as hard as solving it exactly. Reductions that preserve gaps then transfer this hardness to clique, vertex cover, set cover and many other problems. Refined versions, such as Håstad's three-query verifiers, give optimal constants for several problems. The unique games conjecture asks for a strengthening with a special kind of two-query test.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Complexity class concept
NP concept
Probabilistic Turing machine concept
PCP theorem statement

Tag	`WJXX7H6B6V`
URI	`m2://WJXX7H6B6V`
Kind	statement, theorem
Writing	W0 stub
MSC	68Q15, 68Q17, 68Q10
Status	This copy of the site has no build data. Run `m2 status WJXX7H6B6V`.
About	NP
Uses	NP, Probabilistic Turing machine, Complexity class
Same as	Wikidata Q1140200 Wikipedia PCP theorem
Changed	3 November 2026