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.<p>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).<p>[1] <a href="http://www.amazon.com/How-Solve-Mathematical-Princeton-Science/dp/069111966X" rel="nofollow">http://www.amazon.com/How-Solve-Mathematical-Princeton-Scien...</a><p>[2] <a href="http://en.wikipedia.org/wiki/George_P%C3%B3lya" rel="nofollow">http://en.wikipedia.org/wiki/George_P%C3%B3lya</a>
I'm not really sure what the point of this post is.<p>It seems pretty standard in all it says.<p>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.<p>I don't even think that he get the point across really well.<p>Two things:<p>- 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;<p>- 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).<p>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.<p>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 ;-)<p>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).<p>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).