P != NP

Moonliner · 08-09-2010, 11:27 AM

*Whew*

It looks like P != 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 · 08-09-2010, 11:38 AM

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 · 08-09-2010, 11:47 AM

Also possibly of interest it the Metafilter thread. The post at 11:38 AM (starts "Losts of problems involve...") is a good layman's explanation.

Kevy Baby · 08-09-2010, 06:29 PM

WHOOSH

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

Ghoulish Delight · 08-09-2010, 06:55 PM

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 · 08-09-2010, 11:50 PM

Wiki explanation of the problem

Capt Jack · 08-10-2010, 08:58 AM

Quote:

Originally Posted by Kevy Baby

WHOOSH

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

yeah, went past me like a rifle shot

08-09-2010, 11:27 AM	#1
Moonliner 8/30/14 - Disneyland -10k or Bust. Join Date: Jan 2005 Posts: 9,022	P != NP Whew It looks like P != 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. __________________ - Taking it one step at a time.
	Submit to Quotes

08-09-2010, 11:38 AM	#2
Alex . Join Date: Feb 2005 Posts: 13,354	I'll wait a while before getting too excited (not the first proof that's been put out there) but it is big news.
	Submit to Quotes

08-09-2010, 11:47 AM	#3
Alex . Join Date: Feb 2005 Posts: 13,354	Also possibly of interest it the Metafilter thread. The post at 11:38 AM (starts "Losts of problems involve...") is a good layman's explanation.
	Submit to Quotes

08-09-2010, 06:29 PM	#4
Kevy Baby Chowder Head Join Date: Jan 2005 Location: Yes Posts: 18,500	WHOOSH That's the sound of this going right over my head. __________________ The thing about quotes on the internet is that you cannot verify their validity. - Abraham Lincoln
	Submit to Quotes

08-09-2010, 06:55 PM	#5
Ghoulish Delight I Floop the Pig Join Date: Jan 2005 Location: Alternative Swankstyle Posts: 19,348	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. __________________ 'He who receives an idea from me, receives instruction himself without lessening mine; as he who lights his taper at mine, receives light without darkening me.' -TJ
	Submit to Quotes

08-09-2010, 11:50 PM	#6
Morrigoon I throw stones at houses Join Date: Jan 2005 Location: Location: Location Posts: 9,534	Wiki explanation of the problem __________________ http://bash.org/?top "It is useless for sheep to pass a resolution in favor of vegetarianism while wolves remain of a different opinion." -- William Randolph Inge
	Submit to Quotes