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…