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