Inapproximability

When a problem is NP-hard, the usual escape hatch is to lower your standards: stop demanding the perfect answer and settle for one that's close. A route 10% longer than optimal, a schedule that wastes a little space, a clique nearly as big as the biggest. For many problems this works beautifully — fast approximation algorithms get you within a guaranteed factor of the best answer.

But for some problems, the escape hatch is welded shut. Not only is the exact answer hard to find — any answer within a fixed factor of the best is also NP-hard to find. This is inapproximability, and it is one of the most surprising results in all of computer science.

The headline example is Maximum Clique: in a network, find the largest group where everyone is connected to everyone else. We'll see that you can't even reliably get vaguely close to the right size — and that this is a theorem, not a gap in our cleverness.

Here is a small social network. A clique is a group of people who all know each other — every pair connected. The goal is to find the largest clique. Click Greedy guess to run a fast heuristic that repeatedly grabs the most-connected vertex, then Find the true maximum to brute-force the real answer.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 300 240" class="graph"></svg>
<div class="scores">
  <div class="score"><span class="lbl">{{lbl_greedy}}</span><span id="greedy" class="val">—</span></div>
  <div class="score"><span class="lbl">{{lbl_optimum}}</span><span id="optimum" class="val">—</span></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="greedyBtn" type="button">{{btn_greedy}}</button>
  <button id="optBtn" type="button">{{btn_optimum}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.graph { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto .4rem;
         background: #f5f7fa; border: 1px solid #dde4ec; border-radius: 10px; }
.edge { stroke: #b9c4d0; stroke-width: 2; }
.edge.in { stroke: #1d3557; stroke-width: 3.5; }
.node { fill: #c9ccd1; stroke: #adb1b8; stroke-width: 1.5; }
.node.in { fill: #e63946; stroke: #c92f3c; }
.nlabel { font: 700 11px ui-monospace, monospace; text-anchor: middle; pointer-events: none; }
.scores { display: flex; gap: .6rem; margin: .3rem 0; flex-wrap: wrap; }
.score { flex: 1; min-width: 120px; background: #eef2f6; border: 1px solid #d6dee7;
         border-radius: 8px; padding: .4rem .6rem; display: flex; justify-content: space-between; align-items: center; }
.score .lbl { font-size: .82rem; color: #45566a; }
.score .val { font: 800 20px ui-monospace, monospace; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.gap { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the gap. The greedy method is instant but often returns a clique noticeably smaller than the true maximum. You could try smarter heuristics, and on a tiny graph the optimum is easy to brute-force. But as graphs grow, brute force becomes hopeless — and the deep result is that no fast algorithm can guarantee to stay close to the maximum. The gap you're watching is not a bug in the heuristic; it is a wall.

How hard is it to approximate? The answer reshaped complexity theory.

• Approximation ratio. An algorithm is an r-approximation if its answer is always within a factor r of optimal. The question is: for which r does a fast (polynomial-time) algorithm exist?
• The PCP theorem (1992). Proved by Arora & Safra and Arora, Lund, Motwani, Sudan & Szegedy (Gödel Prize, 2001), it gives a new view of NP: every proof can be checked by reading only a constant number of random bits. This rewrites optimization problems so that a "yes" instance has a large optimum and a "no" instance has a tiny one — with nothing in between.
• A gap you cannot cross. Because that gap exists, any algorithm that even estimated the optimum closely would let you tell "yes" from "no" — solving an NP-complete problem. So beating a fixed ratio is itself NP-hard.
• Max-Clique is the extreme case. Håstad (1996) proved that for n vertices, approximating the maximum clique within a factor of $n^{1-\varepsilon}$ is NP-hard — essentially no useful approximation is possible unless P = NP.

This is a proven hardness result (conditional on $P \ne NP$), not an open question. The reductions run through SAT-style constraints, which is why inapproximability and satisfiability are two faces of the same coin.

Knowing the limit of approximation is enormously practical — it tells you when to stop searching for a clever algorithm:

• Network analysis. Finding the biggest tightly-knit community (a large clique) in a social or biological network is inapproximable in the worst case, so practitioners rely on heuristics and accept no guarantees.
• Scheduling and resource allocation. Some variants admit good approximations; others don't. The theory tells engineers which is which before they waste months.
• Machine learning. Many learning tasks reduce to optimization with sharp approximation thresholds — a reason some models are trained heuristically with no quality certificate.
• The approximability map. Some NP-hard problems have a perfect $(1+\varepsilon)$-approximation, some a fixed constant, some only logarithmic, and some — like Max-Clique — essentially none. The Unique Games Conjecture would pin down many of these thresholds exactly.

Inapproximability is the partner of Max-Clique and independent sets: it draws the line between problems you can tame with a heuristic and problems where every shortcut fails.

We instinctively believe that if a problem is too hard to solve perfectly, we can at least get close. Inapproximability shatters that comfort. The PCP theorem builds an unbridgeable gap into NP-hard problems, and for Maximum Clique that gap is total: unless P = NP, no fast algorithm can guarantee to land anywhere near the right answer.

So the next time a greedy heuristic falls short and you wonder whether a smarter trick would close the gap — sometimes the honest answer is that the gap is a wall, and the mathematics has already proven you can't climb it.