7 ms·
Computer scientists prove that a 40-year-old algorithm is optimal
- mabbo 11y agoShort 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.
- rbanffy 11y agoWell... I guess now it's up to the hardware engineers to make it faster... ;-)
- sanxiyn 11y agoThe 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.
- paulfr 11y agoWhat the article doesn't state clearly is that this assumes the strong exponential time hypothesis: it assumes that SAT cannot be solved in time 1.9999^n -- in other words that it's impossible to do better than the brute-force algorithm, which has complexity 2^n (up to polynomial factors). That's a very strong assumption.
- dietrichepp 11y ago> But it also means that computer scientists can stop agonizing about whether they can do better. This is incorrect... because a "better" algorithm might have 99.9% accuracy but be millions of times faster.
- CHY872 11y agoThat's pedantic and also incorrect. The problem of whether an exact solution can be found efficiently can be put to rest. You might not choose to use this algorithm, but that's not really the point of algorithms research. You've just picked a strawman to criticise the wording on.
- cafebeen 11y agoThere is plenty of work being done on approximation algorithms, for good reason. If you're dealing with scientific data that's subject to measurement noise, it's valuable to research whether that 0.1% difference actually matters or not. That said, this is great work, it's just not a closed case.
- CHY872 11y agoYes, of course - and there are some really cool proofs (easy to understand also). A personal favourite is the Run of Christofides. BUT that's not relevant here.
- cafebeen 11y agoIt seems relevant to start talking about approximation algorithms as the next step after proving a "1000 year" runtime for exactly comparing genomes. My understanding is that comp bio folks typically use heuristics anyway.
- mcherm 11y agoI don't think so. I think he is pointing out a really, really important thing that many overlook because of the way we have come to teach computer science. When evaluating different algorithms, there are lots of criteria we could use. How often is it correct? How long does it take to run? How difficult is it for people to read? How often does it use the letter "r" which happens to be broken on my keyboard? Computer science made ENORMOUS strides by picking out a specific criterion (running time on the computers of the time) and finding a way to make it mathematically rigorous (asymptotic performance analysis, Big-O notation, and all of the related mechanisms that we learn in computer science classes). This was TREMENDOUSLY valuable, and by turning the whole power of mathematical analysis loose on the problem it formed the modern field of algorithm analysis and completely transformed how we build computers. But we need to remember that this is base on one particular simplification of how computers work. It assumes a Von-neuman architecture where execution steps are the key criterion. We have extended this framework to consider things like parallel execution... that was fruitful also. More recently, we've been noticing that our actual machines are no longer dominated by the "steps" in the algorithm, but most often are dominated by memory usage, so we have turned the same formalism onto the use of memory -- but still (in my opinion) lack a rigorous approach for analyzing the combination of steps taken and memory usage. Even more significant is the fact that there are OTHER things we could trade off. One of those is accuracy. Look at some of the research on probabilistic algorithms: you will find that there are some incredible gains to be made with losses in accuracy that are well within the bounds of what are acceptable for most uses. Yet this isn't covered in an introductory computer science course, so many programmers are not even aware of the option. With so much of traditional algorithm analysis already mapped out by the past several decades of researchers, much of the fertile ground in the near future will, I believe, lie in investigating these other sorts of tradeoffs.
- davmre 11y agoDick Lipton (GATech) has a blog post discussing this paper: https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/ https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/.
- dfan 11y agoHere's the paper: http://arxiv.org/abs/1412.0348 http://arxiv.org/abs/1412.0348
- necessity 11y agoThe 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.
- throwaway12357 11y ago> that’s disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. I did a quick googling [1] and > Our algorithm divides the problem into independent `quadrants' ... > Our results show that our GPU implementation is up to 8x faster when operating on a large number of sequences. It's still soul crushing. Why did our genome have to be that long :( BTW, do you have numbers for setups with hundreds of GPUs? I'm also left wondering about results using stochastic solutions. On how accuracy and problem size relate. [1] http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6339593 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=tru...
- daveloyall 11y agoI'm confused by this. 1,000 years seems a bit steep to me. Suppose you have two files, `bob.genome` and `mary.genome`. Let's say they are 1gb each [1]. I think I can diff two 1gb files in less than 1,000 years. diff(1) shows "deletions, insertions, and substitutions". Therefor, I don't believe it. Yet. What did I miss? 1. http://stackoverflow.com/questions/8954571/how-much-memory-would-be-required-to-store-human-dna http://stackoverflow.com/questions/8954571/how-much-memory-w... (Rounded up because Fermi estimation [2].) 2. https://what-if.xkcd.com/84/ https://what-if.xkcd.com/84/
- mmarx 11y ago> diff(1) shows "deletions, insertions, and substitutions". diff(1) doesn't give you a _minimal_ set of edits to apply to go from one file to the other, just _a_ set of edits.
- zerokk 11y agoThis 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.
- epistasis 11y agoHeuristic algorithms can never be "optimal". The article is precise and correct. I use heuristic algorithms for all my DNA alignment, and for all my probabilistic modeling, but I do that with the knowledge that I'm not necessarily finding an optimal solution, I'm only find a "pretty good" solution like the SAT solvers do.
- mafribe 11y agoIt's questionable whether SAT solvers really work well for "the vast majority of the cases". They work very well for the problems they are tasked with. DPLL-based SAT solvers don't work well with randomly generated SAT instances which survey-propagation-based solvers excel on. On SAT-instances that arise in the verification of CPUs the opposite is true. Both approaches break down where SAT instances have more than 10^7 variables, and that's almost all cases. ;) Still, it never ceases to amaze me just how well DPLL-based solvers work on the instances that I feed them, and that despite all the theoretical limitations that we know they have.
- lorenzhs 11y agoIt's θ(n²) time with Needleman-Wunsch / Wagner-Fischer. The paper now says that the problem requires Ω(n²) time as long as P ≠ NP. Nothing NP-hard about sequence alignment, and it also isn't an optimization problem. You are also mixing up two kinds of heuristics. SAT solvers use heuristics to guide the search, making it faster in the expected case (but possibly also slower), but they do not sacrifice correctness. Sequence alignment heuristics sacrifice correctness for speedups. Those are two very different concepts.
- jbapple 11y agoThe 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". 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. It's also interesting reading; just Google for "edit distance" and "Four Russians" and you'll find many summaries.
- ruggeri 11y agoAm I reading this wrong? The title is wrong, right? 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. That's very interesting, but it's not a proof that no strongly sub-quadratic solution exists for SED. Note that exponential time hypothesis is strictly stronger than 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... Of course, the paper was careful to explain it, but the media summary... Edit: I was interested to learn about the notion of strongly quadratic; 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.
- ianamartin 11y ago"Prove" is an incredibly strong word. Too strong for this case.
- anonetal 11y agoI haven't seen too many results that rely on SETH, so just did a bit of research. Ryan Williams (from Stanford) at least doesn't believe SETH is true -- here is a nice talk by him on SETH: http://www.imsc.res.in/~vraman/exact/ryan.pdf http://www.imsc.res.in/~vraman/exact/ryan.pdf
- Sniffnoy 11y agoInteresting to note there slide 5 -- "For many polynomial time problems, improving the best known algorithms, even slightly, implies ¬SETH or ¬ETH." So apparently the edit-distance result discussed here is part of a history of similar results. Edit: More detail on this in slides 11 and forward.
- j2kun 11y agoIf you're going to be so specific you should also note that ETH and P != NP could be equivalent. So "strictly stronger" is also a hypothesis.
- 11y ago
- judemelancon 11y agoThe 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.
- Retric 11y agoO( (n/log(n))^2 ) > 0(n^1.99999999999999) for sufficently large N
- judemelancon 11y agoYes, the fact it's >O(n^k) for all k in [1,2) is why it's not strongly. It's still less than O(n^2).
- anacleto 11y agoI love 'proofs' which rely on an unproven component.
- beefman 11y agoThe 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] 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). [1] see page 63 of https://scholar.google.com/scholar?cluster=9946036749686151606 https://scholar.google.com/scholar?cluster=99460367496861516...