5 ms·

In retrospect, the traveling salesman problem was actually an impediment for me to understand the P vs. NP question. Reasons: 1) Formally, P vs. NP is presente

In retrospect, the traveling salesman problem was actually an impediment for me to understand the P vs. NP question. Reasons: 1) Formally, P vs. NP is presented as a binary YES/NO question rather than a "what is the smallest number such that <something>"? Only after you grasp the Y/N format of the question are you shown the trick where you can convert any problem in FNP into NP by converting it into a binary Y/N question with the help of a binary search. If you are presented initially with the TSP as the canonical P/NP problem, it is unclear for a while how it fits into the formal presentation 2) (If my understanding on this point is incorrect, I will be glad if someone disabuses me of my misconception): Sometimes, P vs. NP is presented as "problems to which it is harder to find the solution than to verify a solution once it's given". TSP is not actually one of those problems: if someone hands you a possible solution, the process for verifying that it is indeed correct is equivalent to finding it in the first place.

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 ago
  A 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.
eru 16y ago
About 2): If somebody gives you the minimal solution and some additional information, you can verify it in P. The size of the additional information is no more than polynomial in the size of the problem.

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

eru 16y ago

About 2): If somebody gives you the minimal solution and some additional information, you can verify it in P. The size of the additional information is no more than polynomial in the size of the problem.