Gap Amplification and Why Some Ratios Cannot Be Improved

Every approximation ratio discussed so far has been an upper bound: an algorithm that achieves it. A hardness result is the complementary statement, that no algorithm can do better unless a complexity assumption fails. The tool that produces most such results is the PCP theorem, which characterizes NP in terms of probabilistically checkable proofs and, in its combinatorial form, produces constraint systems in which satisfying many constraints is easy to certify and satisfying almost all of them is NP-hard. That gap in satisfiability, once established, transfers to approximation ratios for optimization problems by a reduction that preserves the gap.

The gap idea before the theorem

Consider 3-SAT. Deciding satisfiability is NP-complete, so no polynomial algorithm solves it exactly unless P = NP. Suppose instead the question is: given a formula that is either satisfiable or has every assignment falsifying at least a constant fraction $\varepsilon$ of its clauses, decide which. This is a promise problem with a gap. If it is NP-hard, then no polynomial algorithm distinguishes the two cases, and any algorithm that approximates MAX-3SAT within a factor better than $1/(1 - \varepsilon)$ would solve it. That is the shape of every hardness-of-approximation reduction: a gap in a decision problem becomes a bound on an approximation ratio.

The PCP theorem supplies such gaps for constraint satisfaction, and the constants are what make the results quantitative.

What a probabilistically checkable proof is

A PCP verifier is a randomized polynomial-time machine that reads a claimed proof of a statement and queries a small number of its bits. Completeness: if the statement is true, some proof makes the verifier accept with probability 1. Soundness: if the statement is false, every proof makes the verifier accept with probability at most some constant $s < 1$.

The PCP theorem states that every language in NP has a PCP verifier that uses $O(\log n)$ random bits and queries a constant number of proof bits. The $O(\log n)$ randomness means the verifier can be run over all $2^{O(\log n)} = n^{O(1)}$ random strings in polynomial time, and for each random string it queries a constant number of positions. That is the bridge to a constraint system: each random string defines a constraint on the queried positions, the proof is an assignment, and the acceptance probability is the fraction of satisfied constraints.

With $q$ queries and soundness $s$, the resulting constraint system has the property that either all constraints are satisfiable (when the statement is true) or at most a fraction $s$ are (when it is false). Since $q$ is a constant and $s$ is a constant bounded away from 1, the gap is a constant.

The original proofs of the theorem are substantial. Arora and Safra introduced the class of probabilistically checkable proofs with logarithmic randomness and the proof-composition idea that reduces the number of queries the verifier must make, establishing a characterization of NP with a small soundness error. Arora, Lund, Motwani, Sudan and Szegedy then pushed the composition to its limit, obtaining a verifier that queries a constant number of positions. The later work of Dinur reproved the theorem by gap amplification, a combinatorial argument that iteratively amplifies a small gap into a constant one while preserving the constraint graph’s locality.

From constraint gap to inapproximability

The transfer to an optimization problem has a standard form. Given a constraint system with a gap, encode each constraint as a “clause” of the target problem such that satisfying the constraint corresponds to satisfying the clause, and the target problem’s optimum is proportional to the maximum number of satisfiable constraints. Then:

• If the source instance is satisfiable, the target has a solution of value 1 (or the maximum).
• If the source instance is at most $s$-satisfiable, the target’s optimum is at most $s$.

A polynomial-time algorithm approximating the target within a factor better than $1/s$ would distinguish the two cases, contradicting the NP-hardness of the gap problem. The ratio $1/s$ is therefore a lower bound on the inapproximability of the target.

The reduction must preserve the gap, which means it must be gap-preserving: the value of the target’s optimum must be a fixed function of the source’s satisfaction fraction, with the function known and monotone. Many reductions used for NP-completeness are not gap-preserving, which is why the PCP theorem was needed: the classical reductions preserve satisfiability, not the fraction of satisfied constraints.

Ratios that the theorem fixes

MAX-3SAT. There is a constant $\varepsilon > 0$ such that distinguishing satisfiable 3-CNF formulas from ones where every assignment falsifies at least $\varepsilon$ of the clauses is NP-hard. Consequently MAX-3SAT has no polynomial-time approximation scheme unless P = NP. The random assignment that sets every variable independently satisfies each clause of three literals with probability $7/8$, because a clause is falsified exactly when all of its literals are set false, so the assignment achieves a ratio of $7/8$ in expectation, and Håstad’s sharper PCP analysis shows that no ratio above $7/8$ is achievable unless P = NP. That $7/8$ is a threshold rather than an artifact of the algorithm.

Set cover. Feige’s result, discussed in the harmonic bound, shows that no polynomial algorithm approximates set cover within $(1 - o(1))\ln n$ unless NP has quasi-polynomial algorithms. This matches the greedy algorithm’s $H(n)$ bound in order. The two bounds meeting is unusual; for most problems there is a gap between the best algorithm and the best hardness result, and closing it is open.

Vertex cover. The standard approximation rounds the LP relaxation at threshold $1/2$ and gives a ratio of 2. The best unconditional hardness result is about 1.36, from Dinur and Safra, and the unique games conjecture would raise it to $2 - \varepsilon$ for any $\varepsilon > 0$. Without that conjecture the gap between 1.36 and 2 is open. This is the standard illustration that hardness results are conditional and often do not match the algorithms.

Metric TSP. No constant-factor approximation exists for the general problem, since an arbitrary cost matrix can be encoded with a single edge whose cost dwarfs all others. For the metric case the classical algorithm is the $3/2$ construction from Christofides, and the first improvement on it in four decades, by Karlin, Klein and Oveis Gharan, reduces the factor by a constant too small to detect. The integrality gap of the subtour linear program, which is the lower bound that line of work uses, is at least $4/3$, and no hardness result for metric TSP comes close to that.

Gap amplification as a technique

Dinur’s proof of the PCP theorem is worth understanding as an algorithmic idea, because it is the cleanest demonstration of how a gap can be increased deliberately.

Start with a constraint graph: vertices are variables, edges are constraints, and the goal is to maximize satisfied edges. A gap amplification step consists of two operations. Powering replaces the graph with one whose vertices are walks of length $t$ in the original, so that a single new constraint summarizes $t$ old ones. This increases the gap: if the original was at most $1 - \varepsilon$ satisfiable, the powered graph is at most roughly $(1 - \varepsilon)^t$ satisfiable, which for constant $t$ is a substantially larger gap. The cost is that the alphabet size grows from $q$ to $q^t$, and the graph’s degree grows.

Alphabet reduction then brings the alphabet back down to a constant size while preserving the gap, at the cost of a constant-factor blow-up in the graph size. Alternating powering and alphabet reduction drives the gap to a constant in a constant number of rounds, each of which multiplies the instance size by a constant. The result is a polynomial-time construction of a constraint system with a constant gap from any NP statement.

The technique is not directly an algorithm for an optimization problem, but it is a reduction, and it demonstrates that the “hardness amplification” intuition — a small gap can be made large by composing constraints — is a rigorous construction rather than a heuristic.

What hardness results do and do not say

Three qualifications matter when reading a ratio claim.

Conditionality. Every hardness result rests on an assumption: P ≠ NP, or NP does not have quasi-polynomial algorithms, or the unique games conjecture. The assumptions are believed but unproven. A hardness result is therefore not a proof that no better algorithm exists; it is a proof that a better algorithm would imply something unexpected about complexity classes.

Worst case versus typical. Hardness results construct families of instances, and the instances may be exotic. A ratio that is unachievable in the worst case may be beaten on inputs that arise in practice. This is why the set cover algorithm is used despite its logarithmic bound: an instance whose sets do not overlap adversarially does not exercise the mechanism the hardness construction exploits.

The gap between algorithm and hardness. For vertex cover, for metric TSP, and for many scheduling problems, the best algorithm and the best hardness result do not meet. The open question is whether the algorithm is suboptimal or the hardness analysis is weak. The primal-dual schema is one of the few general techniques for improving ratios, and its limits are exactly the integrality gaps of the relaxations it uses.

Why the exchange argument’s failure is the right frame

The material above began with the exchange argument, which proves optimality when a repair exists at equal cost. Hardness results explain when no polynomial algorithm can have such a repair, at least not one that preserves cost within a constant factor. The connection is not merely thematic.

An approximation algorithm can be read as a weakened exchange: instead of showing that the greedy choice can be swapped into an optimal solution at no cost, one shows it can be swapped at a bounded multiplicative cost. When the bound is 1, the algorithm is exact; when the structure forbids any bounded bound, the problem is hard to approximate. The PCP theorem is the tool that proves the forbidding for a wide class of constraint problems, and the reductions from it translate the impossibility into specific ratios.

What remains open for most of these problems is the exact location of the boundary. For knapsack the picture is complete at the level of constant factors: a fully polynomial-time approximation scheme exists, so no constant-factor hardness can hold unless P = NP. For set cover and MAX-3SAT the algorithm and the hardness meet. For vertex cover and metric TSP they do not, and the distance between them is where the current work sits.