The Simplest Hard Problem
Here is a problem you can explain to a ten-year-old in thirty seconds. A salesman has to visit twenty cities, starting and ending at home. He wants the shortest possible route. Which way should he go?
That's it. There's no trick, no hidden variable, no sneaky philosophical twist. Just cities, roads, and distance. A child can understand it. A child could even try to solve it — and, as we'll see, a child might do surprisingly well.
But here's the thing: no one on Earth knows how to solve it efficiently. Not for twenty cities. Not, in the general case, for any large number of cities. And by "no one on Earth" I don't mean "no one has gotten around to it yet." I mean there are strong theoretical reasons to believe that an efficient solution doesn't exist — that the universe simply isn't built that way.
The Traveling Salesman Problem is the poster child of computational complexity: a question so easy to ask that it feels like it should be easy to answer. It isn't. And the gap between those two things — between the simplicity of the question and the impossibility of the answer — tells us something deep about the nature of mathematics itself.
Let's start with the numbers. With 20 cities, the salesman has 20 choices for his first stop, then 19 for his second, then 18 for his third, and so on. That's 20 × 19 × 18 × … × 1, better known as 20 factorial, written 20!. Since every tour and its reverse are the same route, we divide by 2. The result is roughly 1.2 × 1017 possible routes — about 120 quadrillion.1
If a computer could check a billion routes per second, it would take about four years to check them all. Bump it to 30 cities and you need more time than the age of the universe. At 100 cities, the number of possible routes exceeds the number of atoms in the observable universe by a factor so absurd that writing down the factor would itself require more atoms than exist.
Number of possible routes (log scale). By 20 cities, brute force would take years; by 25, longer than the age of the universe.
This is the factorial explosion, and it is not a minor inconvenience. It's a wall. Most problems get harder as they get bigger, but the Traveling Salesman Problem gets harder at a rate that makes "harder" feel like an understatement. It's not climbing a steeper hill; it's watching the hill turn into Everest and then into Jupiter.
A Brief, Improbable History
The problem floated around mathematical circles in the 1930s, though pinpointing exactly who "invented" it is surprisingly hard — like tracing the origin of a folk song.2 What we know is that by the 1950s, it had become a central challenge in the new field of operations research. And in 1954, three mathematicians at the RAND Corporation — George Dantzig, Ray Fulkerson, and Selmer Johnson — did something remarkable.
They solved a 49-city instance. Optimally. Not approximately, not "pretty close" — they found the provably shortest route through 49 cities in the United States and proved no shorter route could exist.3 They did this not by checking all the routes (there are roughly 1062 of them, which would have been a challenge even for the RAND Corporation) but by a clever technique called cutting planes: they formulated the problem as a linear program, then systematically added constraints to slice away impossible solutions until only the optimum remained.
It was a tour de force. It was also, in a sense, a magic trick — because the method worked beautifully for that instance but offered no general guarantee. The TSP remained, and remains, unsolved in the deepest sense.
Why "Hard" Means Something Specific
In 1972, Richard Karp proved that the Traveling Salesman Problem is NP-hard.4 This sounds like jargon, but the idea behind it is one of the great organizing insights of modern mathematics, and it deserves a moment of your time.
Think of it this way. Some problems scale gracefully: sorting a list of a million numbers takes about twenty times longer than sorting a list of fifty thousand. Double the input, and you roughly double the work. These are polynomial-time problems — the work grows as a manageable power of the input size.
TSP is not one of these. As far as anyone can tell, the work grows exponentially — not like climbing a longer staircase, but like the staircase regenerating new flights beneath your feet as you climb. NP-hard means something even worse: if anyone found a fast algorithm for TSP, it would automatically solve thousands of other problems we also believe to be intractable. Finding a polynomial-time algorithm for TSP would be equivalent to proving P = NP, which would overturn decades of theoretical computer science and also, incidentally, break most of modern cryptography.5
Most experts believe no such algorithm exists. But — and this is the wonderful, pragmatic twist — it doesn't matter.
Chapter 57Good Enough Is Good Enough
Here's the dirty secret of the Traveling Salesman Problem: we may not be able to find the best route, but we can find really, really good routes. Fast. And in practice, "really good" is all you need.
The simplest approach is the nearest-neighbor heuristic. Start at any city. Go to the closest unvisited city. Repeat until you've visited them all, then go home. It's the algorithm equivalent of doing your errands in whatever order seems most convenient right now.
And like doing your errands in whatever order seems most convenient right now, it has a tendency to leave you driving across town at the end because you forgot one stop. Nearest neighbor is fast — linear time, essentially — but it can produce tours that are 20% or 25% longer than optimal. Sometimes worse.
The next level up is 2-opt, and it's based on an insight so simple it feels like cheating. Look at your tour. Find any two edges that cross each other. Uncross them. Repeat until no edges cross. Each swap shortens the tour, and you stop when no more improvements are possible.
The 2-opt move: when two edges cross, uncrossing them always produces a shorter tour. Simple, effective, and surprisingly powerful.
Two-opt typically gets you within 5–8% of optimal. Not bad for an algorithm you could explain to a middle schooler. And then there's the crown jewel of approximation algorithms: the Christofides algorithm, published by Nicos Christofides in 1976.6 It uses a combination of minimum spanning trees and minimum-weight perfect matchings to guarantee — mathematically guarantee — that the tour it produces is no more than 1.5 times the length of the optimal tour. For nearly fifty years, no one has improved on that guarantee. It's one of the most stubborn bounds in all of combinatorial optimization.
The Approximation Paradox
TSP is provably hard to solve exactly, but provably easy to solve approximately. Christofides guarantees you're within 50% of optimal — and in practice, modern heuristics routinely get within 1–2%. The gap between "impossible" and "good enough" is where the real world lives.
Beyond Christofides, there's a whole zoo of approaches: simulated annealing (imagine heating metal and slowly cooling it — you allow the tour to get temporarily worse to escape local optima), genetic algorithms (breed good tours together and mutate the offspring), Lin-Kernighan (a hyper-optimized generalization of 2-opt). The Concorde TSP solver, developed by David Applegate, Robert Bixby, Vašek Chvátal, and William Cook, has solved instances with tens of thousands of cities to provable optimality.7
Try It Yourself
Don't take my word for it — watch the algorithms in action. Click on the canvas below to place cities, then run nearest neighbor and 2-opt to see how they compare.
TSP Solver
Click to place cities. Then run the algorithms and watch the tour improve.
Everywhere You Don't Expect It
If the Traveling Salesman Problem were merely a mathematical curiosity, it would still be a good story. But it turns out that TSP is everywhere.
UPS uses a system called ORION — On-Road Integrated Optimization and Navigation — that solves massive TSP-like problems for its fleet of delivery trucks every single day. The company estimates ORION saves 100 million miles of driving per year and roughly $400 million in fuel and labor costs.8 Amazon's warehouse robots navigate pick-and-pack routes that are, at their core, traveling salesman problems. When a circuit board manufacturer needs to drill thousands of holes, the drill head traces a TSP tour. Even DNA sequencing relies on a variant: finding the shortest superstring that contains all observed fragments is essentially TSP in disguise.
UPS drivers don't turn left. Well, they try not to. Left turns across traffic waste time and fuel, so ORION's TSP-based routing heavily penalizes them. The result: UPS trucks trace right-turn-heavy loops that look bizarre on a map but are ruthlessly efficient in practice. This is what TSP looks like when it escapes the textbook.
The beautiful irony is that while we can't prove we've found the optimal UPS route, the heuristic solutions save hundreds of millions of dollars. Perfection is the enemy of extremely profitable near-perfection.
Chapter 57The Human Advantage
Here is perhaps the strangest fact about the Traveling Salesman Problem: you are pretty good at it.
In experiments dating back to the 2000s, psychologists have found that when humans are shown a scattering of 10 to 20 dots on a screen and asked to draw the shortest loop through all of them, they consistently produce tours that are within a few percent of optimal — and they do it almost instantly, in a fraction of a second, with no conscious calculation at all.
This shouldn't be possible. The problem is NP-hard! Your brain is not secretly running a cutting-plane algorithm. What seems to be happening is that the human visual system uses powerful perceptual heuristics — something like "follow the convex hull, then fill in the interior" — that happen to work extremely well for the geometric version of TSP. We see the shape of a good tour in the same way we see a face in a cloud: not by computation, but by pattern.
Humans instinctively trace the convex hull first (red dashes), then connect interior points (blue). This "perceptual shortcut" produces near-optimal tours surprisingly often.
And here's the kicker: for small instances, humans routinely beat the nearest-neighbor algorithm. Your brain, with zero training in combinatorial optimization, outperforms a computer running the most obvious strategy. Try it below.
Human vs. Algorithm
Click cities in the order you'd visit them to draw your tour. Then see how you compare to the algorithms.
Click "New Challenge" to generate cities, then click them in order to draw your route.
What TSP Teaches Us
The Traveling Salesman Problem matters not because anyone is particularly worried about traveling salesmen. It matters because it is a lens — a way of seeing a whole class of problems that are everywhere in the world and that share the same maddening structure: easy to state, hard to solve, but amenable to solutions that are good enough.
Scheduling nurses at a hospital. Assigning students to schools. Routing packets across the internet. Folding proteins. Planning a road trip. These are all, in their bones, combinatorial optimization problems. They all live in the shadow of NP-hardness. And they all succumb, in practice, to the same pragmatic philosophy: don't let the perfect be the enemy of the good.
This, I think, is one of the most useful lessons mathematics has to offer. There is a deep human instinct to search for the best answer — the optimal solution, the perfect route, the right choice. And mathematics tells us, with great precision, that this instinct is often misguided. Not because perfection doesn't exist, but because the cost of finding it vastly exceeds the benefit of having it.
The salesman who uses 2-opt and arrives at a tour that's 3% longer than optimal? He's done. He's better than done — he's saved hours of computation for a negligible cost. The lesson of TSP is not "some problems are hard." The lesson of TSP is: most problems are hard, and that's fine, because good enough is almost always good enough.
The next time you're agonizing over the optimal order to run your errands, remember: you're facing a problem that has defeated every mathematician and computer scientist who ever lived. Then remember that your brain, with its quick visual intuition and its willingness to settle for "pretty good," is already doing a better job than you think. Sometimes the best algorithm is the one between your ears.