4 ms·

I'm confused by this post. I was under the impression NP-complete problems could not be solved efficiently, but the author is saying that TSP, the most well kno

I'm confused by this post. I was under the impression NP-complete problems could not be solved efficiently, but the author is saying that TSP, the most well known NP-complete problem, can be solved practically. I read what he wrote but did not understand what he was saying. Why is TSP famously hard if it's actually tractable in practice?

cvwright 11y ago
I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case is hard -- in fact, most instances that you're likely to run across in the real world might be quite easy. That's pretty much what the author is arguing here: > Due to the tremendous amount of work that has been done on the Traveling Salesman Problem, the TSP is one such problem. If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. The difference between problems that are hard in the average case, and those that are only hard in the worst case, is really important in cryptography. The knapsack cryptosystem is a good example of this: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
- te_platt 11y ago
  Exactly. A good example would be a set of co-linear points. Even for N=1,000,000 if all the points are at (n,0) on the plane then it's pretty trivial to find the solution.
geofft 11y ago
I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there's no particular intuition about how hard 3SAT (and 2SAT) should be. It's a fairly abstract mathematical construct. NP-complete problems admit no polynomial-time solution for every possible answer, and even if they run in more-than-polynomial time, there's no constraint on what those constants look like. Suppose the best algorithm takes 2^n / 2^100000 seconds. That's definitely more than polynomial, but also pretty fast for real-world problem sizes. It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora's and SUSE's dependency solvers (in dnf and zypper, respectively) convert your package dependencies to an instance of SAT and throw it at a generic SAT solver, because that's better-optimized.
rm445 11y ago
Each NP-complete problem is in fact a family of problems. In the sense that you could compute an optimal sales route between a small number of cities or optimally pack a very small knapsack in your head. I believe the point the posted article is making is that reasonable progress has been made against such problems of sizes that seem 'large' in terms of normal human experience, through brute-force computation and clever heuristic tricks. That doesn't mean they don't scale in the expected way or that a true shortcut has been found.

cvwright 11y ago

I think it's more accurate to say that NP-complete problems have at least some cases that cannot be solved efficiently. That's not to say that the average case is hard -- in fact, most instances that you're likely to run across in the real world might be quite easy. That's pretty much what the author is arguing here: > Due to the tremendous amount of work that has been done on the Traveling Salesman Problem, the TSP is one such problem. If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. The difference between problems that are hard in the average case, and those that are only hard in the worst case, is really important in cryptography. The knapsack cryptosystem is a good example of this: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...

te_platt 11y ago
Exactly. A good example would be a set of co-linear points. Even for N=1,000,000 if all the points are at (n,0) on the plane then it's pretty trivial to find the solution.

geofft 11y ago

I think it's famous because it's one of the most easily understandable NP-complete problems: it has a nice, intuitive "word problem" description. 3SAT has no such intuitive description. Even for those of us who understand boolean formulas, there's no particular intuition about how hard 3SAT (and 2SAT) should be. It's a fairly abstract mathematical construct. NP-complete problems admit no polynomial-time solution for every possible answer, and even if they run in more-than-polynomial time, there's no constraint on what those constants look like. Suppose the best algorithm takes 2^n / 2^100000 seconds. That's definitely more than polynomial, but also pretty fast for real-world problem sizes. It turns out that even SAT solvers are also pretty good in practice on real-world-sized problems, to the point where Fedora's and SUSE's dependency solvers (in dnf and zypper, respectively) convert your package dependencies to an instance of SAT and throw it at a generic SAT solver, because that's better-optimized.

rm445 11y ago

Each NP-complete problem is in fact a family of problems. In the sense that you could compute an optimal sales route between a small number of cities or optimally pack a very small knapsack in your head. I believe the point the posted article is making is that reasonable progress has been made against such problems of sizes that seem 'large' in terms of normal human experience, through brute-force computation and clever heuristic tricks. That doesn't mean they don't scale in the expected way or that a true shortcut has been found.