News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by praptak on Monday December 30, 2013 @12:52PM (#6985764)
NP is a class of decision problems - the solution has to be "yes" or "no". NP-complete problems are a subset of NP, so only decision problems can be NP-complete.

TSP, the optimization version (what's the shortest path?) is an optimization problem therefore it is NP-hard, not NP-complete. TSP, the decision version (is there a path shorter than K?) is NP-complete.

There are no comments on this comment yet.