Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman problem) is true? That is, whether a given route is the shortest possible one. The problems are supposed to be equivalent...
2026-04-03 14:32:15.1775226735
On
Quick solution check for the TSP
329 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
5
On
One quickly checks "whether a solution for the TSP (travelling salesman problem) is true"
by quickly solving a coNP-complete problem.
I don't know how much asking about uniqueness changes the situation.
The TSP has to be modified to a decision problem for it to be quickly checkable. Plus there is an issue of discretization for the Euclidean TSP.
A comment on the human performance: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Human_performance_on_TSP