Well... The traveling salesman decision problem, not the general case.
The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum.
What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum.
What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.