The Traveling Salesman Problem (TSP)
You'll learn: How TSP asks for the shortest route through all cities with no repeats—a famous NP-complete optimization problem that connects graph theory to real-world logistics.
What Is the TSP?
Imagine a traveling salesperson who must visit every city on their route exactly once, then return home. The challenge: find the shortest possible tour that hits all cities. This is the Traveling Salesman Problem—deceptively simple to state, brutally hard to solve optimally.
Why It's NP-Complete
TSP belongs to the class of NP-complete problems. While we can easily verify that a given tour has a certain length (just add up the distances), finding the optimal tour seems to require checking exponentially many possibilities as cities increase.
For n cities, there are roughly (n-1)!/2 possible tours. With 10 cities, that's over 181,000 tours. With 20 cities? Over 60 quintillion. Brute force quickly becomes hopeless.
The Decision Version
To fit NP-completeness formally, we phrase TSP as a decision problem: "Does there exist a tour of length ≤ k?" This version was proven NP-complete by reduction from the Hamiltonian Cycle Problem you learned previously—if you can solve TSP, you can solve Hamiltonian Cycle (just set all edge weights to 1).
Real-World Impact
TSP isn't just theoretical. It models delivery routing, circuit board drilling, DNA sequencing, and more. Since optimal solutions are often impractical, researchers use approximation algorithms and heuristics that find "good enough" solutions in reasonable time.
Key Takeaway: The Traveling Salesman Problem seeks the shortest tour visiting all cities exactly once—a cornerstone NP-complete problem that epitomizes the difficulty of combinatorial optimization.