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