The Exponential Time Hypothesis and Fine-Grained Complexity

Symptom

You have a string algorithm. Edit distance between two sequences, the classic dynamic program, $O(n^2)$ time. It has been in production for years.

Now the inputs are genome-scale. At $n = 10^5$ characters, $n^2 = 10^{10}$ operations, about 10 seconds at a billion ops per second. At $n = 10^6$ it is $10^{12}$ operations, about 1000 seconds — seventeen minutes for one pair of strings. You need to do a million pairs.

So you go looking for a subquadratic algorithm. You find heuristics, bit-packing tricks worth a constant factor of 64, banded variants that assume the answer is small. What you do not find is an $O(n^{1.9})$ algorithm, and after a week you start wondering whether you are missing something obvious.

You are not. And the classical theory is useless here, because edit distance is in P. Polynomial time, solved, efficient by the standard everyone taught you. P vs NP has nothing to say about the gap between $n^2$ and $n^{1.9}$, and that gap is where your actual problem lives.

That is the hole fine-grained complexity fills. P vs NP asks whether a problem is tractable. Fine-grained complexity asks whether your particular exponent is optimal, and it answers with conditional lower bounds that are just as actionable.

Statement

Three hypotheses, in increasing strength.

ETH. 3-SAT cannot be solved in $2^{o(n)}$ time on formulas with $n$ variables.

SETH. For every $\epsilon > 0$ there is a $k$ such that $k$-SAT cannot be solved in $O((2-\epsilon)^n)$ time.

Fine-grained reductions transfer these lower bounds to problems in P.

SETH says brute force over $2^n$ assignments is essentially optimal — you can shave the base below 2 for any fixed $k$, but not by a constant that works for all $k$.

These are conjectures, and that is the honest framing. But they are load- bearing conjectures with decades of failed attacks, and a refutation would be a larger result than most people are trying to prove. Building on them is the same bet as building on the hardness of factoring.

Argument

Why ETH is plausible. Fifty years of SAT solving has produced enormous practical progress and no asymptotic progress. The best 3-SAT algorithms run in about $O(1.308^n)$ — Hertli’s refinement of Schöning’s random-walk algorithm. That is a real improvement over $2^n$: at $n = 50$, $1.308^{50} \approx 6.8 \times 10^5$ versus $2^{50} \approx 1.1 \times 10^{15}$, nine orders of magnitude. But it is still exponential, and the base has crept down glacially while the form has never changed.

The key move: fine-grained reductions. A classical reduction preserves polynomial-time solvability and is allowed to blow up the instance polynomially — which destroys exponent information and is why Karp reductions (T028) cannot answer this question. A fine-grained reduction preserves the exponent: it maps an instance of size $n$ to instances of size $O(n^{1+o(1)})$ such that an $O(n^{2-\epsilon})$ algorithm for the target yields an $O((2-\delta)^n)$ algorithm for SAT.

The hub problem: Orthogonal Vectors. Given two sets of $n$ vectors in ${0, 1}^d$, is there a pair with zero dot product? The obvious algorithm is $O(n^2 d)$.

SETH implies OV needs $n^{2-o(1)}$ time. Split the $n$ variables of a CNF formula in half. Enumerate all $2^{n/2}$ assignments to each half, and for each one build a $d$-bit vector recording which clauses it leaves unsatisfied. A pair of half-assignments is orthogonal exactly when together they satisfy every clause. So SAT becomes OV on $N = 2^{n/2}$ vectors, and an $O(N^{2-\epsilon})$ OV algorithm gives $O(2^{(1-\epsilon/2)n})$ for SAT, contradicting SETH.

And OV reduces into everything. Backurs and Indyk showed in 2015 that a truly subquadratic edit distance algorithm gives a subquadratic OV algorithm and therefore refutes SETH. The same holds for longest common subsequence, dynamic time warping, Fréchet distance, and local alignment. Your $O(n^2)$ edit distance dynamic program is optimal unless SETH is false, and that is a complete answer to the week you spent searching.

The other two roots. APSP: all-pairs shortest paths is conjectured to need $n^{3-o(1)}$, and negative-weight triangle, graph radius, and replacement paths are all equivalent to it — a subcubic algorithm for any one gives subcubic for all. 3SUM: given $n$ integers, are there three summing to zero? Conjectured $n^{2-o(1)}$, and it implies quadratic lower bounds across computational geometry, including collinearity testing and polygon containment.

Three conjectures, one reduction web, and most everyday polynomial problems hang off one of them.

A worked reduction, so the transfer is concrete. Take the SETH-to-OV argument and put numbers on it. A CNF formula with $n = 60$ variables and $d = 200$ clauses splits into two halves of 30 variables each. Enumerating one half gives $2^{30} \approx 1.07 \times 10^9$ assignments, and each becomes a 200-bit vector marking which clauses that half fails to satisfy.

A pair of vectors is orthogonal exactly when no clause is left unsatisfied by both halves — that is, when the combined assignment satisfies the formula. So the OV instance has $N = 2^{30}$ vectors, and $N^2 = 2^{60}$, which is precisely the brute-force SAT cost. Nothing has been gained yet.

The leverage is in what a faster OV algorithm would mean. An $O(N^{1.9})$ algorithm would solve this SAT instance in $2^{57}$ steps, and more importantly in $2^{0.95n}$ steps for every $n$. That is a base of $2^{0.95} \approx 1.93$ rather than 2, uniformly across all clause widths, which is exactly what SETH says is impossible. The reduction converts a modest polynomial improvement on a quadratic problem into a modest exponential improvement on SAT, and the reason the exponents line up is the halving: squaring $2^{n/2}$ recovers $2^n$, so an exponent below 2 downstream is an exponential base below 2 upstream.

This is why fine-grained reductions must be near-linear in the instance size. A reduction that blew the instance up to $N^{1.5}$ would dilute the exponent saving to nothing, which is exactly what classical Karp reductions do and why they cannot see this structure.

Forbids

Subquadratic edit distance, LCS, dynamic time warping, and Fréchet distance, unless SETH fails.

Subcubic all-pairs shortest paths, unless the APSP conjecture fails. Floyd-Warshall’s exponent is not laziness. Williams’ $n^3/2^{\Theta(\sqrt{\log n})}$ shaves a subpolynomial factor and stops there.

Subquadratic 3SUM and its geometric descendants, unless 3SUM fails.

$2^{o(n)}$ algorithms for 3-SAT, vertex cover, Hamiltonian path, and graph colouring, unless ETH fails. ETH also rules out $n^{o(k)}$ for $k$-clique, which is the lower-bound half of parameterized complexity (T033) — W[1]-hardness becomes a concrete time bound rather than just a class membership.

A subexponential-time approximation scheme for many problems, via ETH-based lower bounds on PTAS running times, which is a sharper statement than the inapproximability of T031.

Does not forbid

It does not forbid fast edit distance in practice, and treating the lower bound as a reason not to optimize is the misreading that costs the most real performance. Myers’ bit-vector algorithm processes 64 cells per word operation, a genuine 64x speedup that leaves the exponent untouched. Landau- Vishkin runs in $O(nk)$ when the edit distance is at most $k$, which is fast whenever the strings are similar — the usual case in bioinformatics. Minimap2 and BLAST align genomes daily by seeding and filtering so the quadratic kernel only ever runs on short candidate regions. Asymptotic optimality says nothing about constants, parameters, or input structure.

It does not forbid approximation. Edit distance is approximable within a constant factor in near-linear time — Andoni and Nosatzki reached $O(n^{1+ \epsilon})$ in 2020. The lower bound is for exact computation, and relaxing exactness escapes it completely. This is the single most useful escape and it is routinely forgotten.

It does not mean SETH is true. It is a conjecture, and there is real doubt. SETH has already been refuted in restricted settings, and Ryan Williams — who proved several of the strongest SETH-based results — has said publicly he suspects it is false. The results are all stated conditionally for exactly this reason, and a refutation would be a triumph rather than an embarrassment.

It does not apply to quantum algorithms directly. Grover gives $O(2^{n/2})$ for SAT, which violates SETH’s classical form; the quantum analogue QSETH is formulated separately and is much less studied.

It does not forbid better algorithms for structured inputs. These are worst-case bounds. Real strings have low edit distance, real graphs are sparse and often planar, and real geometric inputs are not adversarial. Parameterized algorithms (T033) exploit this systematically, and the fine-grained bounds are what tell you which parameter to reach for.

Boundary

The conjectures sit in a hierarchy, and knowing which one your lower bound rests on tells you how much to trust it:

• $\mathsf{P} \ne \mathsf{NP}$ — weakest, most believed.
• ETH — implies the above; rules out subexponential exact algorithms.
• SETH — implies ETH; the least believed of the three, and the one carrying the most quadratic lower bounds.
• APSP and 3SUM conjectures — independent of the SAT-based ones, each anchoring its own equivalence class.

What the field genuinely delivers is a shift in what “I cannot find a better algorithm” means. Before fine-grained complexity, that was a statement about your week. After it, you can often prove it is a statement about the problem, conditional on a hypothesis you were implicitly relying on anyway. And when the answer comes back “your exponent is optimal,” the productive next moves are named and finite: approximate it, parameterize it, exploit structure, or buy constants. That is a far better place to end a week than where this post started.

Read next