&gt; 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&#x27;t know what a&#x27;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.<p>Usually, the problem is simplified to a threshold test, like: Does this tour have path length &lt; X?  These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.