3 ms·
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
by praptak 13y ago
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.
- anonymoushn 13y agoThe 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.
- deleted 13y ago[deleted]
- baddox 13y agoIsn'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.
- lvh 13y agoPerhaps 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.