Why is the TSP hard?

Read first

• Post 1: What is the TSP? A tour visits every city once and returns to the start. Its cost is the sum of its legs. A tour is a permutation, and a symmetric instance has (n − 1)!/2 distinct tours. We used eight stops, A to H, with coordinates in kilometres and distances rounded to units of 100 m. Their optimal tour costs 315.
• Primer B: algorithms and complexity Big-O notation, and the difference between polynomial growth (n², n³) and exponential growth (2ⁿ, n!).

The question this post answers: if the TSP is so easy to state, why can’t we just compute the best tour?

Intuition

The most honest algorithm for the TSP is to try every tour and keep the cheapest. Let me run it on the eight stops from Post 1. Here is the distance matrix again, in units of 100 m.

Brute force has four steps:

1. Fix A as the first stop. A tour is a cycle, so where you start writing it does not matter.
2. List every ordering of the other seven stops. There are 7! = 5,040.
3. Throw away mirror images. In a symmetric instance, A-B-C-…-H and A-H-…-C-B are the same tour driven in opposite directions. Keep an ordering only if its first stop comes alphabetically before its last. That halves the list to 2,520.
4. Price each tour (eight additions) and remember the cheapest.

Here is that algorithm as code, printing every time it finds a new best:

import math
from itertools import permutations

STOPS = {"A": (2, 2), "B": (6, 1), "C": (9, 3), "D": (8, 7),
         "E": (5, 9), "F": (1, 8), "G": (4, 5), "H": (10, 9)}  # km

def d(a, b):  # straight-line distance in units of 100 m, rounded (TSPLIB style)
    (x1, y1), (x2, y2) = STOPS[a], STOPS[b]
    return int(10 * math.hypot(x1 - x2, y1 - y2) + 0.5)

def cost(tour):
    return sum(d(tour[i], tour[(i + 1) % len(tour)]) for i in range(len(tour)))

start, rest = "A", sorted(STOPS)[1:]
best, checked = None, 0
for order in permutations(rest):
    if order[0] > order[-1]:      # skip the mirror image of a tour already seen
        continue
    tour = (start,) + order
    checked += 1
    c = cost(tour)
    if best is None or c < best[0]:
        best = (c, "".join(tour))
        print(f"tour #{checked:>4}: {best[1]}  cost {c}  <- new best")
print(f"checked {checked} tours; optimum {best[1]} = {best[0]}")

Its output:

Step through the diagram below to watch the record holder change; the lengths it shows are unrounded kilometres, so they differ from the matrix costs in the table by a few tenths.

The optimum turns up at tour 19. The search still has to price the other 2,501 tours, because nothing about tour 19 tells you it is the best. That is the core of the difficulty: a good tour does not carry proof of its own quality.

The table below is the distribution of all 2,520 tour costs, in buckets of 50.

Most tours sit near the middle (the median is 490). Only 6 of 2,520 are within 10% of the optimum, and only 2 within 5%. Picking a tour at random is hopeless, and the good tours are rare.

The formal idea

Counting. With n cities in a symmetric instance there are (n − 1)!/2 distinct tours. n! (n factorial) is 1 × 2 × … × n. Brute force prices each tour in about n additions, so its running time is O(n · (n − 1)!) = O(n!).

The table below shows how that count grows, with the time it would take at one billion tours per second. That speed is generous for a single machine, and it does not change the shape of the table.

The universe is about 1.4 × 10¹⁰ years old. Going from 15 cities to 20 multiplies the work by about 1.4 million. Every extra city multiplies the work by roughly n, so a computer that is 1,000 times faster buys you only a few more cities.

Polynomial vs. exponential. An algorithm is polynomial if its running time is O(nᵏ) for some fixed k. Sorting is O(n log n); Dijkstra is polynomial too. Polynomial algorithms scale: doubling n multiplies the time by a constant. Factorial and exponential algorithms do not.

Decision version. Complexity theory talks about yes/no questions, so restate the TSP: given the matrix D and a number K, is there a tour of cost at most K? Call this TSP-DECISION. If you can answer it quickly, you can find the optimal cost by binary search over K.

P and NP, informally.

• P is the class of yes/no problems that some algorithm can solve in polynomial time.
• NP is the class of yes/no problems where a “yes” answer comes with a certificate you can check in polynomial time. For TSP-DECISION the certificate is a tour. Checking it takes O(n): confirm each city appears once, add up n legs, compare to K.
• A problem is NP-complete if it is in NP and every problem in NP can be translated into it in polynomial time. Solve one NP-complete problem in polynomial time and you have solved all of NP in polynomial time.
• A problem is NP-hard if it is at least that hard, whether or not it is itself a yes/no problem in NP. The optimization version of the TSP (“find the cheapest tour”) is NP-hard.

Whether P equals NP is open. It is one of the Clay Mathematics Institute’s Millennium Prize Problems. Most researchers believe P ≠ NP, which would mean no polynomial algorithm exists for the TSP.

Where the TSP’s hardness comes from. Karp (1972) showed that the Hamiltonian cycle problem is NP-complete: given a graph, is there a cycle that visits every vertex exactly once? The TSP inherits that hardness through a short translation, sketched below. Take any graph G with n vertices. Build a complete graph on the same vertices: an edge costs 1 if it is in G and 2 if it is not. Then G has a Hamiltonian cycle exactly when the TSP has a tour of cost n. The diagram below shows the translation as a flow: build the weighted instance, ask one TSP question, read off the Hamiltonian-cycle answer.

flowchart TD
  G["Graph G, n vertices"] --> K["Complete graph, same vertices"]
  K --> W["Cost 1 if edge in G, else 2"]
  W --> Q{"Tour of cost at most n?"}
  Q -- yes --> Y["G has a Hamiltonian cycle"]
  Q -- no --> N["G has no Hamiltonian cycle"]

So a fast TSP algorithm would give a fast Hamiltonian-cycle algorithm, which would show P = NP. Garey and Johnson (1979) list the TSP decision problem among the standard NP-complete problems.

Optimal vs. good enough. NP-hardness is a statement about the worst case as n grows. It does not say every instance is hopeless, and it does not say near-optimal tours are hard to find. That leaves two practical paths:

1. Exact methods that prove optimality and are fast on many real instances, even though their worst case is exponential. In March 2025, Cook and colleagues finished proving an optimal walking tour through 81,998 bars in South Korea. By their rough estimate it used about 44 years of total CPU time, run in parallel over about two months.
2. Heuristics that return a good tour quickly with no proof. The simplest is nearest neighbour: from the current stop, go to the closest unvisited one. On our eight stops it gives A-G-E-D-H-C-B-F-A, cost 385, which is 22% above the optimum of 315. On berlin52, starting from city 1, it gives 8,980, a 19.1% gap to 7,542. Both numbers come from my own run of the rule; ties are broken alphabetically.

The gap is how we will measure heuristics throughout this series:

gap = (cost found − optimal cost) / optimal cost × 100%

For instances where the distances obey the triangle inequality, there are heuristics with worst-case guarantees, such as Christofides’ algorithm (1976), which is never more than 50% above optimal. For a general matrix, no polynomial algorithm can promise any constant-factor guarantee unless P = NP (Sahni and Gonzalez, 1976). Approximation gets its own post later in the series.

Common misconceptions

“NP means ‘not polynomial’.” NP stands for nondeterministic polynomial time. It is the class of problems whose “yes” answers can be checked quickly. Every problem in P is also in NP.

“NP-hard means every instance is impossible to solve.” Hardness is about the worst case. berlin52 is small enough that exact codes prove 7,542 routinely, and instances with tens of thousands of stops have been solved to proven optimality. What NP-hardness predicts is that no method will be fast on every instance.

“A faster computer will fix it.” Each extra city multiplies brute force by about n. A machine 1,000 times faster lets brute force handle roughly two or three more cities at the sizes in the table above.

“If my heuristic printed 7,542, it proved the tour is optimal.” It matched a number that someone else proved. A heuristic has no way to know it has hit the optimum on a new instance. Proofs need lower bounds, which arrive in Part 2 of this series.

Try it in Python

Brute force cannot touch berlin52, but the nearest-neighbour rule from this post can. It builds a tour in a fraction of a second, and because TSPLIB publishes the optimum, we can measure exactly how good it is.

import math

body = open("berlin52.tsp").read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
xy = [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]
d = [[int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in xy] for p in xy]  # EUC_2D
OPTIMAL = 7542

def nearest_neighbour(d, start=0):
    tour, left = [start], set(range(len(d))) - {start}
    while left:
        here = tour[-1]
        nxt = min(left, key=lambda c: (d[here][c], c))  # closest unvisited city; ties to the lower number
        tour.append(nxt)
        left.remove(nxt)
    return tour

def cost(tour):
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

c = cost(nearest_neighbour(d))
print(f"nearest neighbour from city 1:  {c}, gap {100 * (c - OPTIMAL) / OPTIMAL:.1f}%")
c = min(cost(nearest_neighbour(d, s)) for s in range(len(d)))
print(f"best of all 52 starting cities: {c}, gap {100 * (c - OPTIMAL) / OPTIMAL:.1f}%")

It prints:

That is the “good enough” path in one table. A fast rule gives a usable tour, a little extra effort (trying every start) halves the gap, and nothing in the output tells you how far you are from optimal. We only know the gap because someone else proved 7,542. Closing that gap is the job of local search in Part 4 and iterated local search in Part 5.

Exercise

Run the brute-force script with nine stops by adding a stop I at (7, 5), then ten stops with J at (3, 7). Time each run. Before running the ten-stop version, predict its runtime from the nine-stop one.

Hint: going from n to n + 1 cities multiplies the number of tours by n. Compare your prediction with the measurement, then use the same ratio to estimate how long fifteen stops would take on your machine.

What this method can’t do yet

Brute force answered a clean question: one salesman, eight stops, any order, any time of day. Real problems rarely look exactly like the TSP. Suppose stop B must be served within the first 60 minutes and stop F within the first 140 (with one distance unit per minute). The tour that brute force crowned, A-B-C-D-H-E-F-G-A, reaches F at minute 237, so it is no longer allowed. And that is one constraint of many: two vans instead of one, stops you may skip for a penalty, a hard limit on route length. Post 3, “The TSP family”, introduces those variants and shows how each one changes the answer on the same eight stops.

References

• Karp, R. M. (1972). “Reducibility Among Combinatorial Problems.” In R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum, 85–103.
• Cook, S. A. (1971). “The Complexity of Theorem-Proving Procedures.” Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158.
• Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
• Sahni, S., and Gonzalez, T. (1976). “P-Complete Approximation Problems.” Journal of the ACM 23(3): 555–565.
• Christofides, N. (1976). “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem.” Management Sciences Research Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University.
• Cook, W., Espinoza, D., Goycoolea, M., and Helsgaun, K. (2025). “Korea TSPs” and “korea81998 Computation.” University of Waterloo. https://www.math.uwaterloo.ca/tsp/korea/
• Clay Mathematics Institute. “P vs NP.” Millennium Prize Problems. https://www.claymath.org/millennium/p-vs-np/
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; TSPLIB 95 files and list of optimal solutions.

See the whole series · ← All writing