News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.