On his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

Cover Interview of February 13, 2012

In a nutshell

You wake up in the morning and find that you need to visit a number of cities or towns before returning in the evening. What is the shortest possible route to bring you to each of the locations and safely home again?

Sounds simple enough, but it is in fact a long-standing open question in mathematics—known as the traveling salesman problem, or TSP for short.

As an existential problem, any particular example of salesman routing poses no real challenge. The task comes down to determining the order in which we should visit the locations on our list. To find the best route we simply check each possible ordering and record the shortest.

So the solution for the salesman is out there, but can we actually find it?

A quick counting argument will convince you that when faced with fifty locations or so, all of the world’s computers together could not possibly check each possible ordering. The question is whether we can quickly sift through this impossibly large number of routes and pull out the shortest. Developing such an efficient solution method for the TSP is the focal point of an intense study by the research community into the nature of complexity.

In Pursuit of the Traveling Salesman traces the history of how mathematicians have slowly come to grips with the salesman problem—and how its study has led to a better understanding of the world around us. The book is aimed at a general audience, adopting the TSP to give a tour of modern applied mathematics and some of the important questions we face in the information age.

Spontaneous generation is one of those wrong theories that clutter the basements of the biological sciences and that now look so very obviously wrong that it is hard to see how anyone could have taken them seriously in the first place. Why wouldn’t it occur to anyone that flies might be laying eggs that were too small for us to see? How simple would the crucial experiment be? What I have tried to do in much of my work is to turn this ‘obvious wrongness’ on its head—why, exactly, does it seem so obviously wrong?—and see what the new picture that emerges from that inquiry says about science and our belief in its results.

It’s commonplace to say that humor is subjective, since what’s funny to you might not be funny to me. But humor is also a loaded concept. If you – or your people – have no sense of humor, or the wrong one, that means you’re less rational, tolerant, understanding, or civilized. You don’t get it. Or, worse, you lack something human. Modern Chinese debates about humor were very much caught up with these fundamental questions of value.

## In a nutshell

You wake up in the morning and find that you need to visit a number of cities or towns before returning in the evening. What is the shortest possible route to bring you to each of the locations and safely home again?

Sounds simple enough, but it is in fact a long-standing open question in mathematics—known as the traveling salesman problem, or TSP for short.

As an existential problem, any particular example of salesman routing poses no real challenge. The task comes down to determining the order in which we should visit the locations on our list. To find the best route we simply check each possible ordering and record the shortest.

So the solution for the salesman is out there, but can we actually find it?

A quick counting argument will convince you that when faced with fifty locations or so, all of the world’s computers together could not possibly check each possible ordering. The question is whether we can quickly sift through this impossibly large number of routes and pull out the shortest. Developing such an efficient solution method for the TSP is the focal point of an intense study by the research community into the nature of complexity.

In Pursuit of the Traveling Salesmantraces the history of how mathematicians have slowly come to grips with the salesman problem—and how its study has led to a better understanding of the world around us. The book is aimed at a general audience, adopting the TSP to give a tour of modern applied mathematics and some of the important questions we face in the information age.