Jean Francois Puget writes a controversial post No, The TSP Isn't NP Complete which I discovered during a lengthy twitter discussion with Puget and Peter Cacioppi.
There is a well-known technicality for the Euclidean Traveling Salesman problem but let's focus instead where we are given a complete graph weighted with positive integers. One version of TSP is truly NP-complete
TSP Decision: Given an integer B, is there a cycle through all the vertices such that the total weight of the edges used is at most B?TSP Decision is in NP by guessing the cycle and hardness by a simple reduction from Hamiltonian Cycle.
Puget's makes the point that we normally think of the TSP problem as an optimization question
TSP Minimization: Find the cycle through all the vertices that minimizes the total weight used.TSP Minimization is not even a decision problem. In the 80's, Mark Krentel created a complexity class OptP to capture optimization problems and showed that TSP Minimization is Opt-P-complete.
One can use TSP Decision to solve TSP minimization by doing binary search, so they have effectively have the same complexity.
Puget points out that even if we are given a tour, checking that it is the shortest tour is not believed to be in NP. That problem is in co-NP and I'm guessing co-NP-complete. [Update 3/20: I was right]
Puget doesn't like when people claim TSP is NP-complete when they are talking about the optimization problem. For example from my P v NP survey
The NP-complete traveling salesperson problem asks for the smallest distance tour through a set of specified cities.I'm far less bothered than Puget. Those who understand the technicalities of NP-completeness know that one has to convert the optimization problem to an appropriate decision problem to formally get an NP-complete set. Others aren't led too far astray, for we do have an equivalence that P = NP if and only if there is an efficient (polynomial-time) algorithm for TSP Minimization.