28
What exactly makes the travelling salesman problem hard, given that checking a route is trivial?
The problem is easy to state: visit every city once, return to the start, minimise total distance. Evaluating any particular route takes almost no work — add up the distances. So the difficulty is entirely in the search…