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

Subscribe to Support Independent Journalism

Great science journalism requires human expertise, time, effort and creativity. And it costs money. That’s why I and the journalists here at Scientific American hope you’ll join our community.

When you subscribe, you are supporting staff and freelance journalists who are passionate about telling science stories that are true, important and compelling. Our editors and reporters are often experts in their fields, which means they understand the nuances of big discoveries and can untangle the breakthroughs from the hype. With a subscription, you are also supporting rigorous fact-checking to ensure the words we publish are precise and accurate. And you’re supporting original illustrations, graphics and photos that bring you closer to an advanced laboratory, an ice sheet in Antarctica or a space mission in orbit. You’re helping us craft other types of high-quality journalism as well: Our newsletters are carefully written, edited and curated by staffers you have or will come to know and love. Our Science Quickly podcast is based on original reporting, collaboration with editors and scientists and exacting production.

Subscriptions keep this engine running so we can continue to deliver thoughtful, rigorous and independent science journalism to you. In an era of viral misinformation, this work is crucial. If you value what we do, I hope you’ll consider joining us as a subscriber

Thank you,

Jeanna Bryner, Editor in Chief, Scientific American