The TSP optimization problem is polynomial time reducible to the TSP decision problem by binary search.<p>Suppose we have an algorithm D(TSP,C) which returns 1 if the TSP has a path of cost <= C.<p>Then the basic idea for an algorithm for the optimization version is :<p><pre><code> C = sum( costs of all paths in graph )
while D(TSP,C) == 1:
C = C / 2
</code></pre>
Probably the greatest thing about having a polynomial time algorithm for an NP complete problem would be that it would allow finding the global optimum for any finite optimization problem in polynomial time.
This is a major point of confusion for people who are new to the concepts, and I'm glad someone has taken the time to explain it in depth. And it's not just TSP that it happens with. Almost every popular example of an NP-complete problem I've seen is actually an NP-hard optimization problem corresponding to an NP-complete decision problem.<p>The bad part is that if you don't know better, you'll think "Wait, how the hell would you verify a correct answer to this without searching for an even shorter path?" And you'll be right, but you'll feel like you're missing something. Giving examples of CS that make people feel like they fundamentally don't understand CS is probably a Bad Thing.
I think the author actually adds to the confusion about TSP by being unnecessarily vague.<p>Both P and NP are classes of decision problems. That means they only contain problems that ask for a yes/no answer. So because TSP asks for a route, it is not just a decision problem, and can't be in NP. However, as the author mentions, NP does in fact contain the TSP-DECIDE problem in the way he defines it.<p>Moreover, the problem TSP of finding a lowest cost route can be solved by a polynomial time Turing Machine that can use a TSP-DECIDE oracle (i.e. call a constant time function that solves TSP-DECIDE). It is in fact complete for that class FP^NP ("= function problems solvable in polynomial time with an oracle for NP problems"), which means it is one of the hardest problems there. The class FP^NP contains all of FNP (NP for functional problems) and is believed to contain more problems -- so there is a good chance that TSP is not in FNP.
Perhaps I simply know different people but I'm accustomed to Travelling Salesman, without explaining which version is intended, being given as the canonical NP-Hard (implicitly the optimal solution problem).<p>I normally see SAT given as the NP-complete example.
Well, this is true, but it's also hyperbole. It's not really everybody misunderstanding the problem so much as simply not caring. People are sloppy with the terms "NP-hard" and "NP-complete" and use them interchangeably because it's usually not important. Usually they mean "NP-hard", and that is the significant thing.<p>Yes, it's wrong to use "NP-complete", but plenty of people who thoroughly understand the problem do so. Welcome to Computer Science, sloppy is par for the course.
Ironically enough, I think this guy misunderstands TSP. I wrote this comment on his blog:<p>Let's define a new problem, TSP-cost-optimize, which returns the cost of the best Hamiltonian. It's NP-Complete, because it reduces to TSP-decide: Just do a binary search on the space of possible scores; even if that space is exponential, we're fine, since binary search runs in the log of the size of the space.<p>TSP-cost-optimize's certificate can be the steps of the binary search; that will be polynomial in size, since it's a polynomial number of TSP-decide certificates, and you can verify it in polynomial time.<p>Given TSP-cost-optimize, I can in fact provide a polynomial-time-verifiable certificate for the result of TSP-optimize: The result of TSP-cost-optimize on the same graph! So under your definition of NP, TSP-optimize is in fact in NP. (This also makes sense if you use the non-deterministic Turing machine definition of NP.)<p>What's not clear to me is whether given the result of TSP-cost-optimize, you can actually find a shortest path in polynomial time. But I expect you probably can.
Just a small quibble:<p>If you're going to provide a TL;DR: it's probably better to stick it up top. Otherwise, the people who DR because it's TL will likely never find it.
Since optimization and decision problems are equivalent, what someone means by saying that an optimization problem is in np-complete is that its equivalent decision problem is in np-complete.
TL;DR: For now TSP-OPTIMIZE is in NP-Hard but not (necessarily) in NP, so its not in NP-Complete. TSP-DECIDE is both in NP-Hard as well as NP, and is therefore NP-Complete.
I'm so thankful. After 4.5 years of CS, the only class that taught me anything was my advanced algorithm class and I <i>learned</i> enough to retain an immense amount of the information a year later. This is fun stuff and I hated it two years ago.