If SETH holds, edit distance can’t beat n². Split-and-list, orthogonal vectors, and lower bounds for problems already in P
Complexity theory usually asks “polynomial or not?” Fine-grained complexity asks which polynomial: is n² really the best possible for edit distance, or n³ for shortest paths? Assuming SETH and a few other hypotheses, researchers have shown that many textbook algorithms are optimal — conditionally.
Hover over the grid: each cell pairs half an assignment with the other half, and it turns green exactly when the two clause vectors are orthogonal. Press “Check every pair” and count the green cells against the satisfying assignments.
Rows on the left are the 2⁴ assignments α to the first half of the variables; columns on top are the assignments β to the second half. Each carries one bit per clause, rose when that half leaves the clause unsatisfied. Grid cells are green when uα · vβ = 0, and redder the more clauses both halves miss. Hover or tap a cell; the fuchsia strips mark the clauses neither half satisfies. In the clause list, green clauses are satisfied by the selected pair.
In 2005 Ryan Williams found a way to turn a CNF formula into a problem about vectors. Split the n variables into two halves. For each of the 2n/2 assignments α to the first half, write down an m-bit vector uα with a 1 in position j when α leaves clause j unsatisfied; do the same for the second half. A full assignment α ∪ β satisfies the formula exactly when no clause is missed by both halves — when uα · vβ = 0. Satisfiability has become Orthogonal Vectors (OV): given N vectors on each side, is some pair orthogonal?
Here N = 2n/2 and the trivial algorithm checks N² = 2ⁿ pairs, no better than brute force. But an OV algorithm running in N2−ε time would solve SAT in about 2(1−ε/2)n time, for every clause width k. That is exactly what the Strong Exponential Time Hypothesis forbids. The dimension matters: after the sparsification lemma of Impagliazzo, Paturi and Zane, m can be taken to be O(n), so the vectors have dimension d = O(log N).
The OV hypothesis says there is no N2−ε · poly(d) algorithm once d grows faster than log N. Williams’s reduction proves that SETH implies it. The converse is not known, so OV could stay hard even if SETH failed. The best algorithm known, by Abboud, Williams and Yu (2015), handles dimension d = c log N in time N2 − 1/O(log c): a little below quadratic, but with a saving that shrinks as c grows, so not N2−ε for any fixed ε.
Press Play and watch each cell take the best of its three neighbours, then follow the traceback to the alignment. Switch to random DNA, drag the length up, and see where the cell count lands on the chart.
Cell (i, j) holds the answer for the first i letters of s and the first j letters of t, computed from its three neighbours above and to the left (outlined amber). Arrows show the choice: green diagonal = match, amber diagonal = substitution, rose up = delete, sky left = insert. When the table is full the fuchsia path traces back an optimal alignment, shown above the chart. Hover or tap any filled cell to see its calculation.
Edit distance is the fewest insertions, deletions and substitutions turning one string into another; Vladimir Levenshtein defined it in 1966. The table method shown here was published by Robert Wagner and Michael Fischer in 1974: (n + 1)(m + 1) cells, each a constant amount of work, so O(n²) time for two strings of length n. In 1980 William Masek and Mike Paterson used the “Four Russians” trick of precomputing small blocks to reach O(n²/log² n). Nothing essentially faster has been found since — only that log factor.
In 2015 Arturs Backurs and Piotr Indyk explained why (STOC 2015; SIAM Journal on Computing, 2018): an O(n2−ε) algorithm for edit distance, for any ε > 0, would refute SETH. Their reduction builds, from an OV instance, two strings whose edit distance reveals whether an orthogonal pair exists. The same year Abboud, Backurs and Vassilevska Williams, and independently Bringmann and Künnemann, proved the same for the longest common subsequence. The chart shows what is at stake: two 3-billion-letter genomes would need about 9 × 10¹⁸ cells.
That is why practical tools such as BLAST use heuristics, approximations, or restrictions such as a bounded number of edits, rather than the exact quadratic table. The lower bound says which way to look: exact edit distance on arbitrary long strings is not going to get dramatically faster unless SETH is false.
Click a hypothesis to light up the problems it holds down, then click a problem for its card. Toggle “Assume SETH false” and watch which lower bounds disappear — and that no running time changes.
For every ε > 0 there is a k such that k-SAT on n variables cannot be solved in time O(2(1−ε)n). The savings of the best k-SAT algorithms shrink to nothing as k grows.
Click any box for its card. Clicking a hypothesis lights up everything resting on it; clicking a problem lights its chain back to a hypothesis. An arrow means a fast algorithm for the lower problem would refute the one above; double-headed arrows are subcubic equivalences, where a truly subcubic algorithm for either side gives one for the other. Struck-through hypotheses are assumed false and their dependents turn grey — they lose their lower bounds, but their best known running times (amber in the card) do not move.
Three hypotheses carry most of the field. SETH concerns k-SAT. The 3SUM hypothesis says that deciding whether three of n integers sum to zero needs n2−o(1) time; Gajentaan and Overmars (1995) showed many geometric problems, such as finding three collinear points, are at least as hard. The best 3SUM algorithm, by Grønlund and Pettie (2014), saves only a factor of about (log n / log log n)2/3. The APSP hypothesis says all-pairs shortest paths with integer weights needs n3−o(1) time. Ryan Williams’s 2014 algorithm runs in n³ / 2Ω(√log n) — faster than n³ / logᶜ n for every c, yet not n3−ε. Vassilevska Williams and Williams (2010) showed that APSP, min-plus product, negative triangle and replacement paths are subcubically equivalent: a truly subcubic algorithm for one gives one for all. None of the three hypotheses is known to imply another.
Virginia Vassilevska Williams’s survey for the 2018 International Congress of Mathematicians, “On some fine-grained questions in algorithms and complexity”, maps the field in detail. One caveat runs through all of it: these are worst-case statements. A conditional lower bound says no algorithm is fast on every input; it says nothing about the inputs that occur in practice, which may be far easier.
In October 2026 two AI labs, OpenAI and Anthropic, posted claimed algorithms, formalised in Lean but not yet peer reviewed, that count the solutions of a k-CNF formula in about 2O(n log log n / √log n) time. The claims are unverified and under review. If they hold, SETH is false, along with ETH, and the SETH-based lower bounds lose that foundation. Most of them, though, are really proved from the OV hypothesis, which SETH implies but which is not known to fall with it — the toggle in the demo models this. No algorithm in the web gets faster either way. The shape of the claimed saving resembles Williams’s n³ / 2Ω(√log n) for APSP, though that is a resemblance of form only. See also A Claimed Refutation.
Spot a mistake or have an idea?