&gt;  Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.<p>This is a pretty funny claim to see made about one of the most famous NP-complete problems there is. As thelema314 points out, the usual certificate verifies &quot;is this path shorter than a threshold?&quot;.