The Traveling Salesman's Nightmare

The Traveling Salesman Problem (TSP) asks: given n cities, what is the shortest route that visits each city exactly once? This is a permutation problem — you are ordering cities — and the numbers destroy any hope of brute force.

For 10 cities: 3.6 million routes, checkable in seconds. For 20 cities: 2.4 quintillion routes. A computer checking a billion routes per second would need 77 years. For 50 cities, the route count dwarfs the number of atoms making up the Earth.

No one has found a fast exact method for it. TSP belongs to the famous P vs NP question — and the Clay Mathematics Institute offers a $1 million prize for settling whether problems like it can be solved quickly.