Hacker News Reader

Comment by danpat | Hacker News Reader

There are a few ways to ask the TSP question. One question is "give me the shortest route geometry", this problem is NP-hard and can't be verified easily, this is what you're thinking of. However, the decision version of the problem is usually phrased "Is there a tour of less than length L", and this is NP-Complete - takes a while to find the tour, but it's trivial to check if it's less than length L.

View on HN

That works for one way (where the tour exists), however, if the true answer to the particular decision problem is "no! it can't be done in L steps!" - then the only way to verify is to repeat the whole process, no?

Having an easily verifiable tour that does it in L+1 doesn't really help in verification that some other combination could or could not do it in L steps.

NP only requires that you can verify a positive answer in polynomial time. Problems with polynomial time proofs for negative answers form the class Co-NP.

Besides that, if you can solve the decision problem and the distances are well-behaved, for example integers, you can solve the other variants, you can perform a binary search for the minimal tour length and you can find the actual tour by probing all edges, i.e. removing one by one and checking whether that increases the minimal tour length.

You can just choose an arbitrary starting L, and if the answer is No, keep doubling your guess until the answer is Yes, then just binary search from there. Or if you want to start with the maximum possible L, just start with the sum of all the edge weights in the graph.

Reply on news.ycombinator.com