The traveling salesman problem — P versus NP
An extension of the combinatorics, permutations and computational-complexity topic. The number of possible traveling-salesman routes grows like (n-1)!/2 — explosively, faster than any polynomial function. We know no fast algorithm that solves this problem for large n — this is the heart of the P versus NP question, formalized by Stephen Cook in 1971 and placed by the Clay Institute on the list of Millennium Problems in 2000 (a $1M prize, still unsolved).
I’ll give you a target number of routes — use the slider to set the number of cities n so as to reach it. Number of routes = (n−1)!/2.
What just happened?
A traveling salesman must visit all n cities exactly once and return to the start, looking for the shortest possible route. We increased the number of cities from 6 to 15, and the number of possible routes to check exploded from 60 to over 43 589 145 600.
The model: how many routes are there?
A route is a permutation of n cities, but the starting point is arbitrary (we divide by n), and a route traversed in both directions has the same length (we divide by 2). What remains is:
For n = 5 that is only 12 routes — easy to check all by hand. For n = 10 it is already 181,440 routes. For n = 15 it is over 43,589,145,600 (43.6 billion) routes. And for n = 20 it is over 60 quadrillion — more than the fastest computer in the world could check in centuries.
P versus NP — one of the most important questions in mathematics
The traveling salesman problem is a classic example of an NP-hard problem: a solution (a specific route) is easy to check — just sum the segments and compare with a limit X. But we know of no fast (polynomial) way to find such a shortest route for large n — the only sure method is checking (almost) all (n-1)!/2 possibilities. Stephen Cook formalized this question in 1971: can every problem whose solution can be quickly verified (class NP) also be quickly found (class P)? This “P versus NP” question remains unsolved — the Clay Mathematics Institute placed it in 2000 on the list of 7 “Millennium Problems”, offering a million dollars for a proof. Most computer scientists suspect that P ≠ NP, but nobody has proved it.
What does it mean in practice?
This is not just an academic curiosity. The security of modern cryptography (including RSA encryption, which protects your passwords and online transactions) rests on the assumption that some problems are easy to verify but hard to solve. If someone proved that P = NP and exhibited a fast algorithm, most of today’s cryptography would cease to be secure.
Why this matters for your exams:
The factorial (n-1)! and dividing by symmetries (direction, starting point) is a standard combinatorial trick from advanced mathematics — the same rules for counting permutations with constraints appear in problems about arranging people in a row or around a round table.
Remember: the number of traveling-salesman routes is exactly (n-1)!/2, no matter how the cities are placed on the map — and it grows factorially, that is, faster than any polynomial or exponential function. That is why the traveling salesman problem is NP-hard, and the “P versus NP” question is still waiting to be solved.
Theory & formulas
Number of routes
For cities the number of distinct cycles (with a fixed start, not distinguishing direction): grows factorially — faster than any polynomial function.
The classes P and NP
P — problems solvable quickly (in polynomial time); NP — quickly verifiable. Whether remains open (a Millennium Problem).
Significance
We know no fast algorithm for large . The security of cryptography rests on a similar difficulty.
Notation: the number of cities, the number of possible routes.
Frequently asked questions
›How fast does the number of traveling-salesman routes grow?
Explosively — factorially, as (n-1)!/2, far faster than linearly or exponentially.
›What is the P versus NP problem?
The question of whether every quickly verifiable problem (NP) can also be quickly solved (P) — unsolved since 1971.
›What is its practical significance?
The security of cryptography (e.g. RSA) rests on the assumption that some problems are hard to solve though easy to verify.
Teaching? Embed this experiment on your site.
Free widget — paste it on your school site, blog or notes. It links to the full version.