Introduction

Classical complexity theory draws one great line: problems that are tractable (solvable in polynomial time) versus those that seem intractable (NP-hard, or worse). But once you know a problem is in P, the obvious next question is: how polynomial? An O(n2)O(n^{2}) algorithm is a million times slower than an O(n)O(n) one when n = 10610^{6}. For real inputs that difference is everything.

Fine-grained complexity is the subfield that studies hardness inside polynomial time. It asks: given that problem X has a known algorithm running in O(nk)O(n^k) time, can you do better — say O(nk−0.1)O(n^{k-0.1})? And if not, why not?

The field's central discovery is that many familiar problems — longest common subsequence (LCS), edit distance, triangle detection — are connected by tight conditional lower bounds. Improving any of them below its current polynomial barrier would require breaking one of the foundational conjectures of theoretical computer science. The barriers are not proven absolute (that would require new mathematics beyond anything we have), but they are exactly as solid as the best open conjectures we know.

This situation is open: as of 2025, nobody has broken the quadratic barriers for LCS or edit distance, and none of the key conjectures (SETH, 3SUM) have been refuted. The fine-grained web of reductions grows every year.

Try It: 3SUM to Triangles

The 3SUM problem asks: given n integers, do any three of them sum to zero? The classic algorithm checks all pairs in O(n2)O(n^{2}) time — no truly sub-quadratic algorithm is known.

Triangle detection asks: does a graph contain three mutually adjacent vertices? It can be solved in O(n2.37…)O(n^{2.37\dots}) using fast matrix multiplication, but for sparse graphs the practical barrier is O(n2)O(n^{2}).

The demo below shows the reduction. Every number x in the 3SUM instance becomes a vertex in group A; every number y becomes a vertex in group B; every number -(x+y) is looked up in group C. Three vertices form a triangle exactly when a + b + c = 0.

<p class="hint">Generate a set of integers, run the reduction to build a tripartite graph, then check for triangles — a triangle exists iff three numbers sum to zero.</p>
<div class="panels">
  <div class="panel" id="panel-numbers">
    <div class="panel-title">3SUM Instance</div>
    <div id="numbers-display" class="number-list">—</div>
  </div>
  <div class="panel" id="panel-graph">
    <div class="panel-title">Tripartite Graph</div>
    <canvas id="graph-canvas" width="340" height="180"></canvas>
  </div>
</div>
<div class="status" id="status">Press "New instance" to begin.</div>
<div class="btns">
  <button id="btn-new" type="button">New instance</button>
  <button id="btn-reduce" type="button" disabled>Run reduction</button>
  <button id="btn-check" type="button" disabled>Check triangles</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panels { display: flex; gap: 10px; flex-wrap: wrap; margin-bottom: .6rem; }
.panel { flex: 1 1 150px; border: 1px solid #cdd9e3; border-radius: 10px; padding: 8px 10px; background: #f4f8fb; }
.panel-title { font-size: .75rem; font-weight: 700; text-transform: uppercase; letter-spacing: .06em; color: #5a7088; margin-bottom: 4px; }
.number-list { font: 700 13px ui-monospace, monospace; color: #1d3557; line-height: 1.7; min-height: 2.5em; }
#graph-canvas { display: block; width: 100%; height: auto; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fine-Grained Complexity demo: 3SUM → Triangle Detection reduction.
//
// 3SUM: Given n integers, find a, b, c (with repetition allowed from groups)
//   such that a + b + c = 0.
// Triangle detection: given a tripartite graph (groups A, B, C), find a triangle.
//
// Reduction: for each pair (a,b) with a in A, b in B, create edges:
//   - A-B edge between a and b (always)
//   - A-C edge between a and -(a+b) if -(a+b) in C
//   - B-C edge between b and -(a+b) if -(a+b) in C
// Then (a, b, c) is a triangle iff a + b + c = 0.

const W = 340, H = 180;
const canvas = document.getElementById('graph-canvas');
const ctx = canvas.getContext('2d');

let nums = [], tripartite = null, triangleResult = null;

function randInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function generateInstance() {
  // 5 integers in [-9, 9], guarantee at least one triple summing to 0
  const n = 5;
  nums = [];
  // Pick random values
  while (nums.length < n) {
    const v = randInt(-9, 9);
    if (!nums.includes(v)) nums.push(v);
  }
  // Insert a guaranteed triple: pick two, compute third
  const a = nums[0], b = nums[1], c = -(a + b);
  if (!nums.includes(c) && Math.abs(c) <= 9) {
    nums[2] = c; // replace third slot to guarantee a solution
  }
  nums.sort((x, y) => x - y);

  document.getElementById('numbers-display').textContent =
    '{' + nums.join(', ') + '}';
  tripartite = null;
  triangleResult = null;
  clearCanvas();
  setStatus('Instance ready. Press "Run reduction".', 'info');
  document.getElementById('btn-reduce').disabled = false;
  document.getElementById('btn-check').disabled = true;
}

function buildTripartite() {
  // Groups A, B, C are all equal to nums.
  // Vertices: A[i] = nums[i], B[j] = nums[j], C[k] = nums[k]
  // AB edges: all pairs
  // AC edges: A[i] to C[k] if C[k] === -(A[i] + B[j]) for some j
  //   — but for the graph we track: for each i,j, the pair (i,j) implies
  //     an edge A[i]-C[k] and B[j]-C[k] where C[k] = -(A[i]+B[j])
  const n = nums.length;
  const numSet = new Set(nums);
  const indexMap = {};
  nums.forEach((v, i) => { indexMap[v] = i; });

  const abEdges = new Set();
  const acEdges = new Set();
  const bcEdges = new Set();

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const a = nums[i], b = nums[j];
      const cval = -(a + b);
      if (numSet.has(cval)) {
        const k = indexMap[cval];
        abEdges.add(i + ',' + j);
        acEdges.add(i + ',' + k);
        bcEdges.add(j + ',' + k);
      }
    }
  }

  tripartite = { n, nums, numSet, indexMap, abEdges, acEdges, bcEdges };
  triangleResult = null;
  drawGraph(null);
  setStatus(fmt('Graph built (%size% AB edges). Press "Check triangles".', { size: abEdges.size }), 'info');
  document.getElementById('btn-check').disabled = false;
}

function checkTriangles() {
  const { n, nums, indexMap, numSet, abEdges, acEdges, bcEdges } = tripartite;
  // Find a triangle: triple (i,j,k) such that ab(i,j), ac(i,k), bc(j,k) all exist
  // Equivalently: a + b + c = 0
  let found = null;
  for (let i = 0; i < n && !found; i++) {
    for (let j = 0; j < n && !found; j++) {
      const cval = -(nums[i] + nums[j]);
      if (numSet.has(cval)) {
        const k = indexMap[cval];
        // verify edges exist
        if (abEdges.has(i+','+j) && acEdges.has(i+','+k) && bcEdges.has(j+','+k)) {
          found = { i, j, k, a: nums[i], b: nums[j], c: cval };
        }
      }
    }
  }
  triangleResult = found;
  drawGraph(found);
  if (found) {
    setStatus(fmt('Triangle found: %a% + %b% + %c% = 0  →  3SUM answer: YES', { a: found.a, b: found.b, c: found.c }), 'ok');
    console.log('Triangle:', found.a, found.b, found.c, '— verified sum:', found.a+found.b+found.c);
  } else {
    setStatus('No triangle found — 3SUM answer: NO (no triple sums to zero).', 'bad');
    console.log('No triple sums to zero in', nums);
  }
}

// ── Drawing ──────────────────────────────────────────────────────────────────
function groupX(group) {
  // 3 groups: A=left, B=middle, C=right
  return [60, 170, 280][group];
}
function vertexY(i, n) {
  const spacing = Math.min(30, (H - 40) / Math.max(n - 1, 1));
  const total = spacing * (n - 1);
  return (H - total) / 2 + i * spacing;
}

function clearCanvas() {
  ctx.clearRect(0, 0, W, H);
  // Group labels
  ctx.fillStyle = '#5a7088';
  ctx.font = '700 11px system-ui';
  ctx.textAlign = 'center';
  ['A', 'B', 'C'].forEach((label, g) => {
    ctx.fillText(label, groupX(g), 14);
  });
}

function drawGraph(triangle) {
  clearCanvas();
  if (!tripartite) return;
  const { n, nums, abEdges, acEdges, bcEdges } = tripartite;

  const triSet = triangle
    ? new Set([triangle.i + ',A', triangle.j + ',B', triangle.k + ',C'])
    : new Set();
  const isTriEdge = (type, i, j) => {
    if (!triangle) return false;
    if (type === 'AB') return i === triangle.i && j === triangle.j;
    if (type === 'AC') return i === triangle.i && j === triangle.k;
    if (type === 'BC') return i === triangle.j && j === triangle.k;
    return false;
  };

  function drawEdges(edges, gA, gB, type) {
    edges.forEach(key => {
      const [ii, jj] = key.split(',').map(Number);
      const x1 = groupX(gA), y1 = vertexY(ii, n);
      const x2 = groupX(gB), y2 = vertexY(jj, n);
      const hi = isTriEdge(type, ii, jj);
      ctx.strokeStyle = hi ? '#e63946' : '#b0bec5';
      ctx.lineWidth = hi ? 2.2 : 1;
      ctx.globalAlpha = hi ? 1 : 0.55;
      ctx.beginPath(); ctx.moveTo(x1, y1); ctx.lineTo(x2, y2); ctx.stroke();
    });
    ctx.globalAlpha = 1;
  }

  drawEdges(abEdges, 0, 1, 'AB');
  drawEdges(acEdges, 0, 2, 'AC');
  drawEdges(bcEdges, 1, 2, 'BC');

  // Draw vertices for all 3 groups
  [0, 1, 2].forEach(g => {
    nums.forEach((v, i) => {
      const x = groupX(g), y = vertexY(i, n);
      const groupKey = i + ',' + ['A','B','C'][g];
      const inTriangle = triSet.has(groupKey);
      ctx.beginPath();
      ctx.arc(x, y, inTriangle ? 9 : 7, 0, 2 * Math.PI);
      ctx.fillStyle = inTriangle ? '#e63946' : '#1d3557';
      ctx.fill();
      ctx.fillStyle = '#fff';
      ctx.font = '700 9px ui-monospace';
      ctx.textAlign = 'center';
      ctx.textBaseline = 'middle';
      ctx.fillText(v, x, y);
    });
  });
  ctx.textBaseline = 'alphabetic';

  // Group labels
  ctx.fillStyle = '#5a7088';
  ctx.font = '700 11px system-ui';
  ctx.textAlign = 'center';
  ['A', 'B', 'C'].forEach((label, g) => {
    ctx.fillText(label, groupX(g), 14);
  });
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

document.getElementById('btn-new').addEventListener('click', generateInstance);
document.getElementById('btn-reduce').addEventListener('click', buildTripartite);
document.getElementById('btn-check').addEventListener('click', checkTriangles);

// Auto-start
generateInstance();
Result
Console

Click New instance to pick a random set of integers, then Run reduction to watch the tripartite graph appear. Check triangles highlights any triangle found. Notice: if you could detect triangles faster than O(n2)O(n^{2}) in this graph, you would solve 3SUM faster — that is the fine-grained reduction in action.

The Real Complexity

Fine-grained complexity rests on a small set of hardness conjectures and a growing web of reductions from them.

The Strong Exponential Time Hypothesis (SETH) — proposed by Impagliazzo and Paturi (1999, 2001) — states that for every ε>0\varepsilon > 0, there exists a kk such that kk-SAT cannot be solved in O(2(1−ε)n)O(2^{(1-\varepsilon)n}) time. No polynomial saving, not even shaving a tiny fraction from the exponent in the exponent. SETH is believed true but remains open.

The 3SUM conjecture states that deciding whether any three numbers in an nn-element set sum to zero requires Ω(n2)\Omega(n^2) time. Again, no truly sub-quadratic algorithm is known despite decades of effort.

From these two conjectures, reductions prove conditional lower bounds for many other problems:

  • Orthogonal Vectors (OV): under SETH, no O(n2−ε)O(n^{2-\varepsilon}) algorithm exists for deciding if two sets of bit-vectors contain an orthogonal pair. OV is the key bridge from SETH to string problems.
  • Longest Common Subsequence / Edit Distance: Backurs and Indyk (2015) and Abboud, Backurs, Williams (2015) showed that any O(n2−ε)O(n^{2-\varepsilon}) algorithm for LCS or edit distance would violate SETH. These are classic O(n2)O(n^{2}) dynamic-programming problems — the quadratic bound is tight under the hypothesis.
  • Triangle detection: an O(n2−ε)O(n^{2-\varepsilon}) algorithm for triangle detection in a dense graph would imply an O(n2−ε)O(n^{2-\varepsilon}) algorithm for Boolean matrix multiplication, believed impossible under SETH.
  • All-Pairs Shortest Paths (APSP): the cubic O(n3)O(n^{3}) bound is hard to break under the APSP conjecture; shaving even a logarithm seems out of reach.

What status? Open (conditional). The lower bounds are not absolute — they hold if SETH (or 3SUM) is true. But these conjectures are among the most widely believed in the field. Researchers have tried for decades to refute them; the best sub-quadratic 3SUM algorithm (Grønlund–Pettie, 2014) shaves only a poly-log factor. The web of fine-grained reductions mirrors NP-completeness inside polynomial time: one breakthrough would collapse dozens of barriers at once.

See also: P vs NP for the classical big boundary, and exponential time hypothesis for ETH, SETH's slightly weaker cousin.

Where It Matters

Fine-grained complexity is not an ivory-tower curiosity. The quadratic and cubic barriers it studies appear in systems used every day:

  • Genome alignment: computing the edit distance between DNA sequences is the inner loop of alignment tools like BLAST. The O(n2)O(n^{2}) bound has been engineering dogma for decades; fine-grained results explain why clever tricks haven't broken it.
  • Text diff tools: git diff, diff, and every merge tool use LCS as their backbone. The quadratic algorithm has been known since 1974 (Hunt–McIlroy); fine-grained complexity now certifies it is essentially optimal under SETH.
  • Routing and distance oracles: shortest-path precomputation in large networks has cubic cost in general. APSP lower bounds tell network designers that certain precomputation guarantees come with unavoidable costs.
  • Compiler analysis: data-flow analysis and alias detection can require all-pairs reachability — another problem governed by cubic or near-cubic bounds.
  • Databases: similarity joins (find all pairs of rows within edit distance k) inherit the quadratic barriers; database engineers benefit from knowing when approximation is the only practical path.

The broader lesson: when an algorithm has run at the same asymptotic cost for 40 years and no one has improved it, fine-grained complexity often explains why. It turns engineering folklore into a theorem — conditional on widely-believed conjectures.

Conclusion

Classical complexity theory told us which problems can be solved at all in reasonable time. Fine-grained complexity tells us which ones can be solved quickly. The two together give a far richer picture: even inside the comfortable land of polynomial algorithms, there are walls that seem just as solid as NP-hardness.

The central lesson is beautiful and a little unsettling. Edit distance, LCS, triangle detection, APSP — decades of algorithmic research have nudged their runtimes but never truly broken them. Fine-grained complexity explains why: under SETH and the 3SUM conjecture, a breakthrough would be a revolution. A refutation of either conjecture would be a bigger earthquake still.

Until then, the quadratic and cubic barriers stand — not as proven impossibilities, but as the best conditional lower bounds theoretical computer science can currently offer. That is enough to guide a generation of algorithm designers toward the problems where cleverness can still win, and away from those where the walls are almost certainly real.

Explore P vs NP for the classical landscape, and exponential time hypothesis for the sibling conjecture that launched much of this field.

Share this article

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

Comments

Loading comments...

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