P != NP

[Moonliner]

*Whew*

It looks like P != NP (http://gregbaker.ca/blog/2010/08/07/p-n-np/). So all my mathematician buddies get to keep their jobs, our banking system is still secure, and life will go on. That was a close one.

[Alex]

I'll wait a while before getting too excited (not the first proof that's been put out there) but it is big news.

[Alex]

Also possibly of interest it the Metafilter thread (http://www.metafilter.com/94553/Complex-matters-for-the-millenium). The post at 11:38 AM (starts "Losts of problems involve...") is a good layman's explanation.

[Kevy Baby]

WHOOSH


That's the sound of this going right over my head.

[Ghoulish Delight]

Here's the best non-techie sounding analogy I can come up with (it's a little clumsy):

Let's assume for a construction company, building types fall into 1 of two categories. "P" or "NP"

For building types that fall into the "P" category, if it takes a builder X amount of time to complete a project of a certain size (Y), any larger projects of similar type of course take longer. Specifically, the amount of time they take is some relatively slow-and-steady-growing equation. So perhaps the amount of time can be described as 100*Y. Or Y^2. Or even Y^2000. So if Y doubles or triples or gets 100 times bigger, it's not a gigantic penalty.

Now, for "NP" projects, as they get bigger, the amount of time needed to complete it grows very very very rapidly. 10^Y, or 100^(3Y+6). In that case, if Y doubles, the penalty is huge.

I think everyone can follow along with that.

Now the tricky part. Assume that you've analyzed the 2nd type of project and learned that for many of the projects that fall into that category, it turns out that they all pretty much consist of the same kind of construction (say, nailing sets of boards together in a particular way). And nailing those boards together is itself a project that belongs in the NP group. So if you can figure out how to nail those boards together more efficiently...efficiently enough that you can then move the "nailing boards together in that way" project over into the "P" category...well then voila, you've now moved all of those other ones into the "P" category as well. And holy hell you've saved a lot of people a lot of work.

So far, no one's been able to figure out how to nail those boards together efficiently enough. And they've been trying for so long and so hard, that everyone pretty much agrees that it can't be done.

What this paper claims to do is PROVE that it can't be done. So, not earth shattering, it's the unfortunate conclusion that everyone has already assumed to be true. But it's still significant since it means everyone can stop trying and move on to improving how we deal with those NP projects as best we can.

[Morrigoon]

Wiki explanation of the problem (http://en.wikipedia.org/wiki/P%3Dnp)

[Capt Jack]

WHOOSH


That's the sound of this going right over my head.

yeah, went past me like a rifle shot