Why Can't Edit Distance Be Computed Faster?

The edit distance between two strings is the minimum number of single-character insertions, deletions, or substitutions needed to turn one into the other — the basis of spell-checkers, DNA sequence alignment, and diff tools. In 1974, Robert Wagner and Michael Fischer described a dynamic-programming algorithm that computes it in O(n²) time for strings of length n. For over 40 years afterward, nobody found anything meaningfully faster for the general problem, despite it being one of the most heavily studied problems in algorithms. The edit-distance fine-grained barrier is the proof of why.

A different kind of hardness proof

In 2015, Arturs Backurs and Piotr Indyk proved that a truly subquadratic algorithm for edit distance — one running in O(n^2−δ) time for any fixed δ > 0 — would imply a faster algorithm for Boolean satisfiability than is believed to exist under the Strong Exponential Time Hypothesis (SETH). SETH is a stronger, more specific conjecture than P ≠ NP: it says that satisfiability on n variables genuinely requires close to 2ⁿ time, not just “more than polynomial” time. This style of argument — a conditional lower bound tied to a specific exponent, not just a growth class — is the signature move of a subfield called fine-grained complexity.

What the barrier actually says

The Registry states the result as a conditional lower bound: solving edit distance requires n^2−o(1) time, assuming SETH. That’s deliberately not the same certainty as a proof that P ≠ NP would give — SETH could in principle be false — but SETH has resisted refutation for the exact string, satisfiability, and graph problems it’s been tested against for just as long as P ≠ NP has, which is why the field treats conditional lower bounds built on it as strong evidence rather than folklore.

Why it’s here

Most of the open problems in the Registry ask whether a faster algorithm could exist. Fine-grained barriers like this one instead pin down a specific exponent as the likely final answer, conditional on a named, actively studied assumption — a useful third category alongside “proven” and “unconditionally open.”

Primary source

Backurs & Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)” ↗