Mathematics
The Traveling Salesman Problem and Why It Is Hard
Quick fact
For 15 cities, there are over 43 billion possible routes to check—but a computer can handle it. However, for 100 cities, the number of routes exceeds the number of atoms in the entire universe!
Why this is interesting
Imagine you have to visit 15 cities by car and return home. You’d probably think, ‘How hard can that be?’ But the Traveling Salesman Problem turns out to be one of the most fiendishly difficult puzzles in all of mathematics.
Read the full explanation
Understanding The Traveling Salesman Problem and Why It Is Hard
The Traveling Salesman Problem (TSP) asks: given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the starting city? It’s easy to understand—just find the shortest loop. But the hard part is that there are many possible loops. With only 4 cities, there are just 3 distinct routes (since the starting city is fixed and direction doesn’t matter). But the number of possible routes grows incredibly fast—it’s (n-1)!/2 for n cities. So, for 10 cities, that’s 181,440 routes; for 15, it’s 43 billion; for 20, it’s 60 quadrillion. Even the fastest supercomputer would take longer than the age of the universe to try every route for just 30 cities. Because of this rapid growth, we can’t simply check every possible route when the number of cities is large. Instead, computer scientists have developed clever heuristics and approximation algorithms that find good—but not necessarily perfect—solutions in a reasonable time. This problem is a perfect example of a combinatorial optimization problem, where the size of the search space explodes with the input size, making exact solutions impractical.
A deeper explanation
The underlying difficulty of the TSP lies in its combinatorial explosion. The number of possible tours grows factorially with the number of cities, meaning that any algorithm that relies on checking all possibilities becomes infeasible for even moderately large inputs. In computational complexity theory, the TSP is a classic NP-hard problem: it is at least as hard as any problem in NP, and there is no known algorithm that can solve all instances in polynomial time. This means that no one has found a way to compute an exact solution efficiently for all possible inputs. The significance of this is profound: it means that for many real-world applications (like delivery route planning, circuit board drilling, or DNA sequencing), finding the absolutely optimal solution is impossible within reasonable time. Instead, researchers and engineers use heuristic methods like nearest-neighbor, genetic algorithms, or simulated annealing to find approximate solutions that are good enough for practical purposes. Understanding the TSP and its hardness helps us appreciate why some problems in computer science are fundamentally difficult, and why we must often settle for 'good enough' rather than perfect.