4 ms·
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
by danpat 11y ago
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.
- PeterisP 11y agoThat 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.
- danbruc 11y agoNP 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.
- deleted 11y ago[deleted]
- baddox 11y agoYou 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.