The Traveling Salesman Problem – NP‑hardness

A salesman must visit n cities and return home, minimising total distance. The brute‑force solution checks (n‑1)!/2 routes – impossible for n=100 (≈ 10¹⁵⁷ routes). The problem is NP‑hard: no known polynomial‑time algorithm, but if P=NP then such an algorithm exists. Practical solutions use heuristics (nearest neighbour, genetic algorithms, branch and bound). The TSP appears in drilling circuit boards, genome sequencing, and telescope scheduling. It’s the quintessential optimisation problem and a testbed for AI and operations research.