Probabilistically Checkable Proofs

In 1994 researchers proved something paradoxical: to verify an NP proof of one million bits, reading exactly three random bits suffices. Not three thousand, not three percent - exactly three bits. This single theorem instantly rendered dozens of optimization problems inapproximable beyond specific constants - problems that previously seemed merely 'hard'.

• **Routing and TSP:** the Travelling Salesman Problem has no polynomial approximation beyond certain constants - the PCP theorem explains why improving algorithms past a specific ratio is pointless.
• **Scheduling:** for many NP-hard scheduling problems, greedy algorithms hit the PCP boundary - investing in more complex algorithms is theoretically futile.
• **Zero-Knowledge proof systems:** the PCP idea underlies modern zkSNARK systems, where a short proof is verified by sampling a few random positions.

The PCP Theorem

In 1971 Cook proved NP-completeness of SAT: every NP proof can be verified deterministically in polynomial time by reading the entire proof. In 1992 Arora, Lund, Motwani, Sudan and Szegedy proved something astonishing: every NP proof can be re-encoded so that a verifier with access to **O(log n) random bits** can check its correctness by reading only **O(1) positions** in the proof string.

**PCP Theorem (1998, final form):** NP = PCP(log n, 1). For every language L ∈ NP there exists a probabilistic verifier V that uses r = O(log n) random bits, reads q = O(1) bits from proof π, and satisfies: if x ∈ L then ∃π: Pr[V accepts] = 1; if x ∉ L then ∀π: Pr[V accepts] ≤ 1/2.

The intuition behind the theorem: an NP proof is translated into a redundant encoding (a linear code over GF(2)) where any incorrect proof is 'broken' in a large fraction of positions. A random check of three positions hits a broken location with constant probability.

Gap Amplification

The PCP theorem is equivalent to the following statement about 3-SAT: there exists a polynomial reduction mapping any formula φ to a formula φ' such that if φ is satisfiable then φ' is also satisfiable; if φ is unsatisfiable then at most (1 - ε) fraction of clauses in φ' are simultaneously satisfiable for some constant ε > 0. This is **gap amplification** - widening the gap between the satisfiable and unsatisfiable cases.

The gap amplification technique in the proof of the PCP theorem (Dinur's 2007 simplified proof): take the constraint graph of the problem and repeatedly apply two steps - **expander powering** (raising to a power via an expander graph, increasing the gap) and **alphabet reduction** (reducing the alphabet back to a constant). After O(log n) iterations the gap reaches a constant.

**Alphabet vs gap:** after each powering step the alphabet grows, but the gap grows too. Alphabet reduction (via error-correcting codes) brings the alphabet back to a constant while preserving the gap. This balance is the key idea of Dinur's proof.

Inapproximability Results

The PCP theorem directly implies: **Max-3-SAT cannot be approximated beyond ratio 7/8 unless P = NP**. The number 7/8 is not coincidental - it is exactly the fraction of clauses satisfied by a random variable assignment (each 3-clause is unsatisfied with probability 1/8). The simplest randomized algorithm is therefore optimal by its guarantee.

The scheme for obtaining an inapproximability result: take a problem L ∈ NP, apply the PCP reduction to an optimization problem (e.g., Max-CSP), then show that any algorithm with ratio > c would solve L in polynomial time. The constant c is determined by the parameters of the PCP verifier.

Hardness of Approximation in Practice

PCP results explain why many LP/SDP relaxations are the 'right' algorithms: they achieve the theoretical limit. The Goemans-Williamson algorithm (1995) for Max-Cut with ratio 0.878 is optimal under the Unique Games Conjecture (UGC, Khot 2002). If UGC is true, Vertex Cover cannot be approximated better than 2 - ε, although a simple greedy gives exactly 2.

**Unique Games Conjecture (UGC):** for any ε > 0 it is NP-hard to distinguish satisfiability ≥ 1-ε from satisfiability ≤ ε in a system of linear equations over Z_k with exactly 2 variables per equation. UGC is stronger than PCP and allows proving optimality of many known algorithms.

The most practical lesson: before designing an approximation algorithm, check whether a known lower bound exists. If yes, this is the ceiling for any polynomial algorithm. If no, the problem may admit a better approximation, or it may be hard to approximate but the bound has not yet been proven.

Key Ideas

• **PCP Theorem:** NP = PCP(log n, 1) - every NP proof can be re-encoded for verification with O(1) random queries using O(log n) random bits.
• **Gap amplification:** PCP is equivalent to a polynomial reduction 3-SAT → Max-3-SAT with a constant gap between satisfiable (OPT=1) and unsatisfiable (OPT ≤ 7/8) instances.
• **7/8 threshold for Max-3-SAT:** approximation above 7/8 is impossible under P ≠ NP; random assignment achieves this bound exactly.
• **UGC extends results:** the Unique Games Conjecture allows proving optimality of SDP algorithms (Max-Cut 0.878, Vertex Cover 2) - many greedy solutions are theoretically unbeatable.

Related Topics

The PCP theorem connects several key areas of complexity theory:

• Randomized Algorithms — The PCP verifier uses randomness; repetition reduces error exponentially
• Interactive Proofs (IP, AM) — PCP is a non-interactive analogue of IP: no interaction, but random access to the full proof

Вопросы для размышления

• If a PCP verifier reads only 3 bits, how does the re-encoded proof still contain all the information about the original proof?
• The 7/8 threshold for Max-3-SAT coincides with the probability of satisfying a clause by random assignment. Is this a coincidence, or does a deeper principle underlie it?
• If P = NP were proven, which inapproximability results would automatically collapse, and which would remain valid?

Связанные уроки

• alg-01-big-o