5 ms·
The title of the Boston Globe article and of the HN submission is misleading. The article does not prove that subquadratic edit distance algorithms do not exis
by a3_nm 11y ago
The title of the Boston Globe article and of the HN submission is misleading.
The article does not prove that subquadratic edit distance algorithms do not exist. It only proves it conditional to another unproven complexity hypothesis (SETH). In other words, it shows that if such algorithms exist, then faster algorithms exist for another problem (SAT for CNF formulae with certain size bounds), where we haven't been able to find them yet. See the original article http://arxiv.org/abs/1412.0348 http://arxiv.org/abs/1412.0348 whose title is more accurate.
This is important work, of course, and provides more evidence that faster edit distance computation is not possible, but it is not proven yet.
- logicallee 11y agoI don't get it - how does the author of the piece not know this? He seems to reflect an excellent understanding, and it's bizarre that he would would miss this.
- mckoss 11y agoOften times authors of articles are not the same people who write their titles ... it may even be changed without their knowledge (until the paper is actually printed).
- dsfsdfd 11y agobeat me to it
- brudgers 11y agoThere are really two notions of proof here [and hence truths and facts]. The article uses proof in a scientific sense, where P!=NP is accepted as empirical fact by the community of computer scientists in the same manner that biologists take natural selection as empirical fact. To put it another way, representing the world as if P!=NP is no less reasonable than representing the world as if Newtonian physics are applicable.
- a3_nm 11y agoTheoretical CS is usually not thought of as an experimental or empirical field. When a paper in that field claims "X does not exist", this has to mean that the inexistence of X was proven, not that a body of empirical knowledge against the existence of X has been collected. By contrast, such things are called "plausibility arguments", "heuristics", etc. There is such a thing as experimental truth, but it applies to experimental fields, and theoretical CS is usually not thought as one of them. I still think it is misleading to claim that the inexistence of something has been proven if it is conditional to another hypothesis.
- brudgers 11y agoComputer scientists behave as if P!=NP, and Donald Knuth will send a check to anyone who comes up with a polynomial time general solution to 3-sat. Or to put it another way, P!=NP is a de facto if not de jure axiom of theoretical computer science. And the burden of justification is on anyone whose conclusions are not premised on P!=NP just as it is a biologist who takes issue with evolution by saying "it's only a theory."
- ChrisLomont 11y ago>The article uses proof in a scientific sense Science does not deal in proofs, for example, the wiki page on scientific method does not use the word except in the mathematical sense [0]. Science deals in hypotheses, evidence, and models. [0] https://en.wikipedia.org/wiki/Scientific_method https://en.wikipedia.org/wiki/Scientific_method
- brudgers 11y agoOne common form of scientific proof is that upon which your comment rests: pointing to something and proving that x obtains, e.g. showing me a unicorn would demonstrate that unicorns exist. G. E. Moore (the less famous of Wittgenstein's doctoral advisors) pointed out this out in Proof of an External World [1]. It's more popular form is Popper's falsifiability [2] which is the more commonly accepted formulation of scientific formalism. [1]: http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Moore%20Proof%20External.pdf http://www.thatmarcusfamily.org/philosophy/Course_Websites/R... [2]: https://en.wikipedia.org/wiki/Falsifiability https://en.wikipedia.org/wiki/Falsifiability
- tomerv 11y agoThe wording in the article also makes it sound like the existence of a faster algorithm for edit distance would imply P=NP ("Most if not nearly all computer scientists believe the P equal to NP problem is false", although later a variant of the problem is mentioned), but that's not the conclusion of the theorem. A more accurate wording would be that the existence of a fast algorithm for edit distance implies that P is "close" to NP, because there would exist a sub-exponential algorithm for SAT (but not necessarily a polynomial algorithm).
- joe_the_user 11y agoThe title isn't misleading. The title is a reasonable summary of what the article aims to say, in actuality. What article is attempting to say may be wrong but that's a different issue.