Submitted by
Users who Dugg This
Leena Helttula
11667 Followers
Lior Galanti
19 Followers
Lior Galanti
19 Followers
Financial Highway
1566 Followers
Financial Highway
1566 Followers
macbookformeAug 9, 2010
Wow, finally!
liorgalantiAug 9, 2010
i wouldn't call it finally... we need some confirmations first.
But its good to see the scientific community has not completely gave up trying.
Closed AccountAug 10, 2010
that would be interesting. We'd probably solve a number equal to the new ones created though ;)
impedance101Aug 10, 2010
Guess ill never be able to say md5 FAIL
peeequalsnpAug 10, 2010
.... -_- s***
hordespawnAug 10, 2010
http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
ikorkyiAug 10, 2010
N=0
runner108Aug 10, 2010
Congratulations to Vinay Deolalikar for contributing something great to the world. Hopefully it turns out to be correct and if it does not, hopefully the flaws are found to be correctable.
On a side note, I just took a look at the paper.. is it standard to refer to yourself in first person plural in proofs? Or did he work with someone on this?
gcnaddictAug 10, 2010
I'm assuming he worked with others, but even if he didn't, it's psychologically better to say "we" as it implies both a team effort and a degree of selflessness in trying to solve the problem.
Saying "I" all the time basically implies "I'm smarter than you, so piss off." Therefore, those who don't actually want to sound like douchebags tend to write proofs matter-of-factly with no first person references if he/she is the only one who did the proof.
landslydeAug 10, 2010
Writing a technical paper or proof you never refer to yourself with "I."
runner108Aug 10, 2010
Thanks didn't know that.
ayeroxorAug 10, 2010
Heck, that's the standard for all professional documents. For instance, if a journalist ever writes about himself, he should write something akin to, "This author has witnessed no such altercations."
godstwinAug 10, 2010
Step 2: ???????
Step 3. PROFIT!!!!
timthetaxmanAug 10, 2010
Step 2: Collect one million dollar reward for solving a Millennium Prize Problem
http://en.wikipedia.org/wiki/Millennium_Prize_Problems
luckyirishlocksAug 10, 2010
I really f**king hope that doesn't mean I have to take that algorithms course again...
newerakbAug 9, 2010
Congrats if he's right, but I hope he's wrong. The future would be a lot more exciting if P = NP.
trevorbradleyAug 9, 2010
Either that or a reality where P=NP was true have been significantly less interesting from the start.
trevorbradleyAug 10, 2010
"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."
— Scott Aaronson, MIT
(Scott thinks this version of the proof is probably incorrect, and appears willing to bet his house on the matter)
tblaskoAug 9, 2010
Can you explain for a maths layman such as myself?
trevorbradleyAug 10, 2010
OK, as briefly as I can make it...
Some math problems (NP) are very hard (factoring large numbers to component primes, determining the best route for a UPS truck to drive on) and take a lot of computing time to work out. The difficulty factoring large numbers is used in cryptography, under the assumption that because it's so hard to do, you can easy encode secrets using these large numbers. The UPS truck problem may seem simple, but as you add more and more routes the amount of computer time required to compute the best route grows very very quickly. If you had even just tens of thousands of points it might take until the end of the universe to compute the very best route. Once you've found the solution to an NP problem, it's very easy to check if you're correct.
P problems are easy to solve and easy to verify. If NP was really P, then these really hard problems would be easy to solve, decades of computer cryptography would be thrown out the window, and computers would be able to determine things much easier and more quickly than anyone could imagine today.
This proof is that P!=NP, which means that hard problems are indeed hard, and there's no shortcut around crunching through all the numbers or giving up and making a compromise.
The fascinating thing about the P=NP? question is that it's been so difficult to solve. At first glance you'd think it would be relatively easy.
asherpAug 10, 2010
Thanks Trevor, the internet owes you one!
tblaskoAug 10, 2010
Cheers - now I can regurgitate your main points in an upcoming conversation to make myself sound smarter than I am!
throwdiniAug 10, 2010
Thanks for explaining that Trevor. You could have called my mom a slut in that post and I would have still dug you up for taking the time to explain that.
trevorbradleyAug 10, 2010
@throwdini: I tried very hard to avoid a follow up joke, saying your mother was P instead of NP, but here I am making it.
Glad I could help. Someone with more maths knowledge will come along soon and say my explanation isn't exactly correct and hopefully give a better explanation. (For example, I believe the NP UPS problem is more "Find a route that takes less than N minutes" rather than finding the shortest route)
thcobbsAug 10, 2010
Effectively, the UPS problem is the same as the Traveling Salesman problem.
bartledooAug 10, 2010
Valiant attempt Trevor, although not completely accurate.
The traveling salesman problem is indeed NP-complete, but integer factorization is not known to be (although unlikely, it is possible that it is polynomial in time but we just don't know the algorithm yet).
Also, P problems aren't necessarily "easy". A P problem can be solved in polynomial time, but if the order of complexity is say O(n^100,000), for all practical purposes it's not scalable and may actually be "worse" than exponential until n is very large.
Just nitpicky things though, you are essentially correct. Props for educating the masses.
P =/= NP has more or less been assumed for years by most computer scientists, so this is exciting (if the proof turns out to be correct) but not surprising. Time to stop chasing magical leprechaun reduction algorithms and keep working on approximation algorithms for "hard" problems.
slipperyottterAug 10, 2010
is it still too late to call throwdini's mom a slut?
D:
bartledooAug 10, 2010
Further clarification: all P problems are in fact NP problems (P is a subset of NP).
The P ?= NP question is if all NP problems are actually P.
NP means that the solution can be *verified* efficiently (in polynomial time).
P means that the solution can be *computed* efficiently.
kamtsaAug 10, 2010
Further clarification, not all NP problems are 'hard to solve'. For example, finding the first number in an ordered list of N number is an NP problem and it can be solved in less than 3.1415ns regardless of the size of N.
trizzleatlAug 10, 2010
Seriously? All this time and effort just to prove that some math is hard? I proved that back in school.
Closed AccountAug 10, 2010
If the future is quantum computing it may not matter.
path411Aug 10, 2010
Isn't the highest calculation by a quantum computer something stupid like 3x3?
buckrogers1965Aug 10, 2010
@path
The NSA has had 128 bit quantum computers for over a decade now.
orky7Aug 9, 2010
it is not published he e-mailed it to peer for review so there is still a Big Question mark involve, just wait do not get too exited, if it is true then good for cryptologist...
thatinternetguyAug 10, 2010
Unless modulus is actually a P problem.
wordsncollisionAug 9, 2010
VD > P≠NP = !!!
radicaldementiaAug 9, 2010
The proof seems to use results from model theory, a branch of mathematical logic that is a mixture of abstract algebra and first-order logic. Unfortunately the depth and scope of the concepts used are beyond what I know, but at the very least this does seem like a serious proof by a guy who knows what he's talking about, of course that doesn't mean it's correct.
Also, for those who don't know, in simplest terms the statement "P=NP" means that computing problems whose answers are "easy" to verify (NP) are also "easy" to solve (P). For example, factoring an integer into it's prime factors (ie 12 = 2 x 2 x 3) is hard (try doing it for, say 520502842575465294824), but it's easy to take a suggested list of factors and see if they multiply to that number, so prime factorization is NP, but as best we know it is not P. There are many other problems in the same boat.
The most relevant practical consequence is that all modern cyber-security relies on prime factorization being NP. If it was proven that P=NP, it would mean that there is a way to easily factor large numbers and thus quickly circumvent all encryption methods currently used (though it wouldn't necessarily tell us "how" to do this). However this proof is that P≠NP, so if it's correct it means we don't have to worry about that.
executexAug 9, 2010
I wish my computer engineering professors knew how to explain it like this.
ubernickAug 9, 2010
Ours explained it to us in Tetris:
http://www.colinfahey.com/tetris/tetris_en.html
darklich14Aug 9, 2010
How would you prove P=NP but not have some proof to map a polynomial algorithm into a nonpolynomial algorithm? I guess you could hypothetically do it, but all algorithms of similar complexity map into one another, so all you need is one. That one can be mapped into another, and another, and reduced into direct mapping, etc.
kimballjAug 10, 2010
NP = "nondeterministic polynomial"
Not a dis, just a clarification.
hordespawnAug 10, 2010
It's called a non-constructive proof. Assuming Deolalikar's proof is incorrect, it might be possible to prove that P=NP but not provide a method for actually solving some x \in NP in polynomial time. Such a result would be interesting, but not really change things radically, at least not right away.
Closed AccountAug 10, 2010
just to clarify on what hordespawn's talking about, because i'm rather bored and need to kill some time, think about this theorem: there exist irrational numbers J and K such that J^K is rational.
the proof goes: let J and K = sqrt(2). if J^K is rational then the theorem is proven. if not, J^K is irrational, so let R=J^K. then R^J = sqrt(2)^sqrt(2)^sqrt(2) = sqrt(2)^2 = 2 which is rational and the theorem is proven.
this is a perfectly valid proof that doesn't actually say whether sqrt(2)^sqrt(2) is rational or not (by other theorems, it's not, but that is irrelevant to the validity of the proof above).
as such, in the case you're talking about, the existence of a mapping M could be assumed to map an NPC problem to a P problem, and if you could show that assuming that M doesn't, yet a known alteration of it does, then you've proven the problem without saying specifically whether or not M maps NPC to P or not.
though it should be mentioned that if M can be shown to be by alteration to bring NPC to P, there likely exists a manner to show whether or not M itself does or does not. like in the example above, sqrt(2)^sqrt(2) is irrational by a theorem that states given J and K roots of a polynomial, if J is not 0 or 1 and K is irrational J^K is transcendental (and thus irrational).
Closed AccountAug 9, 2010
That's an accurate description, but Prime Factorization isn't necessarily in NP.
http://en.wikipedia.org/wiki/Prime_factorization#Difficulty_and_complexity
A better example would be something like TSP or Hamiltonian cycles.
ubernickAug 10, 2010
From your link: "It is known to be in both NP and co-NP."
You're thinking NP Complete, which is a more-strictly defined set of problems within NP. It's been suspected that P != NPC would be solved first, but the most interesting results coming from P != NP would probably be related to factoring.Comment is buried, click here to see the rest.
Closed AccountAug 10, 2010
I didn't say it wasn't in NP or co-NP. I said it was possible that it was in P.
So no, I'm not thinking NP-Complete.
ubernickAug 9, 2010
One cool thing about the researcher is that he went to grad school at the same place an inventor of RSA (the A) taught logic, computation, and cryptography. The professor, an interesting guy who won the Turing award and invented DNA computers, would talk about NP during class like it was the holy grail of mathematics. This is on par with the Riemann Hypothesis in its significance, and will be more famous than the solving of Fermat's Last Theorem.
alwaysskepticalAug 9, 2010
Please correct me if I'm wrong, but I don't believe prime factorization is an NP problem; prime factorization used in cryptography is based on the DLP and Fermat's Little Theorem such that there is no known efficient way to accomplish this, while NP refers to nondeterministic polynomial time complexity theory, key word being "nondeterministic" (colloquially, no known way to solve the problem without attempting all combinations of solutions)
I believe prime factorization is deterministic with a finite set of solutions (a finitely large number with two large prime factors) so it could be solved in polynomial time (albeit for a very large polynomial), but is not a NP problem.Comment is buried, click here to see the rest.
Closed AccountAug 10, 2010
I don't think you understand exactly. There are an exponential number of possible combinations of factors (even going up to only the square root of n) for some integer. This means that it's potentially not in P. The understanding, though, is that it may not be in NP, so you may be right.
Simply because there are a finitely large number of solutions doesn't mean you're not in NP. There potential answer space for Hamiltonian Cycle is finite, but exponential, and there is no known efficient way to solve it.
Closed AccountAug 10, 2010
i think you're both confused. integer factorization IS an NP problem. it's unknown whether it's in P or NP-C or in neither. P is a subset of NP, all P problems are NP problems. there is no known reduction from an NP-C problem to a P problem. so there is no proof that P is a strict subset (pending review of the proof in the article).
@AlwaysSkeptical
""nondeterministic" (colloquially, no known way to solve the problem without attempting all combinations of solutions)"
no. it does not mean that at all. nondeterministic in this situation means it requires a nondeterministic turing machine to solve the decision problem with a "yes" in polynomial time. P requires deterministic turing machines to solve in polynomial time. deterministic turing machines are a special case of nondeterministic turing machines.
Closed AccountAug 10, 2010
I'm not confused, but my fingers were last night. :P
You are, of course, correct. I used NP here to simply mean "The set of things in NP which we consider to not be in P, including NP-Complete and other NP problems for which we don't have a polynomial deterministic Turing time algorithm."
Closed AccountAug 9, 2010
I remember when Digg had lots more comments like these. I miss those days.
farmy87Aug 10, 2010
To touch on the "so we don't have to worry about that" part at the end of your post.. that is a HUGE logical fallacy. P is known to be a subset of NP. Just because it's proven that P≠NP does NOT mean that for any x∈NP, x∉P, which is what your statement was implying.
newerakbAug 10, 2010
Was about to say the same thing. It's clear to me that radicaldementia is light years ahead of me in mathematics, but it is a bit of a fallacy to say that this proof has any relevance to prime factorization.
Even if the proof is correct, that doesn't preclude there from being an easy solution to prime factorization.
kimbomittAug 10, 2010
I think this is the first time I've seen the ∈ (or ∉) symbol in a Digg comment.
radicaldementiaAug 10, 2010
@farmy87, my statement was ambiguous and you are quite correct. I did not mean to say P≠NP --> (x∈NP --> x∉P), which is obviously a false statement, but rather I was simply saying that proving P≠NP would (obviously) mean that we don't have to worry about P=NP being true.
Most people believe that prime factorization is not in P, since many have tried and failed to find such an algorithm. Since proving P=NP is by some considered the closest method to proving factorization in P (or at least the most widely known), proving its negation would be a strike against the hypothesis. Of course one day a proof via another path may yet come along, but perhaps it would have been better if I said "we don't have to worry about that immediately", since I think any other proof of prime factorization in P is a long ways off.
ih8ualotAug 10, 2010
2x2x2x631x103110705739989163
http://www.wolframalpha.com/input/?i=prime+factors+of+520502842575465294824
kimbomittAug 10, 2010
hmm...I figured out 8 and 631, my wimpy little computer was still trying to figure out factors of 103110705739989163. Probably gonna take awhile, I kind of don't want to interrupt just to see how long it'll take.
mxm111Aug 10, 2010
@kimbomitt
Strange, my computer factors that number nearly instantaneous in Mathematica, well below 0.01s (Mathematica itself times the computation at 0s, and it should be accurate with at least 0.001s). And my computer is nothing special, it has Core 2 duo at 3MHz
kimbomittAug 10, 2010
@MxM111
Yeah, I should add that rather than use existing software like Mathematica I wrote a little piece of code myself to use, and i just wrote it as fast as possible instead of trying to make it any good...and it was in Java...so that was probably the real reason.
cantholditdownAug 10, 2010
Thanks. Never knew this was how cryptography worked.
runner108Aug 10, 2010
I am only new to this problem so I do not grasp the implications of it completely. Let's say that the proof is said to be valid so P !=NP. Does that necessitate that there are at least some problems that can't be solved in polynomial time? I'll give an analogy.. it was difficult for humans to learn to create a flying machine. Once gravity and aerodynamics were better understood, we have gotten a lot better at doing it. Is it possible that some problems that are considered 'hard' to solve could be made to be solved within polynomial time with some unexpected leap in understanding in mathematics or the like? Or does this flat out rule out those possibilities?
hordespawnAug 10, 2010
Well, you're being a little loose with definitions. We knew that there were some problems that couldn't be solved in polynomial time; There are even problems that are unsolvable. What the P != NP question was asking was if a problem in NP could be solved in polynomial time. If the proposed proof is valid, then we cannot solve problems in NP in polynomial time, no matter how much our technology or knowledge grows.
runner108Aug 10, 2010
Certainly I was due to my lack of understanding but I appreciate that you understand and answered the question anyways.
limeparrotAug 10, 2010
Far out. Mind blown just before I go to sleep.
fugeelamaAug 10, 2010
Isn't this the basis for the algorithm used by the black box in the movie Sneakers?
diggorelseAug 9, 2010
Wow, some exciting news for a change! Yeah, I like the pics of [insert babe here], but this is really quite interesting!
mikedothAug 9, 2010
P != NP
uv0001Aug 9, 2010
If this is true, it's a history making proof for Computer Science.
gcnaddictAug 10, 2010
Nah. If P=NP were proven, *that* would be a history-making proof. P≠NP is boring and changes nothing other than saving a few people any effort spent trying to find shortcuts to ass-kicking problems.
bartledooAug 10, 2010
Don't be ridiculous. It is certainly a history-making proof. It's one of the top Millennium Problems for goodness sake. Far more important than say Fermat's Last Theorem.
While it certainly isn't shocking and game-changing like it would be if P = NP, it is still a big deal.
arkansawAug 10, 2010
Nah, it is just CS masturbation without serious ramifications
bizkit00Aug 9, 2010
P≠NP for all values of N≠1
bartledooAug 10, 2010
Unless P = 0.
You must not be very good at remembering to check special cases.
yodaofdarknessAug 9, 2010
<?php
define('P', ord('P'));
define('N', ord('N'));
echo (P == NP) ? 'P = NP :)' : 'P != NP :(';
?>
Comment is buried, click here to see the rest.
scuba7183Aug 10, 2010
awww, that's cute
wigen1jtAug 9, 2010
In Soviet Russia, NP=P.
milfordcubicleAug 10, 2010
surprised it took this long to find its way into the thread...
fifteenstepperAug 9, 2010
Could turn into quite a windfall for him.
http://en.wikipedia.org/wiki/Millennium_problems
cyclozionAug 9, 2010
Breaking news comes from Wikipedia now?
redhookesbAug 10, 2010
Congrats, wikipedia!
Closed AccountAug 10, 2010
[citation needed]
cfuseAug 10, 2010
Beats TMZ
ubernickAug 9, 2010
He could win the Millennium prize! But as a USC grad, the NCAA would probably make him give it back.
rainemakerAug 10, 2010
That's what Vinay gets for talking to scouts.
wateryouthAug 10, 2010
Wow, a mixture of sports and mathematics humor, what a broad spectrum audience this should have.
debatorAug 10, 2010
as an IIT grad he probably already owns the world
dmarantAug 11, 2010
Actually, if he didn't win it, USC would just say he did, even if they agreed that only the winner gets the prize (see: 2003 football).
dikkyAug 9, 2010
we should hope not because the interweb without encryption would suck
manbeefAug 10, 2010
I think you've got it backwards.
genadyAug 10, 2010
Seatec Astronomy
friedjellyfishAug 9, 2010
I was kinda hoping for some 100 pages of formulas that then resolve to "P ≠ NP" in the last line...
cyclonusripAug 9, 2010
I'm pretty skeptical that this is correct, but if it is this guys name is gonna be showing up in some text books.
danisthAug 9, 2010
Could anyone explain what this means in simple language?
trevorbradleyAug 9, 2010
Short Answer: not really.
sigmaman2Aug 10, 2010
Long answer: Well, based on your question, you probably don't want the long answer, so nevermind.
falserAug 10, 2010
The simplest way to explain it would be show you the mathematical proof.
dikkyAug 10, 2010
when you encrypt something it takes, with modern technology depending on the level of encryption, seconds to billions even trillions of years break. the actual limit on the time it can take to break the encryption approaches infinity as the encryption level goes up.
when you have the correct password it takes a very tiny amount of time to verify it.
if p = np is true, then there is a method out there that is just as fast as finding out the password as it is to verify the password.
wateryouthAug 10, 2010
Now that is a very clear and concise answer.
mkriss5681Aug 10, 2010
Which is terrifying if P=NP were true because it would break most types of encryption.
danisthAug 10, 2010
Ok I looked at a few wikipedia pages and have decided that its way beyond me and my liberal arts credits.
thebay6Aug 10, 2010
Normal Answer: A rough formation of the question is on Wikipedia - Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"? If so, P=NP.
gbladeclAug 10, 2010
Simple Language: Hard problems are actually hard and not secretly easy.
ymegAug 10, 2010
some s**t is easy to figure out and some s**t isn't so easy. Is there a way for the hard s**t to be easy?
staticthunderAug 10, 2010
No, because the hard s**t is actually made of different stuff than the easy s**t. Demonstrating that its ALWAYS made of different stuff than the easy s**t, and there is no magic tool out there that cuts hard s**t like its easy s**t, turns out to be difficult.
newerakbAug 10, 2010
Basically, the guy is saying he's proven that just because you can VERIFY an answer easily doesn't mean you can FIND an answer easily.
So, if I give you 500 integers and ask if their sum is 32,574, you can quickly add them up and verify. However, if I asked you to give me 500 integers whose sum is 32,574, you couldn't solve that as easily. If someone proved that P=NP, then there WOULD be an easy solution for both of those situations.
What this guy claims to have proven seems like common sense, but there wasn't a proof either way, and it would have been earth-shattering to discover that P=NP.
trevorbradleyAug 10, 2010
We have to be careful about our examples here. For example, 32574+499*0 is an easy solution to your question.
I always liked the "filling the college dorm" problem:
http://www.webmasterworld.com/foo/4124058.htm
newerakbAug 10, 2010
thanks Trevor, clearly I didn't put enough thought into my example :)
hopefully I still conveyed the general meaning
bartledooAug 10, 2010
The Knapsack Problem is a great example, but as Trevor points out you didn't quite present it correctly.
A better explanation would be:
Say I give you a collection of 500 different integers and ask if there is a combination of some of them which sums to 32,574. Given a specific combination, it is easy to check if it sums to 32,574 or not, but it is not easy to find a combination that does sum to 32,574 (if it exists) without checking every possibility.
P = NP would imply that there is an efficient algorithm to do so.
danisthAug 10, 2010
I kind of get it now, thanks guys!
brasteinAug 10, 2010
http://simple.wikipedia.org/wiki/P_versus_NP
It's a start. I guess.
rchargelAug 10, 2010
I'll do my best, but I'm no mathematician. Basically there are two basic types of problems in computational logic. Those problems which can be solved in an amount of time that is polynomial* to the size of the input (P), and ones that are not (NP). While the NP problems cannot be solved in polynomial time, both P and NP solutions can be verified in polynomial time. The basic question of P = NP is, is there an equivalent P algorithm for every NP problem. Can we break down NP problems into simple enough steps that they can be solved in polynomial time. My understanding however is that this issue becomes less of a problem with non-deterministic systems. So that quantum computing may make these points irrelevant.
*polynomial time basically means that there is an upper boundary to the number of required calculations that is a polynomial of the input (ie: n^2, where n is the number of bits). Whereas superpolynomial (NP) are not bound by a polynomial of the input (basically this could be exponential time) (eg: 2^n). This means that a problem that takes 2 nanoseconds with 2 values could take 10 years with 1,000 values.
hordespawnAug 10, 2010
Actually, quantum computing does increase computational power, but not enough to make NP-complete problems easy.
http://en.wikipedia.org/wiki/Quantum_computer#Relation_to_computational_complexity_theory
philphanphorevaAug 9, 2010
Vinayy in da house! Kudoes my man kudoes ! And he is rathher cute to boot tehe
slashdotordiggAug 9, 2010
So is it over?
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
I guess you pick your side and prove it right somehow.
dbuckAug 9, 2010
I didn't understand a single word of that.
karlhAug 10, 2010
I understood every single word ... individually.
Closed AccountAug 9, 2010
I KNEW God was real. Thanks for the proof Vinay!
firecellAug 9, 2010
Great news everyone!
kornstalxAug 10, 2010
http://holycrapthatsfunny.com/wp-content/uploads/2009/02/good_news_everyone.jpeg
dutchsaintAug 9, 2010
But what if N=1?
P≠NP
P≠1P
P≠P
HA! There you have it! It's FALSE!
gcnaddictAug 10, 2010
I'm guessing you're kidding, but if you're not, NP is one variable, not two.
dutchsaintAug 10, 2010
Oh, being buried to hell, I see, geez, I hate having to explain jokes: /s, obviously
hordespawnAug 10, 2010
Actually, NP is not a variable; it's a set.
wateryouthAug 10, 2010
I cant believe this dude is getting buried, that was funny.
melikbilgeAug 10, 2010
If you're 10.
wateryouthAug 10, 2010
I'm not ten, i = -1 lol get it?
cyclozionAug 9, 2010
I was told there would be no math.
chris15118Aug 9, 2010
Let us not get carried away. Wait for it to be scrutinized by the world at large.
Anyways, the exciting proof would be if P = NP.
Closed AccountAug 10, 2010
actually if this were to happen, public key cryptography would be greatly compromised.... not broken, but compromised.
Due to the fact that Public and Secret keys have a relationship and that it is unfeasible to find the secret key from the public key's information.
So at least for now, I'm hoping that this is NOT true.
bizkit00Aug 9, 2010
"The story made it to Slashdot on August 8, 2010.[4]"
lol, no wonder it made it to Digg on the 9th!
mhuntAug 10, 2010
Let me guess. It made it to reddit sometime in 2009?
eatingpieAug 10, 2010
Well, don't jump the gun. The wiki page starts with a huge header reading...
"This article is being considered for deletion in accordance with Wikipedia's deletion policy."
Knowing absolutely nothing about the situation, this could be a real proof, a flawed one, or a complete and total hoax. We simply do not know yet.
-Pie
Closed AccountAug 10, 2010
http://en.wikipedia.org/wiki/Wikipedia:Articles_for_deletion/Vinay_Deolalikar
trevorbradleyAug 10, 2010
When Andrew Wiles came up for a proof for Fermat's Last Theorem in 1993, it took 2 years to iron out the bugs and for it to be eventually accepted. (The first version had a critical error that was correctable)
Grigori Perelman's proof of the Poincare conjecture is only understood by a handful of people on the planet. (Grigori is an amazing genius, but an absolute recluse. He turned down his $1,000,000 prize even though he's still living in a tiny apartment with his mom: http://en.wikipedia.org/wiki/Grigori_Perelman)
debatorAug 10, 2010
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
definitely exists. and it's on hp's servers - it's not a hoax, at the least.
trevorbradleyAug 10, 2010
There are some skeptical folks out there about this proof:
"If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000."
http://www.technologyreview.com/blog/post.aspx?bid=349&bpid=25584
newerakbAug 10, 2010
Wow, ballsy move.
wateryouthAug 10, 2010
The funny part is that if they do disprove the proof quickly, it will kinda enforce the idea that P!=NP, as creating the proof in the first part took an astronomical longer time.
bivariateAug 10, 2010
After spending a ton of $$ for advanced Math classes in College where I was told P = NP and now this, P != NP . I did not expect that this theory would be debunked in my lifetime. To make life easier I was told to believe that P = NP and not seek to understand. Now I am interested in the details of this theory.
http://www.mynucleus.org/story/2010/08/08/claimed_proof_that_p__np_Comment is buried, click here to see the rest.
bartledooAug 10, 2010
Seriously? Where did you go to college? Computer Scientists and Mathematicians have long suspected P != NP, just no one had been able to prove it.
Closed AccountAug 10, 2010
maybe he's just confused. P is a subset of NP, but there is another subset of NP called NP-Complete. as it stands, each subset is suspected to be disjoint (no problem from NP-Complete has a known reduction to a problem from P). if this proof is correct than such a reduction does not exist. if P=NP then all NP-Complete problems are P problems. likely they taught you that P ⊆ NP and you are remembering it wrong.
spacemanspiff22Aug 10, 2010
You should ask for your money back. Either they taught you the absolutely opposite of what is commonly believed true, or they sucked at teaching and you didn't really learn much.
joeydaiohAug 10, 2010
Am I supposed to know what this is?
gcnaddictAug 10, 2010
Just know this much:
If P=NP, all hell breaks loose in the computing world.
falserAug 10, 2010
Oh crap, I was so close to proving that P=NP, that means I must have made an error early on.
hereticoftruthAug 10, 2010
When N=1. Beat you to it!
captspauldingAug 10, 2010
<--- failed high school algebra 3 times :(
theabsinthehareAug 10, 2010
I failed it 3 times as well, and then twice in college. Then, I found this:
khanacademy.org
Seriously, I learn more from each video than I ever did during weeks of schooling.
Closed AccountAug 10, 2010
Wow, that website is amazing. I wish I discovered this back in my undergrad days as a CS (math) major. Maybe it'll be useful when I start my MSCSE this Fall. Thanks for the link!
captspauldingAug 10, 2010
Wow, thanks! That site is great.
iamsmoothAug 10, 2010
Yeah, Khan is great. His videos helped me get past first year calculus and linear algebra.
danbarkerAug 10, 2010
Wonder if this guy had any affairs and strange expense reports?
Closed AccountAug 10, 2010
P != NP doesn't mean large number factoring encryption is safe. That is actually a BQP problem, which will easy to solve using Shor's algorithim once we get large scale quantum computing.
bartledooAug 10, 2010
Especially since we don't know for sure that integer factorization ∉ P.
spacemanspiff22Aug 10, 2010
"once we get large scale quantum computing"
I loled.
Closed AccountAug 11, 2010
I hope you're wrong because my research is a proof of concept for scalable quantum computing. I know it's hard from experience, but I don't think it to be so impossible as to be laughable.
funnythatAug 10, 2010
This account has been closed by the user
mydiggloginAug 10, 2010
This is incredible. I thought this kind of research labs in corporations were dead.
sghod1212Aug 10, 2010
He says his work is completely independent of his job at HP.
bartledooAug 10, 2010
He did this in his spare time, not while working for HP.
random12345Aug 10, 2010
Why did the Wikipedia entry get front paged? Wouldn't it have been more logical to front page a news article about this?
shapedyAug 10, 2010
What news organization could possibly cover this? "He showed that one side of the equation has an N on it in addition to the P. That means they're not equal."
faithclubdotnetAug 10, 2010
Most people suspected P!=NP due to the fact no one could solve any of them in P time over the course of several decades.
Closed AccountAug 10, 2010
suspecting something and proving something are two entirely different things. there are examples of conjectures which are true until you get into integers in the hundreds of millions. if you were a mathematician before computers, it would be very easy to "suspect" that a conjecture is true which doesn't show up as false until after 900,000,000 when doing it by hand.
theabsinthehareAug 10, 2010
*P!=NP
beatlemaniac007Aug 10, 2010
Dang Steve Cook will be pleased. He was my prof last semester. He derives s**t on the spot and this proof eluded even him.
autokadAug 10, 2010
Digg referencing Wikipedia articles now? O_O
misteratozAug 10, 2010
The next andrew wiles?
bartledooAug 10, 2010
If the proof is correct, he'll be bigger than Wiles. This is a fundamental problem in computer science and a Millennium Problem, not a relatively insignificant number theory problem.
Closed AccountAug 10, 2010
did you just say that fermat's last theorem is in any way insignificant? i mean, it only remained unproven for 358 years and the proof itself is over a hundred pages long. the theorem only spawned algebraic number theory. PvsNP is minor in comparison (particularly if P!=NP... P=NP would be amazingly counter intuitive and would likely have a far greater effect on the mathematical world than P!=NP).
bartledooAug 10, 2010
The theorem itself isn't terribly significant in itself. The reason it's famous it that it was such a long standing problem, not that it's a profound statement. I'm not trying to downplay Wiles and his huge contribution to mathematics, but the fact that x^n + y^n != z^n for n > 2 really isn't a big deal.
P != NP is not surprising, but it is foundational. There is a reason it is a Millennium Problem along with other profound statements like the Riemann Hypothesis and the (now proven) Poincaré Conjecture.
v3nomAug 10, 2010
I had never heard of this problem prior to seeing this article (though I just declared CS so perhaps I'd be exposed to it soon). Very interesting stuff.
danesisAug 10, 2010
"Party and Play"? I'm there.
bstew22Aug 10, 2010
This account has been closed by the user
kaijunexusAug 10, 2010
Articles like this make me feel stupid, and then I feel sad.
shirukenAug 10, 2010
Link to the manuscript containing the proof: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf
dumptakerAug 10, 2010
Oh, wow! Zzzzzzzzzzzzzzzzzzzzzzzzzz........................
nicko68Aug 10, 2010
Easy.
P = NP iff N = 1.
What's the big deal?
:)
Closed AccountAug 10, 2010
first, more than one other person beside yourself tried this "joke" already in the threat.
second, P = NP iff N = 1 or P = 0.
toffeecAug 10, 2010
Cool. The surprise isn't so much in the result (it would have been truly incredible if P = NP, seeing how much effort has been put in coming up with polynomial time algorithms for NP problems). I actually have a background in mathematical logic and model theory, I'll try to see how far I can get into the proof.