Introduction

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.

The Hardness Gap

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">A <b>clique</b> is a group where everyone is connected to everyone else. The goal: find the <b>largest</b> clique. The greedy heuristic is instant but can fall short — the true maximum needs an exhaustive search. Watch the <b>gap</b> between "good enough" and "best".</p>
<svg id="graph" viewBox="0 0 300 240" class="graph"></svg>
<div class="scores">
  <div class="score"><span class="lbl">Greedy guess</span><span id="greedy" class="val">—</span></div>
  <div class="score"><span class="lbl">True maximum</span><span id="optimum" class="val">—</span></div>
</div>
<div class="status" id="status">Run the greedy heuristic, then find the true maximum.</div>
<div class="btns">
  <button id="greedyBtn" type="button">Greedy guess</button>
  <button id="optBtn" type="button">Find the true maximum</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Maximum Clique. A clique = a set of vertices all pairwise connected.
// GREEDY: start from the highest-degree vertex, then keep adding the next
//   vertex that stays adjacent to everyone chosen. Fast, but no guarantee.
// OPTIMUM: brute force over all 2^n subsets — the true largest clique.
// The gap is the point: approximating max-clique within n^(1-e) is NP-hard
// (Hastad, 1996), powered by the PCP theorem (1992). No fast algorithm closes it.

// 12 vertices. The 5-clique {4,5,6,7,8} is the true maximum. But the hub
// vertices {0,1,2} have the highest degree (5), so greedy dives into them and
// gets stuck at a 4-clique {0,1,2,10} — one short of the real answer.
const POS = [
  [60,55],[150,40],[240,55],          // 0,1,2 hubs
  [150,95],                            // 3
  [70,150],[150,135],[230,150],        // 4,5,6 big clique
  [95,210],[205,210],                  // 7,8 big clique
  [25,95],[150,205],[275,95]           // 9,10,11 leaves
];
const E = [
  [4,5],[4,6],[4,7],[4,8],[5,6],[5,7],[5,8],[6,7],[6,8],[7,8], // K5 on {4,5,6,7,8}
  [0,1],[1,2],[0,2],                                            // hub triangle
  [0,9],[0,10],[0,11],
  [1,9],[1,10],[1,3],
  [2,10],[2,11],[2,3]
];
const N = POS.length;
const adj = Array.from({length:N}, () => new Set());
E.forEach(([a,b]) => { adj[a].add(b); adj[b].add(a); });
const connected = (u,v) => adj[u].has(v);
const isClique = s => { for(let i=0;i<s.length;i++) for(let j=i+1;j<s.length;j++) if(!connected(s[i],s[j])) return false; return true; };

function greedyClique(){
  const order = [...Array(N).keys()].sort((a,b)=>adj[b].size-adj[a].size);
  const clique = [order[0]];
  for(const v of order){
    if(clique.includes(v)) continue;
    if(clique.every(u=>connected(u,v))) clique.push(v);
  }
  return clique;
}
function maxClique(){
  let best=[];
  for(let mask=1; mask<(1<<N); mask++){
    const s=[]; for(let i=0;i<N;i++) if(mask&(1<<i)) s.push(i);
    if(s.length>best.length && isClique(s)) best=s;
  }
  return best;
}

let current=[];
function draw(){
  const svg=document.getElementById('graph'); svg.innerHTML='';
  const inSet=new Set(current);
  const inBoth=(a,b)=>inSet.has(a)&&inSet.has(b);
  E.forEach(([a,b])=>{
    const l=document.createElementNS('http://www.w3.org/2000/svg','line');
    l.setAttribute('x1',POS[a][0]);l.setAttribute('y1',POS[a][1]);
    l.setAttribute('x2',POS[b][0]);l.setAttribute('y2',POS[b][1]);
    l.setAttribute('class','edge'+(inBoth(a,b)?' in':''));
    svg.appendChild(l);
  });
  POS.forEach(([x,y],i)=>{
    const c=document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',x);c.setAttribute('cy',y);c.setAttribute('r',13);
    c.setAttribute('class','node'+(inSet.has(i)?' in':''));
    svg.appendChild(c);
    const t=document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',x);t.setAttribute('y',y+4);t.setAttribute('class','nlabel');
    t.setAttribute('fill',inSet.has(i)?'#fff':'#1d3557');
    t.textContent=i; svg.appendChild(t);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

document.getElementById('greedyBtn').addEventListener('click',()=>{
  current=greedyClique();
  document.getElementById('greedy').textContent=current.length;
  draw();
  setStatus(fmt('Greedy found a clique of size %length% ({%sort%}). Is it the biggest?', { length: current.length, sort: current.slice().sort((a,b)=>a-b).join(',') }),'');
  console.log('Greedy clique:', current.join(','), 'size', current.length);
});
document.getElementById('optBtn').addEventListener('click',()=>{
  const opt=maxClique();
  document.getElementById('optimum').textContent=opt.length;
  const g=document.getElementById('greedy').textContent;
  current=opt; draw();
  if(g!=='—' && +g<opt.length) setStatus(fmt('The true maximum is %length% — greedy missed by %v%. That gap is inapproximability.', { length: opt.length, v: opt.length-+g }),'gap');
  else setStatus(fmt('The true maximum clique has size %length% ({%sort%}).', { length: opt.length, sort: opt.slice().sort((a,b)=>a-b).join(',') }),'ok');
  console.log('Max clique:', opt.join(','), 'size', opt.length);
});
document.getElementById('reset').addEventListener('click',()=>{
  current=[]; document.getElementById('greedy').textContent='—';
  document.getElementById('optimum').textContent='—';
  draw(); setStatus('Run the greedy heuristic, then find the true maximum.','');
});
draw();
Result
Console

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.

The Real Complexity

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 n1−εn^{1-\varepsilon} is NP-hard — essentially no useful approximation is possible unless P = NP.

This is a proven hardness result (conditional on P≠NPP \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.

Where It Matters

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+ε)(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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/inapproximability/Content licensed under CC BY-NC 4.0.