Edit Distance Is SETH-Hard

Autocorrect, spell-checkers, DNA sequence aligners, plagiarism detectors — all of them share a common engine: edit distance (also called Levenshtein distance). Given two strings, it counts the minimum number of single-character insertions, deletions, or substitutions needed to transform one into the other.

The classic algorithm, discovered independently by Vladimir Levenshtein in 1965 and by Wagner & Fischer in 1974, fills an n×m dynamic-programming table and runs in $O(n \cdot m)$ time — quadratic when both strings have the same length n. Decades of smart researchers tried to do better. They failed.

In 2015, Artūrs Backurs and Piotr Indyk explained why: a truly sub-quadratic edit distance algorithm — one running in $O(n^{2-\varepsilon})$ for any $\varepsilon > 0$ — would refute the Strong Exponential Time Hypothesis (SETH). SETH says that k-SAT cannot be solved much faster than brute force, no matter how large k grows. Believing SETH (which most complexity theorists do) means believing the quadratic wall is real — not a failure of imagination, but a fundamental limit.

This is fine-grained complexity: instead of coarse NP-hardness, it gives precise conditional lower bounds that match the best known algorithm almost exactly.

Type two strings below and watch the dynamic-programming table fill in. Each cell (i, j) holds the edit distance between the first i characters of the top string and the first j characters of the side string. The answer appears in the bottom-right corner.

<div class="hint">Type two strings to see the edit-distance DP table. Each cell (i,j) is the cost to turn the first <em>i</em> characters of <b>A</b> into the first <em>j</em> of <b>B</b>. The answer is in the bottom-right.</div>
<div class="inputs">
  <label>A: <input id="strA" type="text" value="kitten" maxlength="14" /></label>
  <label>B: <input id="strB" type="text" value="sitting" maxlength="14" /></label>
</div>
<div id="result" class="result"></div>
<div id="tableWrap" class="table-wrap"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin-bottom: .6rem; line-height: 1.45; }
.inputs { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .7rem; }
.inputs label { font-size: .9rem; font-weight: 600; display: flex; align-items: center; gap: .4rem; }
.inputs input { font: inherit; border: 1.5px solid #adb5bd; border-radius: 6px; padding: .3rem .5rem; width: 130px; }
.result { font-size: 1rem; font-weight: 700; margin-bottom: .6rem; min-height: 1.4em; color: #1d3557; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; font-size: .8rem; }
th, td { width: 30px; height: 30px; text-align: center; vertical-align: middle; border: 1px solid #dee2e6; }
thead th { background: #e8eef3; font-weight: 700; color: #1d3557; }
tbody th { background: #e8eef3; font-weight: 700; color: #1d3557; }
td { background: #f8fafc; color: #333; }
td.diag { background: #d4edda; color: #155724; font-weight: 700; }
td.answer { background: #1d3557; color: #fff; font-weight: 700; border-radius: 4px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Levenshtein edit distance via standard DP.
// dp[i][j] = edit distance between a[0..i-1] and b[0..j-1].
// Recurrence: dp[i][j] = dp[i-1][j-1]            if a[i-1]===b[j-1]
//                       = 1 + min(dp[i-1][j],     // delete from a
//                                 dp[i][j-1],     // insert into a
//                                 dp[i-1][j-1])   // substitute
function editDistance(a, b) {
  const n = a.length, m = b.length;
  const dp = Array.from({length: n+1}, (_, i) => Array.from({length: m+1}, (_, j) => i===0 ? j : j===0 ? i : 0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; j++)
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
  return dp;
}

function render() {
  const a = document.getElementById('strA').value.slice(0, 14);
  const b = document.getElementById('strB').value.slice(0, 14);
  const dp = editDistance(a, b);
  const dist = dp[a.length][b.length];

  document.getElementById('result').textContent =
    fmt('Edit distance: %dist%  |  Table size: %v% × %v2% = %v3% cells', { dist: dist, v: a.length+1, v2: b.length+1, v3: (a.length+1)*(b.length+1) });

  // Build table
  const wrap = document.getElementById('tableWrap');
  const tbl = document.createElement('table');

  // Header row: '' | '' | b chars
  const thead = document.createElement('thead');
  const hr = document.createElement('tr');
  [' ', ' ', ...b.split('')].forEach((ch, i) => {
    const th = document.createElement('th'); th.textContent = ch; hr.appendChild(th);
  });
  thead.appendChild(hr); tbl.appendChild(thead);

  // Body rows
  const tbody = document.createElement('tbody');
  for (let i = 0; i <= a.length; i++) {
    const tr = document.createElement('tr');
    // row label
    const lbl = document.createElement('th');
    lbl.textContent = i === 0 ? ' ' : a[i-1];
    tr.appendChild(lbl);
    for (let j = 0; j <= b.length; j++) {
      const td = document.createElement('td');
      td.textContent = dp[i][j];
      if (i === a.length && j === b.length) td.className = 'answer';
      else if (i > 0 && j > 0 && a[i-1] === b[j-1] && dp[i][j] === dp[i-1][j-1]) td.className = 'diag';
      tr.appendChild(td);
    }
    tbody.appendChild(tr);
  }
  tbl.appendChild(tbody);
  wrap.innerHTML = ''; wrap.appendChild(tbl);
}

document.getElementById('strA').addEventListener('input', render);
document.getElementById('strB').addEventListener('input', render);
render();

// Verification log (for node test): editDistance("kitten","sitting")[6][7] === 3
// editDistance("","abc")[0][3] === 3, editDistance("abc","abc")[3][3] === 0
console.log('kitten->sitting:', editDistance('kitten','sitting')[6][7]);
console.log('empty->abc:', editDistance('','abc')[0][3]);
console.log('abc->abc:', editDistance('abc','abc')[3][3]);
console.log('abc->:', editDistance('abc','')[3][0]);

<div class="hint">Type two strings to see the edit-distance DP table. Each cell (i,j) is the cost to turn the first <em>i</em> characters of <b>A</b> into the first <em>j</em> of <b>B</b>. The answer is in the bottom-right.</div>
<div class="inputs">
  <label>A: <input id="strA" type="text" value="kitten" maxlength="14" /></label>
  <label>B: <input id="strB" type="text" value="sitting" maxlength="14" /></label>
</div>
<div id="result" class="result"></div>
<div id="tableWrap" class="table-wrap"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin-bottom: .6rem; line-height: 1.45; }
.inputs { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .7rem; }
.inputs label { font-size: .9rem; font-weight: 600; display: flex; align-items: center; gap: .4rem; }
.inputs input { font: inherit; border: 1.5px solid #adb5bd; border-radius: 6px; padding: .3rem .5rem; width: 130px; }
.result { font-size: 1rem; font-weight: 700; margin-bottom: .6rem; min-height: 1.4em; color: #1d3557; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; font-size: .8rem; }
th, td { width: 30px; height: 30px; text-align: center; vertical-align: middle; border: 1px solid #dee2e6; }
thead th { background: #e8eef3; font-weight: 700; color: #1d3557; }
tbody th { background: #e8eef3; font-weight: 700; color: #1d3557; }
td { background: #f8fafc; color: #333; }
td.diag { background: #d4edda; color: #155724; font-weight: 700; }
td.answer { background: #1d3557; color: #fff; font-weight: 700; border-radius: 4px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Levenshtein edit distance via standard DP.
// dp[i][j] = edit distance between a[0..i-1] and b[0..j-1].
// Recurrence: dp[i][j] = dp[i-1][j-1]            if a[i-1]===b[j-1]
//                       = 1 + min(dp[i-1][j],     // delete from a
//                                 dp[i][j-1],     // insert into a
//                                 dp[i-1][j-1])   // substitute
function editDistance(a, b) {
  const n = a.length, m = b.length;
  const dp = Array.from({length: n+1}, (_, i) => Array.from({length: m+1}, (_, j) => i===0 ? j : j===0 ? i : 0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; j++)
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
  return dp;
}

function render() {
  const a = document.getElementById('strA').value.slice(0, 14);
  const b = document.getElementById('strB').value.slice(0, 14);
  const dp = editDistance(a, b);
  const dist = dp[a.length][b.length];

  document.getElementById('result').textContent =
    fmt('Edit distance: %dist%  |  Table size: %v% × %v2% = %v3% cells', { dist: dist, v: a.length+1, v2: b.length+1, v3: (a.length+1)*(b.length+1) });

  // Build table
  const wrap = document.getElementById('tableWrap');
  const tbl = document.createElement('table');

  // Header row: '' | '' | b chars
  const thead = document.createElement('thead');
  const hr = document.createElement('tr');
  [' ', ' ', ...b.split('')].forEach((ch, i) => {
    const th = document.createElement('th'); th.textContent = ch; hr.appendChild(th);
  });
  thead.appendChild(hr); tbl.appendChild(thead);

  // Body rows
  const tbody = document.createElement('tbody');
  for (let i = 0; i <= a.length; i++) {
    const tr = document.createElement('tr');
    // row label
    const lbl = document.createElement('th');
    lbl.textContent = i === 0 ? ' ' : a[i-1];
    tr.appendChild(lbl);
    for (let j = 0; j <= b.length; j++) {
      const td = document.createElement('td');
      td.textContent = dp[i][j];
      if (i === a.length && j === b.length) td.className = 'answer';
      else if (i > 0 && j > 0 && a[i-1] === b[j-1] && dp[i][j] === dp[i-1][j-1]) td.className = 'diag';
      tr.appendChild(td);
    }
    tbody.appendChild(tr);
  }
  tbl.appendChild(tbody);
  wrap.innerHTML = ''; wrap.appendChild(tbl);
}

document.getElementById('strA').addEventListener('input', render);
document.getElementById('strB').addEventListener('input', render);
render();

// Verification log (for node test): editDistance("kitten","sitting")[6][7] === 3
// editDistance("","abc")[0][3] === 3, editDistance("abc","abc")[3][3] === 0
console.log('kitten->sitting:', editDistance('kitten','sitting')[6][7]);
console.log('empty->abc:', editDistance('','abc')[0][3]);
console.log('abc->abc:', editDistance('abc','abc')[3][3]);
console.log('abc->:', editDistance('abc','')[3][0]);

Notice that every cell depends on its three neighbors — left, above, and diagonal. The table has n × m cells, so the algorithm does exactly that much work. There is no known shortcut that avoids filling most of the table, and the SETH lower bound suggests none exists.

Edit distance sits in fine-grained complexity, a field that trades coarse "NP-hard" labels for precise conditional lower bounds tied to specific conjectures.

• The classic algorithm is $O(n^{2})$ (or $O(n \cdot m)$ for strings of length n and m). Many variants exist — Ukkonen's band-optimization, Four-Russians speedups — but all require $\Omega(n^2 / \text{polylog}\, n)$ time in the worst case.
• SETH — the Strong Exponential Time Hypothesis — conjectures that for every $\varepsilon > 0$ there exists k such that k-SAT cannot be solved in $O(2^{(1-\varepsilon)n})$ time. It implies that CNF-SAT has no sub-exponential algorithm, making it a sharper claim than $P \ne NP$.
• The Backurs–Indyk reduction (2015): They showed that if edit distance on length-n strings can be computed in $O(n^{2-\varepsilon})$ time, then k-SAT on n variables can be solved in $O(2^{(1-\delta)n})$ time for some $\delta > 0$ depending on $\varepsilon$ — directly refuting SETH. The reduction transforms a SAT instance into two carefully encoded strings whose edit distance encodes satisfiability.
• Status: conditionally proven (2015). The lower bound is as strong as SETH itself. If SETH holds (believed by most experts), edit distance genuinely cannot be solved much faster than $O(n^{2})$.

This places edit distance alongside sequence alignment, longest common subsequence, and RNA folding as problems whose quadratic algorithms are not just the best we have — they are likely the best possible. SETH thus explains decades of failed attempts in a single theorem.

The quadratic wall is not just a theory puzzle — it shapes every system that compares sequences:

• Spell-checking and autocorrect: your phone's keyboard computes edit distance to the closest dictionary word. When dictionaries scale to millions of entries, the quadratic cost per query becomes a bottleneck.
• DNA and protein alignment: tools like diff (in Unix), BLAST approximations, and Smith–Waterman alignment are all edit-distance relatives. Genome-scale data makes sub-quadratic methods a holy grail; the SETH result explains why exact algorithms seem stuck.
• Plagiarism detection: document comparison reduces to longest-common-subsequence, which is equally SETH-hard, meaning large-scale exact comparison is provably expensive.
• Version control (git diff): git diff uses edit distance on lines to produce patches. The quadratic cost is why modern VCS tools use heuristics rather than exact edit distance on very large files.
• Natural language processing: fuzzy string matching, typo-tolerant search, and de-duplication all pay the quadratic price. Understanding the lower bound shapes which approximations are worth pursuing.

The SETH lower bound also sparked the broader field of fine-grained complexity, giving conditional lower bounds for dozens of other problems that were previously just "hard in practice." See also P vs NP for the coarser NP-hardness picture.

For sixty years, every string comparison tool ran in quadratic time. Researchers proposed dozens of optimizations — banded DP, bit-parallelism, Four-Russians — yet none broke the $O(n^{2})$ barrier in the worst case.

Backurs and Indyk (2015) finally answered why: edit distance is SETH-hard. A truly sub-quadratic algorithm would collapse SETH, one of the strongest and most widely believed conjectures in all of complexity theory. The quadratic cost is not a gap in our cleverness; it is a fundamental property of the problem, conditional on SETH.

Fine-grained complexity, the field this result helped launch, now provides tight lower bounds for sequence alignment, longest common subsequence, graph diameter, and many other problems. Each result says: "this algorithm is not just the best we found — it is likely the best there is."

The next time autocorrect pauses for a beat, you know why — and why that pause may never fully go away.