Quick solution check for the TSP

329 Views Asked by At

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...

2

There are 2 best solutions below

0
On BEST ANSWER

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

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.