Am I reading this wrong? The title is wrong, right?<p>The paper says that if a strongly sub-quadratic solution exists than the exponential time hypothesis (that SAT cannot be solved in subexponential time) is invalidated.<p>That's very interesting, but <i>it's not a proof</i> that no strongly sub-quadratic solution exists for SED.<p>Note that exponential time hypothesis <i>is strictly stronger than</i> P!=NP. Even if SAT can't be solved in poly time, that doesn't mean it can't be solved in subexponential time. There are functions that lie between polynomial and exponential...<p>Of course, the paper was careful to explain it, but the media summary...<p>Edit: I was interested to learn about the notion of <i>strongly quadratic</i>; there are O(n^2/log n) solutions to SED, but this paper is casting doubt on solutions with time complexity O(n^(2-delta)) for any delta > 0. Another commenter mentioned a method to solve SED like this.
The Wagner-Fischer (1970) algorithm they mention (AKA Needleman-Wunsch,
Lowrance-Wagner, etc) is quadratic in time and space. It might never get any
better than that in time - an improved version with linear space complexity was
presented by Hirschberg in 75 - but that doesn't mean execution times can't be
improved. Today there are various variations of the same family of algorithms
with ever improving execution times. Some adapt the algorithm to massively
parallel setups with hundreds of GPUs, others use speculative execution, some
use approximations, and so forth.
Dick Lipton (GATech) has a blog post discussing this paper: <a href="https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/" rel="nofollow">https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/</a>.
Short version: computer scientists have shown that if the Edit Distance problem can be solved in sub-quadratic time, then SAT can be solved in sub-exponential time, and therefore P=NP.
The article clearly states this, but the title doesn't, so N.B.: the proof is conditional on exponential time hypothesis, that SAT requires exponential time. Of course we don't know whether it does.
The authors of the paper note (though this MIT News summary omits) that there is a well-known algorithm for edit distance that runs is subquadratic time. In fact, it runs in O(n^2/log^2 n) on a word RAM. It uses a method sometimes called "Four Russians" or "shaving a log".<p>Of course, this does not invalidate the results; I mention it only to dispel the notion that a reader may get from this MIT News summary that there is no subquadratic algorithm likely to be found.<p>It's also interesting reading; just Google for "edit distance" and "Four Russians" and you'll find many summaries.
> But it also means that computer scientists can stop agonizing about whether they can do better.<p>This is incorrect... because a "better" algorithm might have 99.9% accuracy but be millions of times faster.
The paper mentions an algorithm published in 1980 is O( (n/log(n))^2 ), which is better than the Wagner-Fischer algorithm mentioned in the article, even if it's not strongly subquadratic.
The edit distance between two strings L and S, where |L| >= |S|, is at most |L|. For any number n and string W, a DFA can be built which accepts an input IFF its edit distance to W is < n. Such a DFA can be built and run in O(|W|) time.[1]<p>What's the complexity of a 'binary search' for the edit distance between L and S using this method? The DFA construction complexity grows very fast with respect to n, but we only need log(|L|) DFAs. And the search cut points can be skewed to amortize the growth with respect to n (i.e. first n << |L|/2).<p>[1] see page 63 of <a href="https://scholar.google.com/scholar?cluster=9946036749686151606" rel="nofollow">https://scholar.google.com/scholar?cluster=99460367496861516...</a>
This is so wrong. Just because it's NP-hard (optimization problem, right?) it doesn't mean that there aren't very-very-very good heuristic algorithms that can make the search significantly faster than exponential in the vast majority of the cases. Take a look at SAT solvers and see how deep the rabbit hole really goes.