Source-linked AI summary
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs, Piotr Indyk
TL;DR
Exact edit distance has long been known through algorithms running in nearly quadratic time, leaving open whether substantially faster exact computation is possible. This paper reduces Orthogonal Vectors to edit distance using carefully designed gadgets, showing that an O(n^(2−δ)) edit-distance algorithm would yield a faster CNF-SAT algorithm and violate SETH. The result provides evidence that near-quadratic exact edit-distance bounds are tight.
Problem
Exact edit-distance computation has a quadratic dynamic-programming algorithm and a fastest known exact running time of O(n^2/log^2 n), motivating the question of whether strongly subquadratic computation is possible.
Method
The paper reduces Orthogonal Vectors to edit distance using concatenated vector gadgets whose alignment costs distinguish orthogonal from non-orthogonal pairs.
Results
If edit distance is computable in O(n^(2−δ)) time, CNF satisfiability with N variables and M clauses is solvable in M^O(1)2^((1−ε)N) time, violating SETH.
Takeaways & Limitations
The paper identifies edit distance as a new important member of the class of conditionally SETH-hard problems, supporting the tightness of near-quadratic exact bounds.
Takeaways & Limitations
The hardness argument does not extend to approximate edit-distance computation, unlike the cited Frechet-distance argument.
Abstract
from arXiv · showhide
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(n^{2-δ})$ for some constant $δ>0$, then the satisfiability of conjunctive normal form formulas with $N$ variables and $M$ clauses can be solved in time $M^{O(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.
1 Introduction
The paper argues that exact edit distance likely requires near-quadratic time by reducing Orthogonal Vectors to edit distance and relating any strongly subquadratic algorithm to a SETH violation. Its construction uses gadget sequences whose alignment costs distinguish orthogonal from non-orthogonal vector pairs.
- 1 Introduction: The fastest known exact edit-distance algorithm runs in O(n^2/log^2 n), which remains nearly quadratic for length-n sequences.The classical dynamic-programming algorithm runs in quadratic time, while faster exact methods have not achieved strongly subquadratic time.
- 1 Introduction: If edit distance were computable in O(n^(2−δ)) time, CNF satisfiability with N variables and M clauses would run in M^O(1)2^((1−ε)N), contradicting SETH.The paper presents this conditional implication as evidence that near-quadratic bounds may be tight.
- 1 Introduction: The edit-distance hardness result joins several important computational problems established as conditionally SETH-hard.The introduction situates the result alongside conditional lower bounds for problems including k-Dominating Set, graph diameter, local alignment, dynamic connectivity, and Frechet distance.
- 1 Introduction: The reduction starts from Orthogonal Vectors and concatenates vector-specific gadget sequences into two input sequences.Each vector receives a gadget; all gadgets from each set are concatenated to form one sequence.
- 1 Introduction: An orthogonal vector pair permits a traversal aligning its gadgets with small induced distance, whereas the absence of such a pair forces every traversal to have large distance.This small-versus-large distinction is the correctness condition connecting the vector instance to edit distance.
- 1 Introduction: Gadgets offer substitution-based costs linear in overlapping 1s and a fixed fallback cost, making orthogonal pairs cost C0 and other pairs cost C1 > C0.Taking the minimum of the two alignment options removes dependence on the number of overlapping 1s when vectors are not orthogonal.
- 1 Introduction: The hardness argument does not extend to approximate edit-distance computation, unlike the cited Frechet-distance argument.This is an explicit scope limitation of the paper’s hardness result.
2 Preliminaries
The preliminaries define edit distance through transformations or a common intermediate sequence and introduce Orthogonal Vectors as the source problem for the reduction. They also state the conjectured difficulty of solving Orthogonal Vectors in strongly subquadratic time.
- 2 Preliminaries: EDIT(x, y) is the minimum number of insertions, deletions, and substitutions needed to transform sequence x into sequence y.The function is a metric, so it is symmetric and satisfies the triangle inequality.
- 2 Preliminaries: Equivalently, EDIT(x, y) is the minimum deletions and substitutions needed to transform x and y into a common sequence z.Insertions can be replaced by deleting the corresponding aligned symbol from the other sequence.
- 2 Preliminaries: The Orthogonal Vectors Problem asks whether two sets of N Boolean d-dimensional vectors contain x and y with dot product x·y = 0.It can also be phrased as asking whether a set from one collection does not intersect a set from the other.
- 2 Preliminaries: Orthogonal Vectors has an O(N^2d)-time solution, while the Orthogonal Vector Conjecture rules out strongly subquadratic algorithms.Strongly subquadratic means d^O(1)·N^(2−δ) time for some constant δ > 0.
- 2 Preliminaries: The reduction assumes every vector b in B has first coordinate 1, which is achieved without loss of generality by adding coordinates.A 1 is added to each b and a 0 to each a.
3 Reductions
The reduction constructs vector gadgets whose edit distance encodes the minimum of two dot products, then uses the resulting gap to reduce Orthogonal Vectors to PATTERN and edit distance.
- 3 Reductions: The construction uses coordinate and vector gadgets over the alphabet Σ = {0, 1, 2, 3, 4}, with lengths determined by the vector dimension d.The parameters include l0 = 1000 · d, l1 = (1000 · d)^2, and l = d(4 + 2l0).
- 3 Reductions: Coordinate gadgets distinguish orthogonal coordinate pairs by edit costs 1 when x1 · x2 = 0 and 3 when x1 · x2 = 1.
- 3 Reductions: The vector gadgets provide two low-cost alignment options, producing costs linear in a · b or a′ · b; minimizing over alignments yields EDIT(VG1(a, a′), VG2(b)) = C + 2 · min(a · b, a′ · b).The two options are realized by different deletion, substitution, and coordinate-gadget transformations.
- 3 Reductions: The reduction fixes a′ · b = 1, making the gadget distance C0 for orthogonal vectors and C1 > C0 otherwise.This gap allows sums of gadget distances to test whether at least one orthogonal vector pair exists.
- 3 Reductions: For vectors b with b1 = 1, the gadget costs are Es = 2l1 + l + d when a · b = 0 and Eu = 2l1 + l + d + 2 when a · b ≥ 1.
- 3 Reductions: The PATTERN reduction sets X := |A| · Eu and separates the cases: an orthogonal pair gives PATTERN(P1, P2) ≤ X − (Eu − Es), whereas no orthogonal pair gives X.
- 3 Reductions: If edit distance on length-n sequences over an alphabet of size 7 ran in O(n^{2−δ}) time, Orthogonal Vectors would be solvable in d^{O(1)} · N^{2−δ} time.