3 ms·
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
by PeterisP 11y ago
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.
- 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.