52 ms·

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 N

by slacka 13y ago

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_NP-complete#The_Traveling_Salesman_Problem_is_NP 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-salesman-the-most-misunderstood-problem/ http://www.nomachetejuggling.com/2012/09/14/traveling-salesm... I'd love a clear explanation.

praptak 13y ago
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.
ColinWright 13y ago
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.

by slacka 13y ago

praptak 13y ago

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.

ColinWright 13y ago

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.