What is Digg?Sponsored by Bing.
Save Cash This Holiday Season. view!
bing.com - Affordable gifts that look expensive--Bing(tm) helps you find gifts under $50.
236 Comments
- darthjure, on 10/29/2009, -6/+440N = 1
I should have gone to MIT. - lex0429, on 10/29/2009, -6/+365I didn't find it confusing at all and I am only a janitor in a Boston based ivy league school where sometimes i solve problems like these left by teachers on blackboards.
- Perleeeze, on 10/29/2009, -6/+122You are all crazy!
P=NP means "Problem=No Problem", pretty much Homer's modus operandi. - BrandonJM, on 10/29/2009, -7/+115Interesting stuff, but the article needs a translation for stupid people like me.
- SoupErmanX, on 10/29/2009, -5/+95as simply as I can make it...
In computational theory, problems can be classified as being either 'P' or 'NP'. P are problems that we consider to be relatively quick to solve, whereas NP problems take a considerable amount longer.
For example, if you give a computer a list of 1,000 numbers, and ask it to sort them in numerical order, it should be able to do that relatively quickly - no more than a few seconds. So we consider that to be a 'P' problem.
The travelling salesman problem is an NP problem. It involves finding the shortest route between several cities (or points) such that you only visit each city once. If we were to give a computer this task with 1,000 cities, even with the most advanced super computers today, it would take many millions of years to solve.
So it would seem obvious that there is a difference between P and NP, however no one has yet been able to formally prove it.
Why does this matter? Well, if someone could in fact prove that yes P and NP are the same, given that the general nature of problems is that they can be transformed into each other in some way (these are known as complete problems), then all those NP-complete problems would suddenly become relatively quick to solve.
A real world application is in security, cracking an encryption is an NP problem. If P = NP was proven, well lets just say 4chan would have a field day... - IKORKYI, on 10/29/2009, -11/+101N=1
- domlachowicz, on 10/29/2009, -6/+92MIT's not in the Ivy League
- krispykreams, on 10/29/2009, -4/+85Your incapability of grasping the significance of this topic does not make it any less important.
- JimTrebek, on 10/29/2009, -5/+84My attempt at translation:
Some problems are "easy" for computers (P). What it means is that if you increase the size of the problem, the time it will take to solve it will increase according to a polynomial curve.
For example, say an algorithm A has a bound of N^2 seconds. If we increase the size from 10 to 100, the time will increase from 100 to 10000 seconds.
NP has problems that are really hard. Some of these go along exponential curves. So, say that an algorithm B has a bound of 2^N seconds. If we increase the size from 10 to 100, the time will increase from 1024 to 1.2 nontillion (1.2 million trillion trillion) seconds, or 40 billion trillion years. So, yeah...
The biggest reason why this sort of research is important is because that's a lot of what computer security is based on. Things like SSH work because, as far as we know, it's really hard (i.e. almost impossible) to do certain problems. Even if computer speed improves to the point where it's possible to crack keys through brute force (like MD5), all we have to do is increase the size of the key a little bit and suddenly it's a million times harder to crack.
Unfortunately, we haven't been able to prove that it's technically impossible to solve these problems in polynomial time, so someone might (though probably won't) find a way, and that would really screw up stuff, security-wise. - juliusthecat, on 10/29/2009, -4/+74or P = 0
- milwaukeesbeast, on 10/29/2009, -4/+72Simple (and therefore somewhat inaccurate) version:
Theres a group of problems that can be solved in a reasonable amount of time or greater. This entire set is called P. Some problems in P can be solved quickly. Then theres a group of problems that take longer inside P, these are called NP.
All problems in NP have a weird property that if you have an answer already, you can verify that it is correct in the same amount of time as the fastest problems in P. But solving the problem itself takes much longer. Some take so long in fact that there is no point in calculating the answer, it will take longer than the age of the universe. Yet you can still verify any answer in the short amount of time.
The idea is you want to prove that you can take a problem in NP and solve it in the same time as those fast ones in P. That would make P = NP. No one has proved you can do this. No one has proved you cant do this. If P did equal NP, it would have the same effect on humanity as the discovery of agriculture, electricity, and the transistor. Actually, even greater than all of those combined. But its very likely that you cant do this, most agree P does not equal NP. Prove me wrong. - NeoNevermore, on 10/29/2009, -6/+68If P=0, and trying to solve for N:
P = NP
N =P/P
Oh *****... - Crimeodial, on 10/29/2009, -1/+52You realize that not all scientists are biologists, right?
- MiJaMaLa1, on 10/29/2009, -5/+50Woah, Woah, Woah. Slow down egghead.
- scott1, on 10/29/2009, -18/+62P=NP=42
done - Mujokan, on 10/29/2009, -1/+45David Cohen loves these maths jokes. You get them in Futurama too. Then he sometimes rambles on for a couple of minutes trying to explain them in the commentary. But it's good to learn stuff from DVD commentaries, God knows I don't read as much as I should!
- DotFreelance, on 10/29/2009, -1/+39OH *****
IT'S CANCER
MATH IT - ag3ntorange, on 10/29/2009, -4/+42Power = Nuclear Power
- FriesandCoke, on 10/29/2009, -1/+35Next on the agenda: Figure out how Mike Nelson/Joel Robinson received food and oxygen while on board the SOL.
- Nerden, on 10/29/2009, -2/+36woo, someone inform the scientific community.
@IKORKYI, would you mind solving cancer while you are here?
Dugg btw - stuffradio, on 10/29/2009, -1/+34Recess did an episode like that where Gretchen had a math equation on the board, and the janitor whatever is name is came in and solved it.
- ileftfark, on 10/29/2009, -2/+35Yes, why aren't more mathematicians and Computer Science majors focused on pathology? WHY?
- OfoarHeffinsake, on 10/29/2009, -1/+33It's just a show, you really should relax.
- twtmc, on 10/29/2009, -2/+32If they were light years ahead of what we have currently they would be so far away from earth that they would be completely useless to us.
- jayhawk88, on 10/29/2009, -2/+31You know it's funny, because if one could prove that P=NP, it would arguably be a more important breakthrough than any of those feats you mention, as it would not only have an incredible effect on mathematics, but computing/algorithm theory as well, and quite possibly lead to computers that are light years ahead of what we currently have.
- diggerado, on 10/29/2009, -1/+29OH GOD!!!! I thought I escaped all that. MAKE THE MATH STOP HURTING!!!!
- Zaxcomp, on 10/29/2009, -0/+27*****
JUST THROW NUMBERS AT IT - Jordan117, on 10/29/2009, -1/+27The best explanation of the P=NP problem I've ever read, courtesy of a comment on Metafilter.com:
* * *
P vs NP is Absolutely Crazy *****. It takes a year to just understand the premise, after which a slowly rising crest of goosebumps mounts on your wretched body. And swells for a decade.
Please trust me on this, you really, really want to think a bit about P vs NP. Read the definitions. Take a nap. Reread them. Think about them on the bus. Stuff like that.
Now, P vs NP. What is it?
The basic philosophical question is this:
If you can understand something quickly, instantly recognise it, could you *do* it?
Note that this is taking us into the territory of human power; The vast, strange sphere of abstract capacity, in which true geniuses are measured to surpass normal people. E.g., a true genius can easily perform some act, and you can easily recognise the skill involved, the majestic beauty. But you can't *do it*.
If we prove that P is NP, we have proven that with the right methods, everyone, everything is a genius.
If we prove that P isn't NP, we have mathematically proven that essentially if you aren't a genius at something, there are some capabilities that are simply *out of your reach*, forever, until the end of time.
And the kicker is that thousands of true, true geniuses *haven't been able to prove it either way*. It's not that we don't know; All we know is that we cannot even yet know if we know.
Souce:
http://www.metafilter.com/84530/The-P-vs-NP-proble ...
See the first reply to this comment for a more involved technical explanation (also from Mefi). - cliffhanger407, on 10/29/2009, -0/+25This is mostly right... Only one problem that I can see is that some people might make the assumption that P=NP implies that problems in NP would be immediately reducible to a problem in P, or more specifically one which is reasonable to solve.
Solving something in P doesn't mean "quick" it means "in polynomail time" (which I'm sure you know based on your explanation, this is just for other people). You can consider a computer program as a series of operations. Given an input of size n, if the amount of time the program runs is in some amount of time that is polynomial with respect to n. So if it ran in n^2 time or in log(n) or in n^84390218490567891758162374862317867912643789163 time, it's still in P. Expanding to NP simply means it's not polynomial, but is exponential. This means your program could run in 2^n time. Or it could run in 4781932074^n time. Both of these are still in NP.
Even if you could prove P=NP, it may only be reducible to some polynomial like n^84390218490567891758162374862317867912643789163 time... which is still completely intractable and could never be reasonably solved. It's more of a toy problem anyway, most algorithms these days are randomized or approximations anyway. - KnightWhoSaysNi, on 10/29/2009, -0/+25That works!
- JDLamb88, on 10/29/2009, -2/+26WELL HOW DO YOU LIKE THEM APPLES
- levi88, on 10/29/2009, -1/+24If one could prove that P=NP, the resulting technology would likely be able to solve all those problems. And then some.
- nicc, on 10/29/2009, -0/+23exactly!
why do we have to bring theoretical sciences into this? just make it straight algebra... - reddikilowatt, on 10/29/2009, -1/+23Take that, you lousy dimension!
- wozup, on 10/29/2009, -0/+21...and by night he patrols the streets of Gotham.
- gdog05, on 10/29/2009, -0/+20"You win this round, Trebek!"
- LarkStew, on 10/29/2009, -0/+19Which is the basis of public key encryption.
- wolfmann, on 10/29/2009, -1/+19I'd rather prove you right, but it seems I can't do that either!
- OnAsideNote, on 10/29/2009, -0/+18They made a real Tomaco plant after Homer invented it . . Why Not ?
- MrLeo1984, on 10/29/2009, -0/+17You underestimate the strength of erotic cake stores.
- davidlyness, on 10/29/2009, -0/+17Good explanation, apart from the fact that MD5 isn't an encryption algorithm, and has no "key".
- ontain, on 10/29/2009, -0/+17there's a surprising lack of Homer in this article.
- bulgingbritches, on 10/29/2009, -2/+17Do you like apples too?
- Oztog, on 10/29/2009, -1/+16I wish they would make a second episode like that and finish the second half to get him back home
- CallMeRooster, on 10/29/2009, -4/+19"Enough of your borax, Poindexter. We need ACTION!"
Direct quote from the same episode. - dayoldblues, on 10/29/2009, -3/+18GLIVEN!
- ColdFireArow, on 10/29/2009, -5/+20Applying l'Hopitals rule we can assert that the lim P->0 of P/P is 1. Therefore, N = 1 as P approaches 0.
- longbow486, on 10/29/2009, -1/+16Lovejoy: Homer do you see a light?
Homer: yes..
Lovejoy: Walk into the light my son...
*Homer yells in pain* - stuwanker, on 10/29/2009, -1/+14You got it backwards: P is inside of NP.
- MartiniD, on 10/29/2009, -0/+13You sir, are an idiot.
Your personal failure to understand the significance of this equation does not diminish its importance.
And when was the last time you heard of a mathematician curing cancer? -
Show 51 - 100 of 242 discussions
© Digg Inc. 2009
— Content created and posted by Digg users is