PCP theorem
The pcp theorem is a central result in computational complexity theory characterizing the class NP through proofs that can be checked by reading only a constant number of their symbols. Here, “pcp” denotes a probabilistically checkable proof, rather than the chemically unrelated abbreviation used for phencyclidine.
In its standard form, the theorem states
[ \mathrm{NP}=\mathrm{PCP}\bigl(O(\log n),O(1)\bigr). ]
The first parameter bounds the number of random bits used by a polynomial-time verifier, while the second bounds the number of locations that the verifier reads from a purported proof. Consequently, every decision problem in NP has proofs whose validity can be tested with constant query complexity and logarithmic randomness, subject to a fixed upper bound on the probability of accepting an incorrect claim.
Formal statement
A language (L) belongs to (\mathrm{PCP}(r(n),q(n))) when there exists a randomized polynomial-time verifier (V) satisfying three conditions. Given an input (x) of length (n), the verifier uses at most (r(n)) random bits and reads at most (q(n)) symbols from a proof string (\pi). The positions examined by the verifier may depend on its random choices and on symbols already observed.
The completeness condition requires that whenever (x\in L), there exists a proof (\pi) for which
[ \Pr[V^\pi(x)=1]=1. ]
The soundness condition requires the existence of a constant (s<1) such that, whenever (x\notin L), every purported proof satisfies
[ \Pr[V^\pi(x)=1]\leq s. ]
The pcp theorem establishes that logarithmically many random bits and a constant number of queries suffice for every language possessing an ordinary polynomially verifiable certificate. The reverse containment follows directly because an NP machine can guess the entire proof, enumerate every random string used by the verifier, and evaluate the resulting acceptance probability in polynomial time. Since (O(\log n)) random bits generate only polynomially many random strings, this enumeration remains polynomially bounded.
The particular soundness constant is not essential to the characterization. Repetition lowers the probability of accepting a false proof while increasing the number of queries by a constant factor whenever the target soundness remains fixed. More elaborate forms of randomness-efficient error reduction provide related parameter tradeoffs.
Equivalent gap formulation
The theorem has an equivalent formulation involving constraint systems. There exists a constant (\varepsilon>0) for which it is NP-hard to distinguish between a satisfiable instance of a bounded-arity constraint satisfaction problem and an instance in which every assignment violates at least an (\varepsilon) fraction of the constraints.
For 3-satisfiability, the corresponding promise problem distinguishes formulas satisfying all clauses from formulas for which no assignment satisfies more than a (1-\varepsilon) fraction. A verifier chooses a constraint using logarithmically many random bits and queries the constant number of proof symbols associated with that constraint. Perfect satisfiability gives completeness, whereas the constant unsatisfied fraction supplies the soundness gap.
Conversely, the random choices and local predicates of a pcp verifier can be encoded as a polynomial-size constraint system. Each possible random string produces a local condition involving only the queried proof symbols. The verifier’s rejection probability then becomes the fraction of corresponding conditions violated by the encoded assignment.
This equivalence connects proof verification with the theory of approximation algorithms. If a polynomial-time algorithm could approximate certain optimization problems beyond the gap supplied by the theorem, it could distinguish the two cases and thereby decide an NP-hard promise problem. The precise inapproximability ratio depends on the reduction used after the pcp construction, rather than on the basic class equality alone.
Historical development
The theorem developed from work on interactive proof systems, algebraic encodings, and multiprover verification. László Babai, Lance Fortnow, and Carsten Lund established structural connections between bounded-round interaction and probabilistic verification. Lund’s work with Howard Karloff, Noam Nisan, and Mario Szegedy also demonstrated how algebraic representations could support randomized checking with limited access to encoded data.
A major precursor was the equality
[ \mathrm{MIP}=\mathrm{NEXP}, ]
proved by Babai, Fortnow, and Lund. It characterizes nondeterministic exponential time through multiprover interactive proofs, in which spatially separated provers cannot coordinate their answers during verification. Transformations from multiprover protocols to oracle-style proof systems supplied the framework from which constant-query verification emerged.
The first proof of the pcp theorem was obtained through a collaboration that combined the work of Sanjeev Arora with that of Carsten Lund. The same collaboration incorporated the verifier analysis developed by Rajeev Motwani and Madhu Sudan, while Mario Szegedy and You Watanabe contributed to the common proof and its soundness analysis. Their construction integrated algebraic proof representations with tests that inspect only a bounded number of locations.
Arora and Shmuel Safra subsequently gave a related formulation based on proof composition. These results established constant-query verification with logarithmic randomness and showed that the local checks retained a constant soundness gap under recursive reduction of the proof components.
Irit Dinur later produced a combinatorial proof centered on gap amplification. Her construction repeatedly transforms a constraint graph so that globally inconsistent assignments violate a larger constant fraction of local constraints. Degree reduction and alphabet management prevent this amplification from causing an uncontrolled increase in instance size or query complexity.
Structure of the original proof
The original argument represents a computation through an algebraic encoding whose consistency can be tested locally. A purported proof contains information about a polynomial or a related structured function over a finite field. The verifier checks whether small samples behave as values of an object having the required low-degree structure.
A low-degree test distinguishes functions close to low-degree polynomials from functions that remain far from every such polynomial. This distinction permits local observations to carry information about a global algebraic object. The analysis converts frequent success on randomly chosen local tests into proximity to a valid encoding, after which additional checks determine whether the encoded computation satisfies the required relations.
The algebraic verifier obtained at an intermediate stage does not immediately have all parameters required by the final theorem. Its local predicates may involve proofs or alphabets that are too large. Proof composition replaces each complex local assertion with another probabilistically checkable proof, thereby reducing the number or size of the queried symbols. The soundness analysis tracks how errors propagate across levels of composition and ensures that a false global claim cannot satisfy too many local verifiers.
The resulting proof strings may be substantially longer than conventional NP witnesses, but their length remains polynomial in the input size. The defining improvement concerns access rather than storage: the verifier receives oracle access to the proof and examines only a constant number of selected locations.
Gap amplification
Dinur’s proof begins with a constraint graph representing a verification problem with a small unsatisfied fraction. Its central operation amplifies this fraction while preserving a polynomial bound on the size of the graph.
Graph powering replaces individual consistency checks with checks along short random walks. When an assignment contains dispersed inconsistencies, a walk has an increased probability of encountering at least one of them, which enlarges the rejection gap. The expansion properties of the underlying graph prevent the walk distribution from concentrating excessively in regions where all constraints happen to be satisfied.
Powering also increases vertex degree and enlarges the local alphabet. Degree-reduction transformations restore bounded degree, while assignment-testing constructions control the amount of information associated with each vertex. Repeating the amplification a logarithmic number of times produces a constant gap without increasing the final instance beyond polynomial size.
This formulation relates the pcp theorem to expander graphs and error-correcting codes. Expansion distributes local inconsistencies across many potential tests, while coding-theoretic distance separates valid encodings from strings that disagree with every valid encoding on a substantial fraction of positions.
Consequences for approximation
The pcp theorem changed the classification of NP optimization problems by making constant-factor gaps available inside polynomial-time reductions. For maximum satisfiability, the theorem implies that some constant (\varepsilon>0) makes it NP-hard to distinguish a fully satisfiable instance from one whose optimum is at most (1-\varepsilon).
Gap-preserving reductions transfer this separation to other optimization problems. A reduction must relate feasible solutions in the source and target instances closely enough that the completeness case retains its designated objective value while the soundness case remains bounded away from it. The resulting threshold is determined by the quantitative properties of both the pcp verifier and the reduction.
Later refinements of probabilistically checkable proofs produced sharper thresholds. Parallel repetition reduces soundness in multiprover systems, while specialized predicate analyses determine how close an approximation algorithm can come to the optimum before it would contradict standard complexity assumptions. The pcp theorem itself supplies the constant gap underlying these developments, rather than every optimal numerical bound derived from them.
Conceptual significance
Ordinary NP verification reads an entire polynomial-size certificate, even though the verification computation remains efficient. The pcp theorem replaces this global inspection with a randomized local test whose query count does not grow with the input. Soundness is possible because the proof is encoded redundantly, causing a false claim to generate inconsistencies across a constant fraction of the verifier’s possible local views.
The theorem therefore identifies a correspondence between computational hardness and robust unsatisfiability. An NP statement that is false can be transformed into a constraint system that remains detectably false under every assignment, rather than merely failing at one isolated condition. This robustness is the property that supports both local proof verification and hardness-of-approximation reductions.