A floor that holds if something else does

Every edit-distance table on this site is $\Theta(nm)$ cells and nobody has ever found a way to compute the distance that is not. That is a fact about the state of the art and it is not, by itself, an argument.

This collection has four arguments that a cost cannot be avoided, and each of them is a proof. Comparison sorting cannot use fewer than $\log_2 n!$ comparisons because a decision tree with fewer leaves cannot distinguish the orderings. Connectivity cannot examine fewer than every edge, because an adversary can hide the answer in whichever one an algorithm skips. An exact one-pass distinct count needs $\log_2 \binom{u}{u/2}$ bits and an exact count over a window of $W$ needs $W$ bits, because two inputs that must be answered differently and are held in the same state cannot be.

Nothing of that kind is known about edit distance. What is known is different in kind, and marking the difference is the whole point of this essay.

What the top of the chain says #

Satisfiability of a formula in conjunctive normal form with $n$ variables can be decided by trying all $2^n$ assignments. For clauses of length $k$ there are algorithms faster than that — for 3-CNF the best known are around $1.31^n$ — and they get closer to $2^n$ as $k$ grows.

The strong exponential time hypothesis is the conjecture that they cannot escape: that for every $\varepsilon > 0$ there is a $k$ for which no algorithm solves $k$-SAT in $2^{(1-\varepsilon)n}$ time. Informally, exhaustive search over assignments is essentially optimal once the clauses are long enough.

It is a conjecture. It has stood for two decades, a great deal is built on it, and nobody has proved it or refuted it.

The link that can be performed #

The first step from that conjecture to anything about strings is split and list, and it is short enough to do here in full.

Take a formula with $n$ variables and $d$ clauses. Split the variables into two halves. For each of the $2^{n/2}$ assignments to the first half, write down a vector of $d$ bits whose entry is 1 exactly where that half fails to satisfy the clause. Do the same for the second half.

Now a pair of vectors — one from each list — is orthogonal, meaning no coordinate is 1 in both, exactly when every clause is satisfied by one half or the other. Which is exactly when the two halves together satisfy the formula.

So: the formula is satisfiable if and only if the two lists contain an orthogonal pair.

Checked by exhaustion, and the trap that check fell into #

A reduction that is right on the formulas somebody thought to try is not a reduction. So this one is checked over every formula of a stated small size rather than over a sample: all formulas on four variables built from at most five of the twenty-four possible two-literal clauses, plus three hundred larger random instances, with brute-force satisfiability and the orthogonal-pair search required to agree on each.

55,754 formulas. 54,706 satisfiable, 1,048 not. No disagreement.

The first version of that check tested nothing at all, and the way it failed is worth recording because it is the failure a sweep is most likely to have.

It enumerated formulas on four variables from at most three clauses of length three — 5,488 of them — and every single one was satisfiable. Four variables give sixteen assignments and three clauses of three literals can rule out at most three of them, so there is nothing to find. A reduction that reported satisfiable unconditionally, without looking at anything, would have passed 5,488 times out of 5,488.

The gate now requires both answers to occur, in the exhaustive part and in the sampled part separately, and it carries the vacuous case as a rejection: a sweep in which every instance has the same answer must fail, whatever the reduction does.

That is the same rule this collection applies everywhere — an assertion that has never rejected anything proves nothing — arriving in a place where it is unusually easy to miss, because the sweep looked large.

Why go through orthogonal vectors at all #

It would be tidier to reduce satisfiability to edit distance directly. The reason nobody does is that orthogonal vectors is a hub.

The problem is simple enough to reduce from easily — two lists of bit vectors, find a pair sharing no coordinate — and it sits at the bottom of a long list of quadratic-looking problems that turn out to be reducible from it. The same conjecture, through the same intermediate problem, gives conditional quadratic bounds for the longest common subsequence, for dynamic time warping, for the diameter of a sparse graph, and for a good many others.

So the work of connecting a conjecture about satisfiability to a fact about strings is done once, at the hub, and each subsequent bound is one gadget construction rather than a fresh argument about assignments. This essay performs the shared half and quotes the specific half, which is where the boundary between what can be checked here and what cannot happens to fall.

The reduction is exponential, and that is not a problem #

One thing about split-and-list looks wrong at first sight and is worth resolving, because it is the commonest confusion about arguments of this kind.

The reduction writes down $2^{n/2}$ vectors. That is exponential in the size of the formula. If it were an algorithm it would be a bad one.

It is not an algorithm; it is a translation used inside a proof by contradiction. The argument is: suppose a fast orthogonal-vectors algorithm existed. Then, given a formula, spend $2^{n/2}$ time building the lists — which is already less than the $2^n$ that exhaustive search would spend — and run the fast algorithm on them. The total is $2^{n/2} + N^{2-\varepsilon}$, which is $2^{(1-\varepsilon/2)n}$, which contradicts the hypothesis.

The exponential step is affordable precisely because the thing being contradicted is also exponential. A reduction only has to be cheaper than the bound it is arguing about, and here it is cheaper by a square root.

The identity that makes it a bound #

The reduction being correct makes it a translation. What makes it a lower bound is arithmetic about its size.

Each list holds $2^{n/2}$ vectors. A quadratic scan compares every vector on one side against every vector on the other, which is

$$2^{n/2} \times 2^{n/2} = 2^n$$

comparisons — exactly the number of assignments exhaustive search would try. Not asymptotically, not up to constants: the same integer.

So an algorithm for orthogonal vectors running in $N^{2-\varepsilon}$ time, on $N = 2^{n/2}$ vectors, would decide satisfiability in $2^{(1-\varepsilon/2)n}$ — beating exhaustive search by a constant in the exponent, for every $k$, which is what the hypothesis says is impossible.

If SETH holds, orthogonal vectors needs $N^{2-o(1)}$. That implication is performed here.

The link that is quoted #

The second step — from orthogonal vectors to edit distance — is not performed here, and the plate says so in as many words.

The construction encodes each vector as a string, concatenates one list into one long string and the other into another, and arranges the costs so that the edit distance between the two long strings reveals whether an orthogonal pair existed. It works, it is not long, and it needs the gadgets separated by enough padding that no optimal alignment can cross a boundary in an unintended way. The smallest instance that demonstrates the property is far past anything a small exhaustive search can walk.

Which leaves two options: build it and check it on instances too small to be conclusive, or quote it and say so. This collection quotes it and says so, for the same reason the approximate space floor for streaming is quoted rather than demonstrated: a figure that measured something adjacent and let the reader assume the rest would be worse than a citation, because a citation is honest about what it is.

So the marks differ. A solid arrow for the link performed, a dashed one for the link quoted, and the word quoted on the plate.

What the conclusion actually is #

Putting the chain together: if SETH is true, there is no algorithm computing edit distance in $O(n^{2-\varepsilon})$ time for any constant $\varepsilon > 0$.

Four things about that sentence are worth pinning down, because each of them is a place the statement is routinely over-read.

It is conditional. If SETH is false the bound says nothing. Somebody may refute SETH tomorrow, and the day after that a sub-quadratic edit distance would be a thing worth looking for rather than a thing ruled out.

It forbids a constant in the exponent, not any improvement. An algorithm running in $O(n^2 / \log^2 n)$ — which exists, for constant alphabets — is entirely consistent with it, because $n^2/\log^2 n$ is not $O(n^{2-\varepsilon})$ for any constant $\varepsilon$. Logarithmic savings are permitted and have been taken.

It is about the worst case and about exactness. Approximation escapes it; so does any restriction on the input. A band of width $2k+1$ computes the exact distance in $O(nk)$ whenever the answer is at most $k$, which on nearly-identical strings is nearly linear. The bound is about instances chosen adversarially, and nothing in it says a particular pair of strings is hard.

It is falsifiable in a specific direction. Somebody who produces a genuinely sub-quadratic exact worst-case edit distance has not merely improved an algorithm — they have refuted SETH, and with it a large family of conditional bounds resting on the same conjecture. That is what a conditional lower bound is for: it converts “nobody has managed it” into “managing it would settle something else”.

What it does not say about any particular table #

There is a reading of this bound that is tempting and wrong, and it is worth blocking explicitly because every other floor on this site invites it correctly.

The comparison-sorting floor is about a specific run: given $n$ elements, this run made this many comparisons, and the floor is $\log_2 n!$, and the gap between them is a number about that run. Every plate in the floors field is drawn that way, with a measurement and a line and a distance between them.

Nothing of the kind is available here. The conditional bound is a statement about the asymptotic worst case of any algorithm, so it does not apply to a table, to a pair of strings, or to a run. There is no line to draw beside a measured cell count, and a plate that drew one would be inventing a comparison.

What can honestly be drawn beside a measurement is the shape — the quadratic curve every method in the tables field sits on — with the bound stated as a sentence about that curve’s exponent rather than as a rule on the plot. Which is why the plates in this essay are about the reduction and about the arithmetic, and none of them puts a floor under a measured algorithm.

That is a limitation of the bound rather than of the drawing, and it is shared by every conditional bound of this kind. They rule out a family of algorithms; they say nothing about the particular one being run.

The company it keeps #

Set the four unconditional floors beside it and the difference is visible in what each one rests on.

A conditional bound is a map of the escapes #

The four clauses above say what the bound does not forbid, and reading them together turns a negative result into something more useful than a warning: a list of the directions in which progress is still possible, each of which this collection has already taken.

Constant factors are permitted, because $n^2/w$ is not $O(n^{2-\varepsilon})$. Taken: a column computed in machine words divides the work by the register width and is entirely consistent with the bound.

Parameterised savings are permitted, because the bound is about the worst case over all inputs and a parameterised algorithm is fast when its parameter is small. Taken: a band as wide as the answer is $\Theta(nd)$ and is nearly linear on the near-identical strings that are most of the real workload.

Average-case savings are permitted, for the same reason. Taken: a filter over an index computes a few hundred windows instead of the rectangle, on text where the seeds are selective.

Approximation is permitted. Not taken here, and it is the one direction this collection has not gone — approximating an edit distance to within a constant factor in sub-quadratic time is a real line of work and nothing on this site touches it.

Read that way the conditional bound is doing exactly what a good negative result should: it says the frontal assault is ruled out, and it says precisely which flanks are open, because each clause of the statement is a door. A bound with no conditions in it would be a wall; a bound with four conditions is a map.

It also explains why the tables field looks the way it does. Every method in it is one of those escapes, and none of them is an attempt at the thing the bound forbids — not because anybody consulted the bound before writing them, but because the escapes are where the achievable results are, and the bound is the statement of why.

More than one conjecture, and which one a bound rests on #

One more thing about conditional bounds is worth stating, because it decides how much weight a particular one carries.

SETH is not the only hypothesis of its kind. Fine-grained complexity rests on a small number of them — that three numbers summing to zero cannot be found in sub-quadratic time, that all-pairs shortest paths cannot be computed in sub-cubic time, and SETH itself — and different problems are hard under different ones. A quadratic bound conditional on the 3SUM hypothesis and a quadratic bound conditional on SETH are not the same claim, and a problem can be hard under one while nothing is known about it under another.

The consequence is a ranking that is easy to miss: a bound resting on a weaker conjecture is a stronger result. If a problem is hard unless a widely-doubted hypothesis fails, that is weak evidence; if it is hard unless a hypothesis everybody believes fails, that is strong evidence; and if two bounds for the same problem rest on two independent conjectures, the problem is hard unless both fail, which is stronger than either alone.

None of that is demonstrated here, and it is stated because a reader who takes away “edit distance has a conditional lower bound” has taken away a sentence with a variable in it. The premise is part of the claim, the premises differ in how much they are believed, and quoting a conditional bound without its condition is the same omission this collection has spent an entire field cataloguing — arriving, this time, in the one place where the omitted clause is the load-bearing half of the sentence.

What was added here #

A fifth kind of lower-bound argument, and the first on this site that is conditional.

The first four are a counting argument, an adversary argument, and two arguments about the number of memory states a machine must occupy. Each of them ends in a proof, and each is demonstrated here by exhaustive construction — the decision tree is counted, the adversary’s hidden edge is produced, the colliding memory states are found and the input that separates them is printed.

This one ends in a conjecture. What is demonstrated is one link of it, exactly, over every formula of a stated size, with the vacuous version of the same check carried as a rejection so that the sweep cannot pass by being empty. What is quoted is the other link, marked as quoted, on a plate that draws the two differently.

That last clause is the essay. A bound with a premise is a different object from a bound without one, they are quoted in the same words, and a collection that draws them the same way is telling its reader something false about how much is known.