News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by slacka on Monday December 30, 2013 @12:40PM (#6985680)
I'm a little confused by this issue. According to Proof Wiki: "Because the Traveling Salesman problem is both NP and NP-hard the Traveling Salesman Problem is NP-complete."

http://www.proofwiki.org/wiki/Traveling_Salesman_Problem_is_...

Here's another site claiming it's not even in NP: http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...

I'd love a clear explanation.

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.

Re:The TSP Isn't NP Complete by ColinWright on Monday December 30, 2013 @12:54PM (#6985780)
There is a chance someone will correct me here, as I'm not an expert. Take this with a grain of salt. Or a handful.

The second claim, that it's not in NP, is what this article is talking about. The optimization problem, as usually given, is not in NP because optimization problems are, by definition, not in NP. NP is for decision problems.

That's why this is regarded by some as simply a technical nit-pick, but continues to be a major source of confusion for those unwilling or unable to reason in nit-picking detail.

Certainly the decision problem "Is there a path of cost less than K?" is in NP, is NP-hard, and is therefore NP complete.

This can then be leveraged up into a solution of the optimization problem. Use a lower bound of 0, an upper bound of #(E) * max{ e in E: cost(e) }, and do a binary search for the optimal cost.

Does that help? With that information, you now need to re-read other sources.