That'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.
I 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.
No - there are many fruitful formalisations of parallel programming (the CLRS chapter is pretty good) and indeed, of non-von Neumann architectures (check out balancing, comparison networks etc etc).
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.
There are 2 much better criticism they could have made:
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).
There 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.
Yes, 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.
It 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.
99.9% accurate is only better for some values of "better". An airplane routing system that ensures 99.9% of the planes will arrive at their destination and 0.1% will collide with terrain or other airplanes and ensure all passengers die screaming in horror is not what I would call a good airplane router.
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.
To be fair, the idea of correctness (in the optimization sense) is based on simplifying assumptions. For example, using the edit distance to compare genomes makes an assumption that insertions, deletions, and substitutions "cost" the same amount, but the reality is far more complicated due to the mechanics of how mutations actually happen. The edit distance is incredibly useful anyway, and a 99.9% answer is possibly just as useful
...Except, of course, that even the exact solution won't always produce the correct answer, due to the wonders of computers not being 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.
You need to be precise. It may be the case that you can solve a different problem, using probabilistic techniques, much more quickly. This happens often. It could be the case that genes have characteristics that make them amenable to such a specialized solution, since they aren't just random strings (introns notwithstanding).
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.
Rather my point was that it's easy to give up on a problem if you have a limited definition of what it means for a solution to be "better". Usually we even have to resort to satisficing for our definition of "better".
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.
Limiting the problem to specific instances is still a different problem. Otherwise, the problem is ill-defined and "certain instances" of all problems can be solved in O(1).
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.
His remark is important as a refutation to this sentence from the article
>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.
In my opinion it is incorrect for a much better reason - we don't know that P != NP. I am not aware of any arguments for P != NP that are much better than »We tried hard to find fast algorithms but failed.« or »Writing a great symphony is much harder than recognizing one.« and therefore I think the possibility that P == NP is often not considered as serious as it maybe should.
Have you looked for intuitive arguments about why P ≠ NP? Scott Aaronson's blog is a good place to find such things [1]:
> 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.)
When I mentioned writing a symphony I was essentially referring to your quote from Scott Aaronson and I am also aware that some known proofing methods have been shown not to be strong enough to settle the question.
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.
This is incorrect... because a "better" algorithm might have 99.9% accuracy but be millions of times faster.