Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

By Arturs Backurs, Piotr Indyk. 2014

441 citations recorded by the source corpus.

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time. In this paper we provide evidence that the near-quadratic running time bounds known for the problem of computing edit distance might be {tight}. Specifically, we show that, if the edit distance can be computed in time O(n2-δ) for some constant δ>0, then the satisfiability of conjunctive normal form formulas with N variables and M clauses can be solved in time MO(1) 2(1-ε)N for a constant ε>0. The latter result would violate the Strong Exponential Time Hypothesis, which postulates that such algorithms do not exist.

Subfields: Artificial Intelligence, Hardware and Architecture, Molecular Biology, Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Molecular Biology

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, background): “The impossibility for sparse-attention follows from hardness results stemming from Orthogonal Vector Conjecture(OVC) [1, 2, 7, 97].”
Tight Hardness Results for LCS and Other Sequence Similarity Measures (2015, methodology): “Given a hard instance of Edit-Distance given by the reduction in [9], consisting of two sequences x and y, we show that there is a mapping for which EDIT(x, y) = DTWD(f(x), f(y)).”
On The Computational Complexity of Self-Attention (2022, methodology): “So instead, mirroring [15], we derive reductions from the Orthogonal Vectors Problem (OVP), which is known to require almost-quadratic time assuming SETH.”