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

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.