Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is the quintessential problem of combinatorial optimisation: given a set of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin. It is NP-hard, which means that no known algorithm solves all instances in polynomial time, and that if one did, it would imply P = NP — collapsing the complexity hierarchy that underpins modern cryptography, scheduling, and logistics.

Despite its deceptively simple statement, TSP has resisted efficient solution for over a century. It is not merely a puzzle. It is a probe into the nature of computational difficulty itself.

The Structure of Combinatorial Explosion

The brute-force approach — enumerate all possible routes and select the shortest — requires examining (n−1)!/2 permutations for n cities. For 20 cities, this is approximately 60 quintillion routes. For 50 cities, it exceeds the number of atoms on Earth. This is the combinatorial explosion that defines NP-hardness: the solution space grows factorially while our computational resources grow polynomially. The gap between these growth rates is not an engineering inconvenience. It is a mathematical abyss.

The formal classification of TSP as NP-hard was established by Richard Karp in 1972, who proved that TSP is as hard as any problem in the class NP — a class of problems whose solutions can be verified in polynomial time but not necessarily found in polynomial time. Karp's proof used a polynomial-time reduction from the Hamiltonian cycle problem, demonstrating that an efficient TSP solver would automatically solve every NP problem efficiently. The conjecture that P ≠ NP — that this gap is fundamental, not merely unclosed — is the central open problem in computational complexity theory.

Exact Methods, Heuristics, and the Approximation Frontier

For small instances, exact methods can find optimal solutions. Branch and bound prunes the search tree by eliminating subpaths that cannot lead to a better solution than the best found so far. Cutting plane methods add linear constraints that exclude non-integer solutions, progressively tightening a linear programming relaxation until an integral optimal tour emerges. These methods have solved instances with tens of thousands of cities — but their success depends on instance structure, and their worst-case behaviour remains exponential.

For large instances, heuristics dominate. The nearest neighbour algorithm — start anywhere, repeatedly visit the closest unvisited city — is fast but can produce tours arbitrarily worse than optimal. 2-opt and 3-opt local search improve a tour by swapping edges until no improvement is possible. Simulated annealing and genetic algorithms escape local optima by accepting worse solutions with a probability that decreases over time. Christofides' algorithm guarantees a solution within 1.5× of optimal for metric TSP — the best known approximation ratio for the general metric case, unchanged since 1976.

The persistence of Christofides' 1.5-approximation as the best known result for half a century is itself a signal. It suggests that metric TSP occupies a structural boundary: close enough to tractable for approximation, yet far enough that exact solution remains out of reach. This boundary is not accidental. It reflects a deep property of the Euclidean plane — its triangle inequality, its geometric structure — that makes approximation possible while exact optimisation remains hard.

TSP as a Model System

TSP is not merely a logistics problem. It is a model system for studying complexity, optimisation, and emergence. In statistical physics, TSP is related to the random energy model and the physics of disordered systems. The optimal tour can be viewed as the ground state of a system with quenched disorder — the city positions are fixed, and the tour energy is the total distance. Studying TSP instances with random city positions reveals phase transitions in solution structure: as the number of cities grows, the optimal tour becomes increasingly determined by local structure, and global optimisation gives way to local patchwork.

In biology, TSP appears as the genome assembly problem: reconstructing a genome from short DNA reads is a TSP variant where the 'cities' are sequence fragments and the 'distances' are overlap scores. In neuroscience, the travelling salesman problem on graphs models how neural circuits might solve routing problems with distributed, parallel computation. In economics, TSP underlies vehicle routing, circuit board drilling, and telescope scheduling — domains where the difference between a good tour and an optimal tour translates into millions of dollars.

The Philosophical Weight of a Simple Problem

TSP's persistence as an open problem is philosophically significant. It is a problem any child can understand — visit these cities, find the shortest path — yet it defeats the most sophisticated algorithms and the fastest computers. This gap between intuitive comprehensibility and computational intractability is a signature of NP-hardness. It suggests that computational difficulty is not merely a matter of scale but a structural property of certain problem spaces.

The belief that 'sufficiently clever algorithms' or 'sufficiently powerful quantum computers' will eventually crack TSP misses the point. If P ≠ NP — and almost all complexity theorists believe it does — then no algorithm, classical or quantum, can solve all TSP instances efficiently. Quantum computers offer quadratic speedups for some problems (via Grover's algorithm) but not the exponential speedup required to collapse NP into P. TSP is not waiting for a better machine. It is waiting for a proof that better machines cannot help.

The Traveling Salesman Problem is the simplest possible question that reveals the deepest possible boundary — between what can be efficiently computed and what cannot. That this boundary remains unproven after seventy years of effort is not a failure of mathematics. It is mathematics' honest admission that some truths about computation are beyond its current reach. The problem is not the difficulty of finding a short tour. The difficulty is proving that the difficulty is necessary.