# Coming Full Circle

### The Traveling Salesman Problem and the dream of optimality

## D. Graham Burnett

The problem is easily stated: given a finite number of points, find the shortest connecting path—the shortest line that touches each point once, and closes on itself by returning to the point of departure. What could be more straightforward? It is a problem a child can understand—a simple game of connect-the-dots.

It is also, however, a problem of absolutely legendary difficulty. Add more than a handful of points, and a brute-force solution requires more computer-years than there are particles in the universe. Untold millions of human- and machine-hours have now been expended on the problem, which has come to function as a touchstone for theories of complexity, and as a kind of conceptual fetish object at the center of the overlapping disciplines of applied mathematics, algorithm theory, and computational geometry. There is, at present, a million-dollar bounty on its head, and some of the very deepest questions in theoretical computer science hang on the prospect of a general solution.^{[1]}

Mathematicians call it the TSP—the Traveling Salesman Problem, a moniker that speaks subtly to the twinned genealogies of capitalism and calculating rationality. And indeed the problem—which has become nothing less than a model system for understanding what can be understood—began its life as a head-scratcher for the shock troops of consumer economics, those late eighteenth- and early nineteenth-century itinerant missionaries of an increasingly abstract and globalizing market. Those men girded their loins and shouldered their sample cases only after perusing the new cartographies made available by centralizing states and expanding empires. They *plotted their routes*, these drummers, and did so with an eye on the bottom line. Which is to say, actual travelling salesmen fretted the TSP long before a clutch of Cold War theoreticians at the RAND Corporation found their way to it, and restyled it as an all-purpose test of number-crunching power and analytic ingenuity. Tellingly, the earliest formulation of the problem would seem to hail from a German-language gazetteer/handbook prepared in the early 1830s for commercial travelers intending to make tours through the Swiss cantons and the German lands. That volume (*Der Handlungsreisende—von einem alten Commis-Voyageur*), mindful that time and space were money, carefully laid out a thirty-three-city circuit—Freiberg-Dresden-Leipzig-Halle, etc.—that pretended to optimality.^{[2]}

Optimality. Life itself is obviously not an optimization function. Nevertheless, one could do worse than describe modernity as the ideological commitment to a progressive extension of optimization logic to domains of self and society not previously understood to yield to such treatment. Where the limits of this exercise lie remains unclear. Again and again it has proven possible (and profitable) to step over the various boundaries inscribed by tradition, habit, and custom. By these lights, “logistics”—the formal science of spatio-temporal optimization; the toolkit for synchronized coordination of human beings and materials in dynamic systems; the study of all problems that can be stated in the form, “Who and what are where when, and how could we do it better?”—must be understood as nothing less than the standard-bearer for social, political, and economic transformation across the last two centuries. Where the formal concepts and technics of logistics have gone—and they have sequenced impressively through war, wealth production, and governance—the modern world has followed.

It is difficult to résumé this history succinctly. And perhaps quixotic to attempt to do so in pictures. But given this ambition, there is much to be said for a survey of graphical representations of the TSP. The trajectory of such a sequence—from the scratch pad plottings of proto-capitalist peddlers to the meta-analytic musings of those who hope to solve the general problem of what problems can be solved—traces an efficient (or is it scenic?) route across the fields of metaphorical money and countinghouse metaphysics.

Let’s take the tour.

- Specifically the “P versus NP” problem. At stake is the issue of whether there exists a polynomial-time solution to all problems for which there is known to be a polynomial-time algorithm for solution verification. A finding in the affirmative (“P=NP”) would have significant implications for cryptography. Some have argued that the impact would be world-historic (an informed commentator recently opined in print that a proof of P=NP would “make the whole Internet look like a footnote in history”). For a general introduction to these matters, see Christos Papadimitriou,
*Computational Complexity*(Boston: Addison-Wesley, 1994). The million-dollar Clay Prize is actually on offer for a solution to P versus NP, but a general polynomial-time algorithm for the TSP would amount to a proof that P=NP and thus bag the prize. - On the
*Handlungsreisende*, see William J. Cook’s*In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation*(Princeton, NJ: Princeton University Press, 2012). Special thanks to Professor Cook for his generosity in sharing expertise and source material.

D. Graham Burnett is an editor of *Cabinet*.

*If you’ve enjoyed the free articles that we offer on our site, please consider subscribing to our nonprofit magazine. You get twelve online issues and unlimited access to all our archives.*