Symptom

You gave up on exact (T028) and went looking for an approximation.

Vertex cover: you find a 2-approximation in four lines. Knapsack: an FPTAS, any accuracy you want. Encouraged, you go looking for the same for max-clique, and you find nothing. Not “nothing good” — the best known ratio is around $n/(\log n)^2$, which on a 10,000-vertex graph means the algorithm might return a clique nearly 60 times smaller than the true maximum. That is not an approximation, it is a rumour.

Why does approximability vary so wildly across problems that are all equally hard to solve exactly? Karp’s problems are interreducible; exact solution is one problem in twenty-one disguises. Approximation shatters that equivalence completely, and the reason it does is one of the deepest results in the field.

Statement

The PCP theorem (Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy, 1992).

$$\text{NP} = \text{PCP}(\log n, 1)$$

Every NP language has a proof format such that a verifier using $O(\log n)$ random bits and reading only a constant number of bits of the proof accepts correct proofs always, and rejects claimed proofs of false statements with probability at least 1/2. The constant can be taken to be 3.

Read that again, because it should sound impossible. You can check a mathematical proof by looking at three bits of it, chosen at random, and catch any flaw half the time. Not three lines. Three bits.

The equivalent gap formulation, which is what gets used. It is NP-hard to distinguish 3-SAT instances that are fully satisfiable from those where at most a $(1-\epsilon)$ fraction of clauses can be satisfied, for some fixed $\epsilon > 0$.

The consequence. If approximating a problem within some ratio would let you distinguish those two cases, then approximating within that ratio is NP-hard. Hardness of approximation follows from hardness of decision — the PCP theorem is the bridge, and before it there was essentially no way to prove any inapproximability result at all.

Sharp consequences, all tight or nearly so:

  • MAX-3SAT is NP-hard to approximate better than 7/8 (Håstad). Random assignment achieves exactly 7/8, so the trivial algorithm is optimal.
  • Max-clique is NP-hard within $n^{1-\epsilon}$ for any $\epsilon > 0$.
  • Set cover is NP-hard within $(1-o(1))\ln n$ (Feige, Dinur–Steurer). Greedy matches it.
  • Vertex cover is NP-hard within $1.36$, and within $2-\epsilon$ under the Unique Games Conjecture.

Argument

The full proof is long and this post will not give it. The load-bearing ideas are gettable, and they are what you need.

Why “3 bits” is not a trick. The verifier does not read the proof as a transcript. The proof is written in an error-correcting encoding (T022) of the satisfying assignment. In a good code, any two valid codewords differ in a constant fraction of positions, so a corrupted or fabricated proof differs from every valid one almost everywhere. Random spot-checks then catch it with constant probability. Local checkability comes from global redundancy — exactly the property T022 studies, deployed for verification rather than transmission.

The easy direction. PCP$(\log n, 1) \subseteq$ NP: a verifier using $O(\log n)$ random bits has polynomially many random strings, so enumerate them all, simulate, accept if all accept. Straightforward.

The hard direction, in outline. Given a 3-SAT instance, encode the assignment in a highly redundant form — the original proof used the Walsh–Hadamard code, where the proof is the value of every linear function of the assignment, an exponentially long object. Linearity testing (the BLR test: check $f(x) + f(y) = f(x+y)$ on random $x, y$) verifies the encoding is close to linear using three queries. Then self-correction recovers any desired value reliably from a slightly corrupted table. Composition — recursively applying the same machinery to the verifier’s own computation — brings the proof length back down to polynomial while keeping the query count constant. Proof composition is the technical heart, and it is genuinely hard.

Dinur’s gap amplification (2007) is the version to know. Instead of building the verifier directly, start from a standard NP-hard constraint system with a tiny satisfiability gap and amplify it. Each round: take the constraint graph, raise it to a power by replacing constraints with walks of length $t$ (which doubles the gap but blows up the alphabet), then compose with a small fixed PCP to shrink the alphabet back. Repeat $O(\log n)$ times. The gap doubles each round and the size grows only by a constant factor, so a constant gap arrives after logarithmically many rounds at polynomial total size.

This reframes the theorem entirely: PCP is not a statement about proofs, it is a statement about amplifying a small gap into a large one, and the amplifier is expander graph powering. That is a comprehensible idea, and it is why Dinur’s proof is the one taught.

How you actually use it. To prove your problem hard to approximate, build a gap-preserving reduction from gap-3SAT: satisfiable instances must map to instances with high optimum, and $(1-\epsilon)$-satisfiable ones to instances with low optimum. Then an approximation algorithm beating the ratio between them would decide gap-3SAT. This is a mechanical technique once you have the gap, and the entire inapproximability literature is instances of it.

Deriving an inapproximability result, end to end. Suppose you had a $(1 - \epsilon/2)$-approximation for MAX-3SAT with $\epsilon$ the PCP gap constant. Feed it a gap instance. If the instance is satisfiable, the algorithm returns an assignment satisfying at least $(1-\epsilon/2)m$ clauses. If at most $(1-\epsilon)m$ clauses are satisfiable, the algorithm cannot return more than that, since it cannot exceed the optimum. Those two ranges do not overlap, so counting satisfied clauses in the returned assignment decides gap-3SAT, which is NP-hard. Therefore the approximation algorithm cannot exist unless P = NP.

That is the entire argument pattern, and every hardness-of-approximation result in the literature is this shape with a gap-preserving reduction bolted on the front. Once you see it once, the wall of ratios in the previous post becomes a set of derived facts rather than a table to memorize.

Forbids

A PTAS for MAX-3SAT, max-clique, or set cover, unless P = NP. Not merely undiscovered. Ruled out at specific, known ratios.

Beating 7/8 for MAX-3SAT. The stupidest possible algorithm — assign each variable at random, satisfying each clause with probability 7/8 — is optimal, and no cleverness can improve it. This is the most striking single corollary.

Beating $\ln n$ for set cover. Greedy is optimal, and the thirty years spent looking for better were provably wasted.

Non-trivial clique approximation. Within $n^{1-\epsilon}$ is hard, so essentially nothing better than returning a single vertex is guaranteed.

Does not forbid

It does not stop good approximations for other problems, and the landscape is wildly uneven. Knapsack has an FPTAS. Euclidean TSP has a PTAS (Arora, Mitchell). Metric TSP had 3/2 from Christofides for forty years and was improved to $3/2 - 10^{-36}$ in 2020. Max-cut has the 0.878 Goemans–Williamson semidefinite bound, which is exactly optimal under the Unique Games Conjecture. Exact-solution equivalence does not survive approximation, and that is the main lesson.

It does not make heuristics useless. Set cover being $\ln n$-hard in the worst case does not stop greedy set cover from being excellent on real instances, and LKH solves TSP instances to within fractions of a percent routinely. Worst-case inapproximability is compatible with near-optimal performance on structured inputs.

It does not apply to average-case or structured instances. These are worst-case results. Planar and bounded-genus versions of many hard problems admit PTASes via Baker’s technique, and geometric instances are frequently much easier.

It does not mean the Unique Games Conjecture results are settled. UGC-based tight bounds — vertex cover at 2, max-cut at 0.878 — are conditional on a conjecture that is open and that some researchers doubt. Subexponential-time algorithms for unique games exist, which is unusual for a hardness assumption and worth knowing before citing UGC results as established.

It does not mean PCPs are only a proof technique. Probabilistically checkable proofs became practical: SNARKs and STARKs, deployed in zk-rollups on Ethereum and in verifiable computation generally, are engineered descendants of this machinery. A verifier really does check a computation by sampling a few positions of an encoded proof. The theorem became infrastructure, which almost no complexity result does.

Boundary

  • The approximability classes. APX (constant-factor), PTAS, FPTAS, and log-APX form a hierarchy that is strict unless P = NP. Locating your problem in it tells you what to aim for and when to stop.
  • Gap-preserving reductions are the working tool. Ordinary Karp reductions do not preserve approximation ratios. L-reductions and gap-preserving reductions do, and building the catalogue of inapproximability results was redoing Karp’s work with a stronger notion of reduction.
  • The Unique Games Conjecture as the missing piece. Many natural problems have a gap between the best algorithm and the best unconditional hardness. UGC closes almost all of them at once, which is either evidence for it or a reason for suspicion depending on temperament.
  • Håstad’s optimal inapproximability results are the sharpest artifacts here: for several problems, the trivial randomized algorithm is provably the best possible. There is something bracing about a theorem whose content is that cleverness cannot help.
  • Parameterized inapproximability. Recent work extends this to FPT approximation, showing some problems resist even the parameter-based escape of T033. The escapes are being closed off one at a time, and knowing which remain open is what tells you where to spend effort.