Traveling Salesman: A Seemingly Unsolvable Problem Offers a Glimpse of the Limits of Computation

Image: Illustration by Thomas Fuchs

Showcasing more than fifty of the most provocative, original, and significant online essays from 2011, The Best Science Writing Online 2012 will change the way...

Read More??

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. Most mathematicians expect this to be impossible.

But suppose that you are handed the locations of 100,000 cities. Is it really impossible to find the shortest route? We are not asking for a solution to every instance of the TSP, just the quickest way around these specific locations.

To take up the challenge, your best bet is to follow Yogi Berra?s advice: ?When you come to a fork in the road, take it.? A tool called linear programming allows us to do just that by assigning fractions to roads that join pairs of cities rather than deciding immediately whether to use a road or not. In this model, it is perfectly fine to send half a salesman along both branches of the fork. The process begins with the requirement that, for every city, the fractions assigned to the arriving and departing roads each sum to 1. Then, step by step, further restrictions are added, each involving sums of fractions assigned to roads. Linear programming eventually points us to the best decision for each road and thus the shortest possible route.

I should add that 100,000 cities is not a hypothetical challenge. Current computations are zeroing in on the solution to a pretty set of 100,000 points created by Robert Bosch of Oberlin College, where the tour traces out a drawing of the Mona Lisa. We may not be able to knock off every example of the TSP, but new ideas can push the frontiers of solvability.

Here is the big picture: complexity theory suggests there are limits to the power of general computational techniques in science and elsewhere. What are these limits and how widely do they constrain our quest for knowledge? That is what research into the TSP is all about.

This article was published in print as "The Case of the Traveling Salesman."

packers score ricky gervais napoleon dynamite michelle williams the descendants the descendants homeland