As mathematical problems go, the “traveling salesman problem” (TSP) is a rare gem: it is simultaneously of great theoretical, historical, and practical interest. On the theoretical front, it is a well-known example of the class of “NP-complete” problems, which lie at the heart of the million-dollar “P vs NP” question (which I still intend to explain at some point). Historically, it has been studied for almost 200 years (given a sufficiently inclusive definition of “study”), and has occupied a place in the public consciousness for at least the last 50. And this great historical interest is partly due to the problem’s practical significance.

So, what is it? Given a set of points in the plane (or, more generally, a set of points with “distances” specified somehow between each pair of points), the problem is to determine the shortest path which visits every point exactly once and then returns to the starting location. Of course, in one sense this is “easy”: just list all possible paths and compute the length of each. Note, however, that for a set of points, there are (that is, ) possible paths that visit every point once and then return to the start. Even with only points, that’s a whopping possible paths—if you could compute the length of one trillion paths every second, it would still take 280 million millenia (that’s years, slightly longer than I’ve been alive) to check all of them! And that’s only points—in practice, people want to solve the TSP for sets of points much larger than . So the point is not just to “solve” the problem; the real question is, can it be solved efficiently?

Amazingly, no one knows! But that hasn’t stopped people from coming up with extremely clever algorithms that seem to work well in practice, on very large sets of points (i.e. thousands, or even tens of thousands of points)—even though there are “pathological” inputs for which these algorithms do essentially no better than just trying every path. So these algorithms constitute a good solution to the TSP from a practical point of view but not a theoretical one!

William Cook’s new book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, does a wonderful job presenting the history and significance of the TSP and an overview of cutting-edge research. It’s a beautiful, visually rich book, full of color photographs and diagrams that enliven both the narrative and mathematical presentation. And it includes a wealth of information (perhaps even a bit too much at times; I got lost in a few places). But it actually bills itself, partly, as an introduction to cutting-edge ideas in TSP research—and I think overall it succeeds admirably, explaining ideas in ways that are accessible but not patronizing. Read this book if you want a fun, beautifully illustrated introduction to (this one fascinating piece of) the edge of human knowledge!