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

Join Our Community of Science Lovers!

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.

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

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."

It’s Time to Stand Up for Science

If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.

I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.

If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.

In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.

There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.

Thank you,

David M. Ewalt, Editor in Chief, Scientific American