> Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.

Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.