[commandlinefan]

The linked article had an interesting way to phrase the traveling salesman problem. I've always heard it formulated as "given a set of cities and their distances, what is the shortest path that takes the salesman through each city", which wouldn't be NP by the definition given: if you were given the answer, you couldn't check it in polynomial time (unless you could solve the problem in polynomial time).

[dorgo]

I had a problem with this too. But actually the problem can be stated as an NP problem: Compute a round-trip shorter than k. If you have an algorithm to solve the NP version then you can use it to find the shortest round-trip by repeadly applying it to different k-parameters.