Hacker News Reader

Comment by a3_nm | Hacker News Reader

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 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.

View on HN

The 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).

I 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.

Often 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).

The 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.

There 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.

Theoretical 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.

Computer 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."

>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

One 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/R...

[2]: https://en.wikipedia.org/wiki/Falsifiability

Showing me a unicorn example is not proof that unicorns exist. It is evidence towards a hypothesis that they exist. After you present your unicorn, I may discover it is a modified horse.

Science can never prove truth or falsity of anything - it only provides evidence for or against hypotheses, but every single thing can be changed subject to future evidence. As such, there is no true/false in science, only degrees of evidence.

This article, which you claim uses proof "in the scientific sense," does not prove a hypothesis is false, only that is gets less and less likely and competing ones get more and more likely, which is what your examples are getting at. The article proves (in the mathematical sense) the non-existence of an item, only if a certain conjecture is true.

As pointed out above, this is math, not empirical.

The thing is the article implies the paper proves a link to p!=NP but the actual paper only claims "evidence" that there is a link, so there are multiple stages where the link is sketchy.

beat me to it

Reply on news.ycombinator.com