I don't understand how verifying a TSP is any different to solving it - I.e. don't I have to do just as much work to verify that a particular solution is correct as if I was solving it from scratch? I.e. brute force?
There are a few ways to ask the TSP question. One question is "give me the shortest route geometry", this problem is NP-hard and can't be verified easily, this is what you're thinking of. However, the decision version of the problem is usually phrased "Is there a tour of less than length L", and this is NP-Complete - takes a while to find the tour, but it's trivial to check if it's less than length L.
That works for one way (where the tour exists), however, if the true answer to the particular decision problem is "no! it can't be done in L steps!" - then the only way to verify is to repeat the whole process, no?
Having an easily verifiable tour that does it in L+1 doesn't really help in verification that some other combination could or could not do it in L steps.
NP only requires that you can verify a positive answer in polynomial time. Problems with polynomial time proofs for negative answers form the class Co-NP.
Besides that, if you can solve the decision problem and the distances are well-behaved, for example integers, you can solve the other variants, you can perform a binary search for the minimal tour length and you can find the actual tour by probing all edges, i.e. removing one by one and checking whether that increases the minimal tour length.
You can just choose an arbitrary starting L, and if the answer is No, keep doubling your guess until the answer is Yes, then just binary search from there. Or if you want to start with the maximum possible L, just start with the sum of all the edge weights in the graph.
TSP is NP-hard -- we don't know if it's in NP (that is, we don't even know if there's a polynomial time algorithm to verify whether a proposed solution is optimal). The decision problem of TSP is NP-complete:
> The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.
( https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co... )
The author got this wrong in the article -- just because you can check that each house has been visited in polynomial time proves nothing.
(other people have answered you already, and their answers seem quite knowledgeable, but I sense their answers are actually off the point of your question, i.e. I think there is a better answer than you have been given. However, I learned this material long time ago and the precise answer is not fresh in my mind, so hopefully I can give you the gist, we'll see, but apologies in advance for all my hand waving)
it's like this: if I give you a large number and say "factor this", you will work hard figuring out the answer, but if I give you a set of factors and say multiply them together and see if they equal the big number, you can do that fairly quickly. i.e. you can check the answer a lot easier than you can find the answer.
An NP complete optimal routing problem is the same way, it's hard to find an answer, but if somebody gives you the optimal solution, it is easy to check that it is optimal by substituting segments from the solution set for segments that are not in the solution set, and trying to incrementally improve on it: if you have a solution, none of your substitutions will piece-wise be an improvement, furthermore, you can do it in an orderly way that "proves" your route is best precisely without duplicating all your work. This is the part I don't remember but it's something like "find the longest segment on your route, is there some shorter way to accomplish what that accomplishes? no there isn't. or look at the shortest segments, are they penny-wise but pound-foolish, no they aren't." i.e. the part I do remember is that it is polynomial time to confirm the answer, and it is not polynomial time to find the answer. This is what is in fact meant by "non-deterministic polynomial", it's polynomial only if you magically know the answer in a non-deterministic way. Polynomial to check, but in a deterministic way it is not polynomial to determine.
Again, sorry for all the handwaving, but I'm pretty certain that's right.
Oh, and while I'm here, what was the most irritating thing about this article is that P vs NP is not a huge "assumption". Call it a conjecture, call it a hypothesis, call it a problem to solve, but it's not an assumption, it's been tested long and hard by a lot of really smart people and it's the fringes of our knowledge. That's not what is typically meant by the word "assumption".
The actual decision problem statement for TSP is "Does there exist a tour of less than length L".
It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.
The Traveling Salesman Decision Problem, the one that's NP-complete and not just NP-hard, does not ask for the lowest cost route. It asks whether there is a route cheaper than k. Verifying that is trivial, you just follow the route and compare to k.