The Travelling Salesman Problem
The Travelling Salesman Problem asks for the shortest route that visits a set of cities exactly once and returns to the start. It is NP-hard (its decision version is NP-complete), so no known algorithm solves every instance efficiently and brute force scales factorially. In practice it is tackled with exact dynamic programming for small inputs and fast heuristics like nearest neighbor, Christofides, and Lin-Kernighan for large ones.
The Travelling Salesman Problem (TSP) is a classic combinatorial optimization problem: given a list of cities and the pairwise distances between them, find the shortest possible tour that visits every city exactly once and returns to the starting point. Despite its simple statement, it is one of the most studied problems in computer science because it captures the difficulty of an entire class of hard problems. TSP is NP-hard, and its decision version — 'is there a tour shorter than length L?' — is NP-Completeness, placing it among the hardest problems in the Complexity Class NP. A brute-force search checks every ordering of the cities, and the number of distinct tours grows with the factorial of the city count (on the order of n! permutations). This blows up far faster than any polynomial, which is why complexity is judged by Why Complexity Is Measured Asymptotically, Not by Counting Steps rather than raw step counts. The best exact algorithm, the Held-Karp dynamic programming method, cuts this to O(n^2 * 2^n) time — still exponential, but enough to solve modest instances. Because exact methods cannot scale, practitioners rely on heuristics and approximation algorithms. The greedy nearest-neighbor rule builds a tour by repeatedly hopping to the closest unvisited city; it is fast but can be far from optimal. For metric instances (where distances obey the triangle inequality), the Christofides algorithm guarantees a tour no worse than 1.5 times optimal — a 3/2 bound that stood unbeaten for over forty years until a 2020 result by Karlin, Klein, and Oveis Gharan shaved off a tiny constant. In day-to-day practice the Lin-Kernighan heuristic, which iteratively swaps tour edges to escape local optima, produces near-optimal solutions for instances with thousands of cities and is considered the state of the art for local search. TSP and its variants underpin real logistics and engineering: vehicle routing, drilling holes in printed circuit boards, ordering DNA fragments in sequencing, and warehouse order-picking all reduce to finding short tours. It also sits at the heart of complexity theory. Because TSP is NP-complete, a polynomial-time algorithm for it would solve every NP problem efficiently, settling the P vs NP Problem: Fundamentals Explained in the affirmative; like the Boolean Satisfiability Problem (SAT), it is one of the canonical problems whose tractability would have sweeping consequences, as explored in What a Resolution of P versus NP Would Actually Look Like.