Yes; the sheer size of the search space isn&#x27;t what makes the problem hard.<p>Here is an obvious difference:<p>In sorting, we have locally correct solutions in that given any two distinct elements a, b out of the N, we know whether a is to the left or to the right of b in the final order.  Moreover, for a given a, we can find, in linear time, the smallest b which is greater than a: a&#x27;s successor in the sorted order.  Thus sorting is no worse than quadratic. Also, we can examine any permutation of the N items and tell in one pass whether or not it is in sorted order. So <i>recognizing</i> solutions to the sorting problem is linear.<p>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>So, yes, the mere fact that there are N! orders to search through is by itself unconvincing about the hardness of the problem.<p>Lectures on it would be easy if that were the case: <i>Good morning everyone; today we discuss a class of so-called &quot;NP hard&quot; problems, which occur whenever there is a combinatorial explosion in a search space.</i> :)