Traveling Salesman (Decision)
← Back to NP-Complete
The decision version of TSP: given a set of cities and distances, is there a tour visiting each city exactly once with total distance at most k? NP-Complete. The optimization version (find the shortest tour) is NP-Hard. One of the most studied problems in combinatorial optimization.