Approximation & PCP Theorem
Approximation ratios, the PCP characterization of NP, and inapproximability.
The idea
Approximation algorithms settle for provably near-optimal answers to NP-hard optimization problems, and the PCP theorem sets limits on how near they can get. A polynomial-time algorithm for a maximization problem has approximation ratio $\rho \le 1$ if its value satisfies $\mathrm{ALG} \ge \rho \cdot \mathrm{OPT}$ on every instance — a worst-case guarantee, not an average.
The limits come from a re-description of $\mathsf{NP}$. A probabilistically checkable proof system equips a language with a verifier that tosses $r(n)$ coins, reads $q$ bits of an alleged proof at positions the coins choose, and decides: it always accepts a correct proof of a true statement, and accepts no proof of a false statement with probability above $\tfrac{1}{2}$. Write $\mathsf{PCP}(r, q)$ for the languages with such a system.
Theorem (PCP theorem).
$\mathsf{NP} = \mathsf{PCP}(\log n,\, 1).$ That is, a language is in $\mathsf{NP}$ if and only if it has a probabilistically checkable proof system whose verifier uses $O(\log n)$ random bits and reads a constant number of bits of the proof.
The direction $\mathsf{PCP}(\log n, 1) \subseteq \mathsf{NP}$ is routine, since a polynomial-time verifier can try all $2^{O(\log n)}$ coin tosses; the content is that every $\mathsf{NP}$ language has a proof checkable by a constant number of spot checks.
This bears on approximation because a proof rejected with probability $\tfrac{1}{2}$ cannot be wrong in just one place — it must be wrong in a constant fraction of the possible checks. Turning each check into a constraint converts that fraction into a gap between the yes-case and no-case optimum values of a constraint problem — every constraint satisfiable on a yes instance, at most a $1 - \varepsilon$ fraction on a no instance — and an algorithm accurate enough to see across the gap would decide an NP-hard problem.
Ways to work on it
- Walkthrough. Approximation ratio, the PCP theorem, and how gaps produce hardness.
- Practice. Approximation guarantees, PCP resource counts, and soundness gaps.
- Hardest. Read the inapproximability threshold off a gap and state the consequence.
Not sure where to start? Take the ten-question placement test.