Home
TSP is an NP-hard problem in combinatorial optimization. That's a term academics use to classify its complexity. When a problem is NP-hard, we cannot (yet) prove that a polynomial time solution exists.
A problem is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(nk). Polynomial-time algorithms are said to be "fast."
BUT WHAT DOES IT MEAN‽
In layman's terms, when a problem is described as "NP-hard", that means it belongs to a class of problems that very quickly become computationally expensive to solve as the input size grows. These problems are in fact rather easy to solve by enumerating all possible solutions and testing them, but solving them takes a long time on larger instances of the problems.
TSP is one of the most intensively studied problems in optimization. It's used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of error.
