News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by praptak on Monday December 30, 2013 @12:35PM (#6985640)
Only decision problems can be NP-complete, other problems can only be NP-hard. The article is a horribly long winded rant over this nitpick.

By the way, in the computational complexity community it is understood that if you say "TSP is NP Complete" you mean the decision version of the problem (is there a path shorter than K?) so nobody will bother to nitpick.

Re:The TSP Isn't NP Complete by anonymoushn on Monday December 30, 2013 @12:50PM (#6985754)
The great thing is that the author doesn't seem to understand the distinction. He states in his update that he has a decision problem of finding the tour of minimal distance.
Re:The TSP Isn't NP Complete by baddox on Tuesday December 31, 2013 @01:54AM (#6989443)
Isn't that decision problem also in NP? The traditional TSP decision problem is in NP, and it seems like you should be able to run that a polynomial number of times to solve his version.
Re:The TSP Isn't NP Complete by lvh on Tuesday December 31, 2013 @09:25AM (#6990544)
Perhaps the parent you're replying to means to say that the author doesn't appear to understand the distinction, because the wording being used doesn't make it a decision problem either. As long as we're nitpicking: decision problems have yes-or-no answers.