Fine-Grained Complexity

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(n^{2})$ algorithm is a million times slower than an $O(n)$ one when n = $10^{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(n^k)$ time, can you do better — say $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.

The 3SUM problem asks: given n integers, do any three of them sum to zero? The classic algorithm checks all pairs in $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(n^{2.37\dots})$ using fast matrix multiplication, but for sparse graphs the practical barrier is $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">{{hint}}</p>
<div class="panels">
  <div class="panel" id="panel-numbers">
    <div class="panel-title">{{panel_3sum}}</div>
    <div id="numbers-display" class="number-list">—</div>
  </div>
  <div class="panel" id="panel-graph">
    <div class="panel-title">{{panel_graph}}</div>
    <canvas id="graph-canvas" width="340" height="180"></canvas>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="btn-new" type="button">{{btn_new}}</button>
  <button id="btn-reduce" type="button" disabled>{{btn_reduce}}</button>
  <button id="btn-check" type="button" disabled>{{btn_check}}</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; }

// Code not found

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(n^{2})$ in this graph, you would solve 3SUM faster — that is the fine-grained reduction in action.

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 $\varepsilon > 0$, there exists a $k$ such that $k$-SAT cannot be solved in $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 $n$-element set sum to zero requires $\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(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(n^{2-\varepsilon})$ algorithm for LCS or edit distance would violate SETH. These are classic $O(n^{2})$ dynamic-programming problems — the quadratic bound is tight under the hypothesis.
• Triangle detection: an $O(n^{2-\varepsilon})$ algorithm for triangle detection in a dense graph would imply an $O(n^{2-\varepsilon})$ algorithm for Boolean matrix multiplication, believed impossible under SETH.
• All-Pairs Shortest Paths (APSP): the cubic $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.

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(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.

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.