the traveling-salesman problem

A salesman must visit a list of cities, each exactly once, and return home, paying the road-distance between consecutive cities, and wants the cheapest possible round trip. This is the traveling-salesman problem, perhaps the most famous optimization problem in all of computing. The number of possible tours explodes factorially with the cities, so brute force is hopeless beyond a few dozen, yet the problem is everywhere: logistics, chip wiring, DNA sequencing.

There are two flavours, and the distinction is the whole point of this field. The OPTIMIZATION version, find the minimum-cost tour, is NP-hard but is not (known to be) in NP, because a single tour is not an obvious certificate that it is THE shortest. The DECISION version asks instead: given a budget B, is there a tour of total cost at most B? This version IS in NP, since a tour with cost at most B is a certificate a verifier sums up in polynomial time, and it is NP-complete. We turn the optimization problem into the decision problem to fit it into the NP framework, then study the decision problem's completeness.

Decision-TSP is NP-complete by a short reduction from the Hamiltonian cycle problem: set every existing edge's cost to 1 and every missing edge's cost to a huge number, then a tour of cost at most n (the number of cities) exists exactly when a Hamiltonian cycle exists. TSP also showcases the gap between worst-case theory and practice. The general problem is NP-hard, but the metric version (distances obeying the triangle inequality) has a classic factor-1.5 approximation (Christofides), and modern solvers find provably optimal tours for instances with thousands of cities. NP-hardness is a warning, not a wall.