The “Traveling Salesman” problem is a famous instance of a problem for which it is easy to guess and check a solution, but which requires exponential time to solve exactly. Here, informally, is the problem: You are given a map of 100 cities in the US, with the distance between each pair of cities. Your job is to start at a given city (say, Boulder); visit each of the other 99 cities exactly once; and then return to Boulder. Naturally, there are many itineraries you could choose to accomplish this. Your goal is to find the minimum-total-distance itinerary that accomplishes your goal. (Sometimes the goal is phrased by stating a target value: i.e., your goal is to find any itinerary that visits each city exactly once, and requires at most M miles of travel.) The sure-fire approach to this problem is to (first) list out all the possible 99-city itineraries (we assume Boulder is the first and last city); sort the list according to miles traveled; and select the cheapest route. How long is our list of possible 99-city itineraries?
