4 ms·
Can somebody explain to me why articles on complexity are careless with the term "Traveling Salesman Problem" (TSP)? To me, TSP means "find the shortest route
by wlievens 16y ago
Can somebody explain to me why articles on complexity are careless with the term "Traveling Salesman Problem" (TSP)?
To me, TSP means "find the shortest route visiting these cities once". That is not a problem that's in NP, since there's no way to verify the solution (shortest route) in polynomial time. Am I right?
What people typically mean is the decision version of TSP: "Find a route visiting all these cities that in less than X total distance cost". That's in NP, of course, since I can quickly check (a) the route connectedness (b) whether the route visits all cities once (c) the total cost of the route is below X.
Do I have my terminology wrong, or are people writing about a very formal territory so unusually careless with terminilogy?