Hardness of Approximation and the PCP Theorem

We have been buying our way out of NP-hardness by giving up a little optimality. It is natural to hope the price always keeps falling — that with enough cleverness every problem gets a PTAS and we approximate as closely as we please. That hope is false, and provably so. For many problems there is a hard floor: no polynomial-time algorithm can beat a specific ratio unless \text{P}=\text{NP}. Approximation, it turns out, has its own theory of intractability.

The engine behind almost every such result is one of the crown jewels of complexity theory — the PCP theorem — and one gorgeous idea: a reduction that doesn't just map yes/no to yes/no, but blows open a gap in the objective value, so that even a rough approximation would answer the original NP-hard question exactly.

Gap-introducing reductions: the core trick

Suppose you want to prove that MAX-3SAT (satisfy as many clauses as possible) cannot be approximated beyond some ratio. You build a reduction from an NP-complete problem that produces formulas of two wildly separated kinds:

YES instances map to formulas where all clauses can be satisfied — optimum value = 1 (a 1-fraction).
NO instances map to formulas where no assignment satisfies more than a \tfrac{7}{8}-fraction — optimum value \le \tfrac{7}{8}.

There is nothing in between. Now suppose you had a polynomial-time \rho-approximation with \rho > \tfrac{7}{8}. Run it: on a YES instance it must report more than \tfrac{7}{8}; on a NO instance it can never exceed \tfrac{7}{8}. So its output tells you which case you're in — i.e. it solves the NP-complete problem in polynomial time. Contradiction, unless \text{P}=\text{NP}.

That is the whole shape of every inapproximability proof: manufacture a gap the approximation would have to fall inside, and let the approximation's own guarantee sort YES from NO. The figure makes the geometry vivid — two islands of possible optima with a forbidden channel between them.

The hard part, of course, is building such a gap — ordinary NP-completeness reductions preserve exact answers but say nothing about approximate ones. Producing a robust, constant-sized gap for a problem as basic as 3SAT was open for years. Its resolution is the PCP theorem.

The PCP theorem

A probabilistically checkable proof is a proof written so that a verifier can be convinced by reading only a tiny random sample of it. Formally, \text{PCP}(r, q) is the class of languages with a proof and a randomised verifier that uses O(r) random bits, reads only O(q) bits of the proof, always accepts a correct proof of a true statement, and rejects any purported proof of a false statement with probability at least \tfrac{1}{2}.

\text{NP} \;=\; \text{PCP}\big(O(\log n),\; O(1)\big).

Every NP statement has a proof that a verifier can check by using only O(\log n) random bits and reading a constant number of its bits — O(1), independent of proof length.
If the statement is true, some proof is always accepted; if false, every proof is rejected with probability \ge \tfrac{1}{2}.

Read that again: a proof of any length, checked by glancing at a fixed handful of bits, and a false theorem cannot sneak past more than half the time. It sounds impossible — yet it is true, and its equivalent phrasing is precisely a gap version of 3SAT. The constant rejection probability is the gap; the reduction from a PCP verifier to a constraint-satisfaction instance is the gap-introducing reduction. PCP and hardness-of-approximation are two faces of one theorem.

What the gaps buy us: sharp thresholds

Plugging the PCP machinery in gives some of the most precise results in all of complexity — down to the exact constant:

Problem	Best poly-time ratio possible (unless P = NP)	Trivially achievable
MAX-3SAT	No better than \tfrac{7}{8} (Håstad — tight)	\tfrac{7}{8} by a random assignment!
Set Cover	No better than (1-o(1))\ln n	\ln n by greedy
Max Clique	No n^{1-\varepsilon} ratio for any \varepsilon > 0	n (essentially nothing)
Vertex Cover	No better than 2 - \varepsilon (under UGC)	2 by matching

Håstad's MAX-3SAT result is the jewel: the threshold is exactly \tfrac{7}{8}, and a coin-flip assignment already achieves \tfrac{7}{8} in expectation (each 3-clause is satisfied with probability \tfrac{7}{8}). So the dumbest algorithm imaginable is optimal, and no amount of cleverness can shave off even an \varepsilon. Max Clique is the opposite extreme — essentially no nontrivial approximation is possible. These are the "beyond APX" problems from the previous page, now given hard proofs.

Take any 3SAT clause, say (x \vee \neg y \vee z). A uniformly random assignment falsifies it only when all three literals are false — probability (\tfrac{1}{2})^3 = \tfrac{1}{8} — so it is satisfied with probability \tfrac{7}{8}. By linearity of expectation, the expected fraction of satisfied clauses is \tfrac{7}{8} regardless of the formula — so some assignment hits at least that. Håstad's theorem says you cannot beat this in the worst case unless \text{P}=\text{NP}. The thousand-page PCP edifice exists, in a sense, to prove that a coin flip is unimprovable.

Two careful caveats. First, inapproximability is conditional: MAX-3SAT being hard beyond \tfrac{7}{8} assumes \text{P} \neq \text{NP} — it is a statement about the barrier, not an unconditional impossibility. Second, and more practically, it is a worst-case statement over adversarial instances. A gap-hard problem can still be approximated beautifully on the structured, real-world instances you actually face — the gap instances are exotic constructions, not your data. And note the Vertex Cover 2-\varepsilon bound leans on the Unique Games Conjecture, still unproven; hardness results come in tiers of confidence, and it pays to know which theorem rests on which assumption.