Mathematics
The Traveling Salesman Problem and Its Computational Complexity
Quick fact
The number of possible routes for n cities grows factorially: for just 20 cities, there are ~2.4 × 10^18 possible tours—so many that checking them all would take billions of years even on a supercomputer.
Why this is interesting
You have to visit five friends spread across your city and return home. What's the shortest route? Now imagine fifty friends—your brain might give up, and a computer quickly runs out of patience too.
Read the full explanation
Understanding The Traveling Salesman Problem and Its Computational Complexity
The traveling salesman problem (TSP) asks for the shortest possible route that visits each city exactly once and returns to the starting city. Picture it as a graph: cities are points, and the distances between them are weighted edges. A route is a Hamiltonian cycle—a loop that hits every vertex once. The simplest way to solve it is brute force: list every possible order of cities and compute the total distance for each. For n cities, the number of different cycles is (n-1)!/2, because the starting point doesn't matter and direction doesn't matter. That factorial grows explosively. With 10 cities, there are ~181,440 cycles; with 20, the number becomes astronomical. The key insight is that no shortcut is known that avoids considering an exponentially large number of possibilities in the worst case.
A deeper explanation
The reason TSP is computationally hard lies in its combinatorial explosion. The problem belongs to the class NP-hard: any other NP problem can be transformed into a TSP instance in polynomial time. This means that if someone discovered a polynomial-time algorithm for TSP, it would prove P=NP, resolving one of mathematics' biggest open questions. The underlying mechanism is that the optimal route must be found among an exponential number of permutations, and no known algorithm can prune the search space efficiently in the worst case. This complexity has practical consequences: for large instances, exact algorithms are infeasible, so researchers and industry rely on heuristics like nearest neighbor, genetic algorithms, and approximation schemes that give good (but not always optimal) solutions. Understanding TSP's complexity is essential for recognizing why many real-world scheduling and routing problems are inherently difficult and why approximation is often necessary.