News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by j2kun on Monday December 30, 2013 @05:37PM (#6987538)
The OP's update is still incorrect. A problem in NP is a set of strings which a deciding Turing machine must accept (and it must reject all other strings). You cannot define a problem in NP by what the machine outputs, because for a decision problem you can only output a single bit.

What the OP meant to say is that you can define TSP as a decision problem as follows:

TSP = {<G, T> : G is a weighted graph, and T is a tour of minimal total weight}

Then this achieves what we want: that deciding whether a given tour has minimal weight is NP-hard but not known to be in NP. You can also formulate the TSP problem as a decision problem this way:

TSP = {<G, v>: G is a weighted graph with a tour of weight at most v}.

This formulation is essentially equivalent to the first problem.

There are no comments on this comment yet.