4 ms·
1) Agreed. 2) You're right; TSP is NP Hard, not NP Complete. But if you're talking about the YES/NO version, then it is defined (ala Wikipedia) like this: "g
by edanm 16y ago
1) Agreed.
2) You're right; TSP is NP Hard, not NP Complete.
But if you're talking about the YES/NO version, then it is defined (ala Wikipedia) like this: "given the [graph and] costs and a number x, decide whether there is a round-trip route cheaper than x". This problem is NP Complete; it's easy to see that verifying in this case just means summing the weights and seeing if they are below `x`.
- Retric 16y agoA version I was told to think about was competing travel agents. At each step they need to find a better solution or know when to stop looking. It's still not quite there "given the [graph and] costs and a number x, decide whether there is a round-trip route cheaper than x" but if you are handed a graph you can say it's shorter and then give it as the answer. The difference is there may be approaches that prove there is a shorter path, without finding it. However, the mental model is vary close to the generic solution because someone can hand you the 2nd best solution which looks nothing like the best solution and you still need to find it. Where if you are handed the best solution they may be a shortcut to proving it's the best. PS: The Clique problem always seemed like the version where shortcuts seemed most obvious. But, understanding why they fail is a larger mental jump IMO than NP Hard TSP to NP Complete TSP.