Computer scientists prove that a 40-year-old algorithm is optimal
newsoffice.mit.edu
newsoffice.mit.edu
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.
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.
Edit: Apparently n here refers to just the number of variables rather than the overall size of the problem instance. But that makes sense, because that's where the exponential dependence of the naïve algorithm is in the first place; adding more clauses just makes checking each possibility take slightly longer.
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=tru...
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-w... (Rounded up because Fermi estimation [2].)
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.
Isn't it more likely that somebody misquoted "slow, like a half an hour" as "slow, like a THOUSAND YEARS"?
>>> 1000 / ((1024. ** 6) / 3e9 / 86400 / 365)
82.0593593076069
If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 elements, an exponential-time algorithm would take about 100 quintillion years.
Yes, indeed! What you're thinking of is "output-sensitive" algorithms. There are some output-sensitive algorithms for edit distance. The fastest one I found is in "Improved Algorithms for Approximate String Matching" by Dimitris and Georgios Papamichail. They note:
"We designed an output sensitive algorithm solving the edit distance problem between two strings of lengths n and m respectively in time O((s-|n-m|)min(m,n,s)+m+n) and linear space, where s is the edit distance between the two strings."
for i := 1..bob'length loop
for j := i..mary'length loop
editdistance(substring(bob,1,i), substring(mary,i,j));
end loop
end loopI saw a talk on it a while ago, I can only remember they were using CUDAlign and Smith-Waterman (the basic idea is the same). Doing some googling too this seems to be a reasonably recent work with GPUs and CUDAlign (DOI 10.1109/CCGrid.2014.18).
>I'm also left wondering about results using stochastic solutions.
Another talk, I think they were running Smith-Waterman too. The speculative part was during the traversal of the matrix to get the edit distance. It's not the most time consuming part of the algorithm. I got in late for the talk and I didn't get to hear what they did about filling the matrix in the first place, but I imagine they might have done something similar. I'm not very familiar with Smith-Waterman so I can't go into details.
This is a result about the worst case expected time for an abstract algorithm for finding the edit distance between any two sequences of less than a given length.
It's possible an algorithm which usually takes much less time exists. And more to the point, an algorithm knowing something about the structure of genomes might wind-up with even less time. Matching broad areas of different genomes together first seems like an obvious speed-up in this case and I'm sure there are a number of others.
This sort of thing is exactly what I love about Computer Science.
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.
This is incorrect... because a "better" algorithm might have 99.9% accuracy but be millions of times faster.
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.
This sort of work is not reliant on von-Neumann - it quantifies the amount of work you need to do. Coincidentally, the algorithm listed parallelises very well; it has a good span.
Of course it is useful to avoid galactic algorithms, but the article is totally correct. It would be incorrect to read its conclusion as anything but what it actually says. As a general principle, sure, but it shouldn't be a criticism of this article.
1. The proof is conditional on the unproven hypothesis that 3-SAT requires 2^n time.
2. There could be an exact algorithm which uses randomness and has less than n^2 expected runtime. After all, it's still unknown whether ZPP=EXP afaik (although it almost certainly does not).
You may have a million-times faster solution that's approximate and that may be just fine. It's not, however, a solution that always produces the correct answer. There is a difference between good enough and perfect.
Maybe 99.9% accurate isn't good enough, but there is always a level of inaccuracy from the algorithm where your random silent computer hardware errors dominate. And that may be still faster than the exact algorithm.
But that would indeed be a different problem. This problem, the precise edit distance problem, has been proved to be optimally-bounded by the existing solution, and yes, computer scientists can stop agonizing about this problem.
It is not advantageous to anybody to try to blur the distinctions, nor is it any sort of "gotcha!" or win to do so... it is only a loss of clarity.
It might be possible to solve the precise edit distance problem exactly, and much faster using a different technique, but only for specific instances of the problem.
The problem is what it is. You don't get to change its domain or its range or the statistical distribution of its instances or the nature of its solution (probabalistic, etc.) or anything else, or you've defined a new problem. There's nothing wrong with creating new problems, but you have changed nothing about the original... problems are immutable.
>In a sense, that’s disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. But it also means that computer scientists can stop agonizing about whether they can do better.
People are using the result to draw conclusions about real world problems that may well be easier than general case.
> If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.
Complexity theorists have also found more formal reasons why it it would be hard to prove P ≠ NP. For example, you can't use "natural" proofs, "relativizing" proofs, or "algebrizing" proofs [2]. (Conversely, in a P=NP world you'd expect it to be easy to prove P=NP.)
1: http://www.scottaaronson.com/blog/?p=122
2: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SCOTT/alg...
I don't really buy into most of the examples of the quote. For example it is already a complex problem to quantify what makes a symphony a great symphony, once you solved this it of course becomes easy to recognize great symphonies. To write a great symphony you could then just exhaustively search the space of symphonies and rate them until you find a great one.
But does it really sound highly implausible to you that once you figured out what makes a symphony a great symphony you could use that knowledge to prune the search space and discover great symphonies much faster that using exhaustive search?
And the fact that known techniques are not good enough to settle the question doesn't sound like a surprise to me either. The very fact that the problem is not yet settled means that the usual approaches don't work and we have to use known things in an innovative way or come up with something entirely new.
So that some things don't work hardly comes as a surprise but not even this implies that P == NP is more likely right or more likely wrong, it just says that figuring it out is hard. You could maybe argue that it is evidence for the problem being independent from ZFC or whatnot if we and our tools constantly fail to settle the problem one way or the other.
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=99460367496861516...
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.
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.