Imagine that a salesman must travel to n cities and wants to take the shortest route possible. Assume that the salesman can start from any city on his itinerary and that the distance from city X to city Y is the same as the distance from Y to X (i.e., there exist no one-way shortcuts).

For small values of n, the traveling salesman problem (TSP) is simple. With three cities, for example, there is only one possible route; with four cities, three routes exist. Unfortunately, as the number of cities increases, the number of possible routes grows immensely. In general, for n cities, there exist ((n - 1)!) / 2 routes to consider. (The factorial (n - 1)! = (n - 1) ⋅ (n - 2) ⋅ ... ⋅ 3 ⋅ 2 ⋅ 1.) For a tour of nine cities, there are 20,160 different routes; for n = 15, the number of possible routes surpasses one trillion.

Although the traveling salesman problem has been solved for some large values of n, the best algorithm known to date is of order 2ⁿ, which means that the time required to solve the TSP grows exponentially with the size of the problem. For each 30 cities added to the salesman's route, the time required to solve the problem with today's algorithms increases by a factor of one billion, since 2³⁰ is approximately 10⁹.

Since an exponential algorithm requires too much time to produce a precise answer to the TSP, one might instead turn to a heuristic or greedy algorithm. A heuristic is a rule or procedure that almost always delivers the right answer. Almost always won't be good enough in some circumstances, but in many occasions a fast, almost-certain-to-be-correct answer will be better than a slow, absolutely correct one.

The TSP is equivalent to a class of mathematical problems called N-P ("nondeterministic polynomial") complete problems, which are often used to create security features on computers and networks. No one has proved that a fast algorithm for the TSP, or N-P complete problems in general, doesn't exist, and in the unlikely event that one is discovered, alternative security measures would have to be put into place quickly.