What Is the Traveling Salesman Problem?

The traveling salesman problem (TSP) asks a deceptively simple question: given a list of cities and the distance between every pair of them, what is the shortest possible route that visits each city exactly once and returns to the starting point? It sounds like something a delivery app should solve instantly, and for a handful of cities it does — but the number of possible routes explodes so fast with each added city that no computer, however fast, can brute-force the exact answer once the list gets even moderately long. TSP is one of the most studied problems in computer science precisely because that gap between “simple to state” and “hard to solve exactly” is so extreme.

Why the problem explodes so fast

For n cities, the number of distinct routes to check is (n-1)!/2 (fixing a start point and ignoring direction, since a route and its reverse cover the same distance). That factorial growth is brutal: 10 cities have about 180,000 possible routes, comfortably checkable. 20 cities have over 60 quadrillion. By 30 cities, the number of routes exceeds any brute-force search a computer could complete before the heat death of relevance to whoever needed the answer. This is the textbook illustration of why understanding Big O notation matters: an algorithm with factorial or exponential time complexity doesn’t just get slower as input grows, it becomes unusable almost immediately past a small threshold, no matter how much faster hardware gets.

TSP and the P vs NP question

TSP belongs to a class of problems where no known algorithm can find the exact optimal answer in time that scales as a polynomial function of the input size — but a proposed answer can be checked quickly (add up the distances and compare to a target). That asymmetry between “hard to solve, easy to verify” is exactly the gap explored in the P vs NP problem, and TSP’s decision-problem variant (“is there a route shorter than length X?”) is one of the classic NP-complete problems used to prove other problems are similarly hard, via reduction. Nobody has proven that a fast exact algorithm for TSP is impossible — but decades of failed attempts by very motivated people are strong circumstantial evidence that it doesn’t exist, at least not one that runs in polynomial time on a conventional computer.

Exact approaches: better than brute force, still not fast

Brute force isn’t the only exact method — it’s just the worst one. Dynamic programming (the Held-Karp algorithm) reduces the problem to roughly O(n² · 2ⁿ), tracking the best route to each subset of visited cities rather than re-deriving every full permutation from scratch. That’s still exponential, but it’s a dramatic improvement over factorial growth, and it pushes the practical limit from roughly 15 cities to around 40. Branch and bound takes a different tack: it explores the same search space as brute force but prunes entire branches early once it can prove they can’t beat the best solution found so far, often finding and verifying the optimal route far faster in practice than the worst-case bound suggests, though the worst case remains exponential. Both approaches guarantee the true optimal answer; both remain impractical once the city count reaches into the hundreds or thousands, which is where most real-world instances of this problem actually live.

Heuristics and approximation: giving up optimality on purpose

For real-world use, giving up the guarantee of the perfect route in exchange for a good route computed in a reasonable time is usually the right trade. Common approaches include:

• Nearest neighbor — at each step, go to the closest unvisited city. Fast and simple, but can end up making a bad early choice that forces a long detour later; it offers no guarantee on how far the result is from optimal.
• 2-opt — start from any valid route and repeatedly swap pairs of edges if doing so shortens the total distance, until no such swap helps. A cheap, effective local-search improvement layered on top of a starting route from a method like nearest neighbor.
• Christofides’ algorithm — for the common case where distances obey the triangle inequality, this method guarantees a route no worse than 1.5 times the optimal length, built from a minimum spanning tree plus a matching step. It’s one of the few heuristics with a provable worst-case bound.
• Genetic and simulated-annealing methods — treat candidate routes like a population that evolves toward better solutions over many iterations, useful when the problem has extra constraints that make exact and classical heuristic methods awkward to apply directly.

None of these guarantee the optimal tour, but for practical logistics problems, a route within a few percent of optimal computed in seconds is far more useful than the exact optimal route computed in geological time.

Where TSP shows up outside the classroom

The problem’s reach extends well past literal delivery routing. Circuit board manufacturing uses TSP-style optimization to minimize the travel distance of a drill head across thousands of holes. Chip design uses it to order the placement and wiring of components. Genome sequencing has used TSP formulations to help reconstruct DNA fragment ordering. Any time a system needs to visit a large number of discrete points in the most efficient order — whether the “distance” is physical, electrical, or purely computational — the same combinatorial structure as TSP tends to reappear, which is part of why so much research effort has gone into approximation methods that generalize well.

Exact vs heuristic, at a glance

	Exact (DP / branch and bound)	Heuristic (nearest neighbor, 2-opt, etc.)
Guarantees optimal route	Yes	No
Practical city limit	Dozens to low hundreds	Thousands and beyond
Time complexity	Exponential	Polynomial
Typical use	Small, high-stakes instances	Large-scale, real-time routing

The takeaway

The traveling salesman problem is a simple question — find the shortest route through a set of points — with no known fast exact solution, making it a cornerstone example in the study of computational hardness. Exact algorithms like dynamic programming and branch and bound guarantee the true optimum but only scale to modest problem sizes; heuristics like 2-opt and Christofides’ algorithm sacrifice that guarantee for solutions that scale to real-world logistics problems with thousands of stops. Which approach to use is really a question of how much the last few percent of route efficiency is worth against how much time you have to compute it.