3 ms·
>He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a poly
by SilasX 11y ago
>He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest.
It's kind of imprecise, but the understanding in these situations is that you're talking about some bounded version of the problem. In TSP, it's common to mean the problem of "is there a solution of length less than N", and you're only verifying that the length is less than N, not that it's optimal.