3 ms·

How to solve supposedly intractable problems

40 points by bluemoon 15y ago

reginaldo 15y ago
This is a great post. It basically says that when you have a problem that seems intractable, look for the conditions under which it is intractable and see if the conditions apply for your specific case. Many times they don't. And even if they do, you can often pretend they don't and still get solutions that are good enough. For a small pearl on problem solving, I recommend "How to solve it"[1], by the great mathematician George Pólya[2]. It teaches you simple techniques you can apply when you are stuck, like "draw a picture", "think about a similar problem you already know the solution for", and "solve a relaxed version of your problem". It all looks pretty much like common sense, but it is not. It's one of those few books I think everyone should read (whenever they are stuck). [1] http://www.amazon.com/How-Solve-Mathematical-Princeton-Science/dp/069111966X http://www.amazon.com/How-Solve-Mathematical-Princeton-Scien... [2] http://en.wikipedia.org/wiki/George_P%C3%B3lya http://en.wikipedia.org/wiki/George_P%C3%B3lya
- gwern 15y ago
  Exactly. One of the most valuable things I ever learned in my philosophy classes was that when someone presents you with a valid proof of something (in this case 'NP-hard is intractable in general'), you have to check whether it is 'sound' - whether it actually applies to you or your beliefs or the material under discussion. The premises are conditions which may or may not be true, and you must check them. As Cook points out, often they don't apply.
RuggeroAltair 15y ago
I'm not really sure what the point of this post is. It seems pretty standard in all it says. It's probably good to remind people that an NP-complete problem doesn't mean death, but I mean, in real world problems I think that everybody knows what the author is explaining. I don't even think that he get the point across really well. Two things: - there is no emphasis on the fact that we live in a real world, so a solution to an integral at any desired accuracy is definitely enough for non academic studies; - he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it). Of course in general there might be no way to know how much better you could do with the exact solution, but unless there is a Maxwell's devil choosing the set of your towns and roads, it's usually possible to estimate what the average error is (also in terms of some few computed cases and using Monte Carlo techniques). It won't give you the 100% certainty, but it'll give you the certainty that your solution is gonna be not that bad, given how quickly you get it. I would suggest another thing. When you have a problem that you know it's hard to deal with, give it to a very intelligent person in your team that doesn't know it's very hard to treat. Most likely they will be more creative than you can, because they don't have that sense of hopeless you get when you know that a problem has no exact and easy solution ;-) I'd say the real world problems are similar to the difference from math and physics according to one of my professors when I was a student. He'd say that when mathematicians and physicists try to approach a problem, their way of trying to find a solution is comparable to two guys approaching a cliff. The mathematician tries to carefully look at every rock and goes down to the ocean very very slowly, the physicist just jumps in an awkward way, kinda scared, screaming and closing their eyes and hoping they won't hit any rocks and that it won't end too bad (they aren't really risking their lives anyhow). If what you need is a real world solution, you can just jump and see how it goes, you most likely won't die for that (because you are also probably not actually jumping off a cliff).
- tripzilch 15y ago
  > he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it). That doesn't really correspond to the real world problems that TSP occurs in. While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design. I'm not super-knowledgeable on either of those two, so I could be wrong, though. Another point, which is not mentioned in the OP, is about graph problems. A lot of the intractable ones are really intractable only for a (large or infinite) class of degenerate inputs. But on the average case, solving it for "real world" graphs, for a lot of practical applications they can be solved in very reasonable time.
  - RuggeroAltair 15y ago
    > While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design. That is true, but it's the same that I was saying (and it's why I included the many variations at the end of the statement). Basically if you have to do something once and for all, then of course you can just solve it in some sort of educated brute force and you are probably fine. It's when you have to continuously adapt the solution to a changing network that you need to be fast, and in that case you need to consider that the computation time kinda together with the traveling time (of course it's more complicated than that and you need to include the cost advantages etc.). I agree with the graph comment, even if we are growing in the amount of data to deal with those graphs, so there will be often more and more need of simplified or shortened solutions if you want them to run in an app on a phone, or on a server (but for a million requests).
    - PotatoEngineer 15y ago
      Another example: Collision detection, finding the shortest path, and other physical-world problems are NP-Hard (as the number of dimensions increases, it gets really disgusting to find intersections and paths). But there are a large number of 3D games out there, because "3" is few-enough dimensions that we can compute it with modern computers really fast.

40 points by bluemoon 15y ago

This is a great post. It basically says that when you have a problem that seems intractable, look for the conditions under which it is intractable and see if the conditions apply for your specific case. Many times they don't. And even if they do, you can often pretend they don't and still get solutions that are good enough. For a small pearl on problem solving, I recommend "How to solve it"[1], by the great mathematician George Pólya[2]. It teaches you simple techniques you can apply when you are stuck, like "draw a picture", "think about a similar problem you already know the solution for", and "solve a relaxed version of your problem". It all looks pretty much like common sense, but it is not. It's one of those few books I think everyone should read (whenever they are stuck). [1] http://www.amazon.com/How-Solve-Mathematical-Princeton-Science/dp/069111966X http://www.amazon.com/How-Solve-Mathematical-Princeton-Scien... [2] http://en.wikipedia.org/wiki/George_P%C3%B3lya http://en.wikipedia.org/wiki/George_P%C3%B3lya

gwern 15y ago
Exactly. One of the most valuable things I ever learned in my philosophy classes was that when someone presents you with a valid proof of something (in this case 'NP-hard is intractable in general'), you have to check whether it is 'sound' - whether it actually applies to you or your beliefs or the material under discussion. The premises are conditions which may or may not be true, and you must check them. As Cook points out, often they don't apply.

RuggeroAltair 15y ago

I'm not really sure what the point of this post is. It seems pretty standard in all it says. It's probably good to remind people that an NP-complete problem doesn't mean death, but I mean, in real world problems I think that everybody knows what the author is explaining. I don't even think that he get the point across really well. Two things: - there is no emphasis on the fact that we live in a real world, so a solution to an integral at any desired accuracy is definitely enough for non academic studies; - he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it). Of course in general there might be no way to know how much better you could do with the exact solution, but unless there is a Maxwell's devil choosing the set of your towns and roads, it's usually possible to estimate what the average error is (also in terms of some few computed cases and using Monte Carlo techniques). It won't give you the 100% certainty, but it'll give you the certainty that your solution is gonna be not that bad, given how quickly you get it. I would suggest another thing. When you have a problem that you know it's hard to deal with, give it to a very intelligent person in your team that doesn't know it's very hard to treat. Most likely they will be more creative than you can, because they don't have that sense of hopeless you get when you know that a problem has no exact and easy solution ;-) I'd say the real world problems are similar to the difference from math and physics according to one of my professors when I was a student. He'd say that when mathematicians and physicists try to approach a problem, their way of trying to find a solution is comparable to two guys approaching a cliff. The mathematician tries to carefully look at every rock and goes down to the ocean very very slowly, the physicist just jumps in an awkward way, kinda scared, screaming and closing their eyes and hoping they won't hit any rocks and that it won't end too bad (they aren't really risking their lives anyhow). If what you need is a real world solution, you can just jump and see how it goes, you most likely won't die for that (because you are also probably not actually jumping off a cliff).

tripzilch 15y ago
> he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it). That doesn't really correspond to the real world problems that TSP occurs in. While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design. I'm not super-knowledgeable on either of those two, so I could be wrong, though. Another point, which is not mentioned in the OP, is about graph problems. A lot of the intractable ones are really intractable only for a (large or infinite) class of degenerate inputs. But on the average case, solving it for "real world" graphs, for a lot of practical applications they can be solved in very reasonable time.
- RuggeroAltair 15y ago
  > While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design. That is true, but it's the same that I was saying (and it's why I included the many variations at the end of the statement). Basically if you have to do something once and for all, then of course you can just solve it in some sort of educated brute force and you are probably fine. It's when you have to continuously adapt the solution to a changing network that you need to be fast, and in that case you need to consider that the computation time kinda together with the traveling time (of course it's more complicated than that and you need to include the cost advantages etc.). I agree with the graph comment, even if we are growing in the amount of data to deal with those graphs, so there will be often more and more need of simplified or shortened solutions if you want them to run in an app on a phone, or on a server (but for a million requests).
  - PotatoEngineer 15y ago
    Another example: Collision detection, finding the shortest path, and other physical-world problems are NP-Hard (as the number of dimensions increases, it gets really disgusting to find intersections and paths). But there are a large number of 3D games out there, because "3" is few-enough dimensions that we can compute it with modern computers really fast.