Traveling salesman problem

The traveling salesman problem (TSP) is the quintessential computationally intractable problem: given a list 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 the canonical NP-hard optimization problem, and its intractability is not a quirk of bad algorithms but a structural feature of the problem itself — the search space grows factorially with the number of cities, and no known algorithm can guarantee an optimal solution in polynomial time. Yet TSP is also one of the most successfully attacked problems in all of optimization. Modern approximation algorithms, heuristic methods, and specialized solvers routinely find near-optimal solutions for instances with millions of cities. The gap between TSP's theoretical intractability and its practical solvability is not a paradox. It is evidence that real-world instances are not drawn from the uniform distribution of all possible graphs, but from structured distributions where geometry, clustering, and locality provide exploitable regularity. TSP is therefore not a monument to computational impossibility. It is a mirror that reflects how much the hardness of a problem depends on what you assume about the world that generates it.