3 ms·
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 cou
by jerf 11y ago
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.
- dietrichepp 11y agoRather 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".
- amelius 11y agoStill incorrect. 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.
- jerf 11y agoLimiting 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.
- im3w1l 11y agoHis 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.