Exact edit-distance complexity

Change “cat” into “cut” by replacing a with u. That uses one edit, and zero edits cannot work because the strings differ. In this problem, inserting one character, deleting one character or replacing one character each costs one; the answer is the minimum cost over all ways to transform one string into the other.

Can the exact answer always be computed with a fixed improvement in the exponent over quadratic time, for arbitrary strings over a fixed finite alphabet? The improvement must persist as the total length of the two strings grows.[1]

Can the exact minimum number of character edits be found for all inputs with one fixed improvement over the quadratic exponent? For “cat” and “cut”, replacing a with u costs one and is optimal because a zero-cost transformation leaves the string unchanged. This is an example of edit distance, not evidence for a faster general algorithm.

Insertions, deletions and substitutions each cost one. With total input length $n=|X|+|Y|$, truly subquadratic means $O(n^{2-\varepsilon})$ for a positive constant $\varepsilon$ fixed independently of $n$. The target uses exact computation over a fixed finite alphabet in the stated standard RAM model. Special input families and approximation guarantees are separate requirements.[1]

Fast approximations do not return the exact answer; a general exponent improvement remains unknown.[2]

The Backurs–Indyk reduction rules out such an exact algorithm if SETH holds; SETH is an unproved hypothesis about the exponent of algorithms for Boolean satisfiability. This is a conditional obstruction, not an unconditional running-time lower bound.

The 2026 approximation scheme, read here in its author preprint, leaves the exact target unresolved. The September preprint on metric-weighted edit distance likewise gives a randomized approximation under its own cost model. Neither an approximation nor quadratic time divided by logarithmic factors meets the exact fixed-exponent target.[1] [2] [3]

Insertions and deletions shift how the remaining characters line up, so comparing only the characters currently opposite each other can miss the cheapest transformation. The exact minimum asks an algorithm to resolve competing alignments. This gives sequence comparison a structure beyond counting mismatches, and makes its running time a concrete question about how that structure can be used.[1] [2]

Dynamic programming makes the minimum over possible alignments finite and systematic: each prefix pair can be reached by an insertion, a deletion, or a character match/substitution from a smaller prefix pair. Shared prefix calculations avoid enumerating all edit sequences, but their grid still has a quadratic number of positions in the usual worst case. The exponent question asks whether further structure can avoid enough of that work while preserving the exact minimum.

SETH connects this local sequence problem to another search space. The established reduction would turn the proposed exponent improvement into a fixed exponent improvement for satisfiability. Its importance is that connection between algorithmic limits, while the hypothesis and the exact/approximate distinction remain explicit.[1] [2]