The standard newspaper example of computational impossibility, measured. The wall is real, it is at about twenty-five cities, and almost nobody has twenty-five cities.
A salesman based in São Paulo has clients in Rio, Belo Horizonte, Brasília and Curitiba. What order?
Not a good tour. The tour — there is provably nothing shorter. Add seven more cities and the answer is still exact:
Twelve cities is about twenty million distinct tours, and the machine ruled all of them out in nineteen milliseconds. Whatever NP-hardness is a statement about, it is not a statement about this.
So why does everyone know this problem as the one that cannot be solved?
The exact method above is Held–Karp: dynamic programming over subsets, $O(n^2 2^n)$. Timed:
Every extra city roughly doubles the work. Extrapolate the measured $n=18$ figure:
That is not a rhetorical flourish; it is the measured constant times $n^2 2^n$. The wall exists and it arrives suddenly, somewhere around twenty-five cities, and it is worth knowing about.
It is also not where the interesting part is.
Two local-search moves — 2-opt (uncross a pair of edges) and Or-opt (lift a short run of cities and reinsert it) — measured against the proven optimum, averaged over thirty random instances:
A few dozen lines of code land within four hundredths of one percent of an answer that is provably the best there is.
This is the part that gets left out, and it is the one that matters operationally. The Held–Karp 1-tree bound relaxes the tour to a spanning structure and then pushes node potentials until the relaxation nearly is a tour. It never produces a tour. It brackets one from below:
So the working procedure is: run the heuristic, run the bound, and if they close to within a fraction of a percent, stop. You have a tour and a certificate, and you never solved the problem the headline says you cannot solve.
∎The theorem: no algorithm is known that solves every instance in time polynomial in $n$, and if one existed then P = NP. Three qualifiers ride along, and the headline drops all three.
Worst case. It quantifies over the hardest instance at each size, not the one you have. Nothing in it forbids every instance you will ever meet from being easy.
Asymptotic. It is a claim about $n\to\infty$. At $n=5$ it makes no claim whatsoever, and §1 took forty microseconds.
Exact. It is about finding the optimum, not about getting close. §3 got within 0.04% and §4 proved it had.
And for the Euclidean case — which is what a map is — the theory runs the other way: Arora and Mitchell showed in 1998 that Euclidean TSP admits a PTAS, an approximation scheme reaching any fixed $\varepsilon$ in polynomial time.
Meanwhile the exact wall keeps moving. §2's algorithm dies near $n=25$. Concorde, using branch-and-cut rather than enumeration, solved an 85,900-city instance to proven optimality — certified and published.
Five cities and eighty-five thousand cities are both solved exactly. The famous impossibility lives in the gap between them, and it is a gap about algorithms, not about salesmen.
Not the combinatorics. §1 solved a national sales tour exactly, in milliseconds, in a hundred lines of Python. What a real problem has that this one does not:
Time windows. A meeting at 14:00 Tuesday is a constraint no distance matrix contains, and TSP with time windows is a genuinely harder problem than TSP.
The metric is wrong. §1 minimises great-circle distance. What is actually being minimised is hours, or fare, or fatigue — and the flight schedule between two Brazilian cities does not care how far apart they are.
Asymmetry. Real travel times are not symmetric and need not satisfy the triangle inequality, which most of the good theory assumes.
The data. Every figure above came from twelve pairs of coordinates. A real system's difficulty is almost entirely in keeping its inputs current, and none of that is a computational question.
Now the version that actually costs money. A company covering a country does not have one salesman visiting twelve cities; it has a field operation, and the question is not what order but how many people, based where.
That is p-median, not TSP: choose $k$ bases minimising the weighted distance from every client to its nearest one. Over the same twelve Brazilian metros, weighted by metro population:
Each base buys about a third off the remaining distance, steadily. There is no knee in that curve and therefore no natural $k$ — the decision is not hiding in the geometry, and anyone who tells you the optimiser chose the headcount is mistaken about what the optimiser did.
What the geometry does say is this:
Over half the weight sits in three adjacent metros. A field operation on this map does not have a travelling salesman problem worth solving. It has a concentration.
And that is the general lesson, which is why this chapter is in a book about people who got the question right. Optimising the route saves a percentage of travel. Getting the districting wrong costs a multiple of headcount. The second lever is far larger than the first, and only the first is famous — so the famous problem is the one that gets solved, over and over, next to the expensive one that does not.
Eight gaps in the script. The two worth stating here:
No large-instance gap is claimed. Running 2-opt at $n=1000$ against the 1-tree bound gives a spread of 11–13%, and that conflates heuristic suboptimality with looseness of the bound at that size. The bound's own quality at $n=1000$ was not established, so no figure is quoted. Published results put 2-opt near 5% above optimal at large $n$ — the sub-1% numbers in §3 are a small-$n$ effect and must not be read as a claim about large instances.
§7's weights are population, not clients. Commodity counterparties cluster by crop and by port, not by headcount. The concentration finding is robust to the weights being roughly wrong; the exact base sequence is not.
Producing script: book7/ch-the-salesman-verify.py — 7 sections, 8 gaps. CITED: Applegate, Bixby, Chvátal, Cook, Espinoza, Goycoolea & Helsgaun, Certification of an optimal TSP tour through 85,900 cities, Operations Research Letters 37 (2009) 11–15; Arora (1998) and Mitchell (1999) for the Euclidean PTAS. Related: WP-126, where the lever that matters is also not the one being optimised.