Traveling Salesman A Seemingly Unsolvable Problem Offers A Glimpse Of The Limits Of Computation
Is it hopeless to try to compute the shortest route to visit a large number of cities? Not just a good route but the guaranteed shortest. The task is the long-standing challenge known as the traveling salesman problem, or TSP for short. Finding a method that can quickly solve every example of the TSP would be a stunning breakthrough in mathematics. Using complexity theory, such a method would allow us to solve efficiently any computational problem for which answers can be easily verified....