Several points on the question of whether the proof is likely to be correct:
* As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.)
* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)
* On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag.
* Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004.
* On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago.
* It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry.
* This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)
* If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier.
* Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning.
* If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking.
Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.
* If the statistical physics method used here is powerful
enough to resolve P != NP, then there's a good chance it
is powerful enough to have led to many smaller results
before the author was able to nail the big one. It's a
little weird we haven't heard anything about that earlier.
Well, Wiles didn't publish intermediate results either, partly because someone might have beat him to the final result with those intermediate results. It would also give away what he was working on. Deolalikar was aiming for the grand prize as well, so skipping the publishing of intermediate results doesn't seem strange to me.
Though I was just reading the synopsis, and the statistical physics part seems to be proven: "The 1RSB ansatz of statistical mechanics says that the space of solutions of random k-SAT shatters into exponentially many clusters of solutions when the clause density is sufficiently high. This phase is called 1dRSB (1- Step Dynamic Replica Symmetry Breaking) and was conjectured by physicists as part of the 1RSB ansatz. It has since been rigorously proved for high values of k. It demonstrates the properties of high correlation between large sets of variables that we will need."
Another thing. It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". (See http://portal.acm.org/citation.cfm?id=1490272&dl=GUIDE&#... and its references for what this means.) The paper doesn't directly address how it avoids these barriers. It does mention the first two barriers in passing. Maybe the answer is obvious to anyone who could read this paper.
Thanks. I think you nailed just about every one of my concerns about this paper. I've only read the introduction, but if the rest of the paper can deliver what the first 16 pages promise, it looks like a winner to me. I suspect that if there's some problem hidden somewhere, it's a case of showing that some property or another of k-SAT holds almost always in the limit, but not being able to show that any specific instance of k-SAT has that property. And, if that's the case, it's probably a symptom of relying on one of those physics "theorems" you've mentioned. Color me cautiously optimistic, here.
Regarding your next to last point, it seems like there has been some prior work involving statistical physics techniques in computational complexity theory; see e.g., http://cdsagenda5.ictp.it/full_display.php?ida=a01155.
I'm not sure if it is or isn't weird that he hasn't published on complexity theory. I recall Gasarch publishing a poll in SIGACT where a handful of the researchers polled claimed that it'll be resolved by someone outside of the field.
Regardless, from reading the synopsis of the proof, I'm skeptical to the point of disinterest.
The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail:
Date: Fri, 6 Aug 2010 21:28:39 +0000
Subject: Proof announcement: P is not equal to NP
Dear Fellow Researchers,
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
Comments and suggestions for improvements to the paper are highly welcomed.
Sincerely,
Vinay Deolalikar
Principal Research Scientist
HP Labs
Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct:
I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof):
"The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound."
How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?
How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?
Let's talk math: In some very formal, reductionist sense, what we're doing when we do math is to start with a set of axioms, operate on them using a fairly small set of logical rules, and arrive at theorems that seem interesting.
If we do this very carefully -- much more carefully than a human would ever normally do, showing 100% of our work -- it's trivial to check such a proof automatically. You just look at each step, and verify that that step follows from the axioms + logical rules you're using + previous steps. This checking is clearly (handwave) polynomial: at worst, at each step N, you have to examine every axiom, every logical rule, and each prior step to make sure that step N+1 is legal.
So proof checking is in P.
Let's say I have a set of axioms, and a logic, and I want to know whether a theorem T is true given that system. One strategy I could use is to decide to only consider proofs of length less than N, and generate every legal theorem that I can reach in fewer than N logical steps. When I'm done, I check my list of proven theorems and see if any of them match T. Since I can always my answer in polynomial time, I know this is in NP.
The try-everything-possible algorithm has the downside of being a bit exponential (since we expect N to be very (very!) large for any interesting theorem) and so also a bit useless.
But what if a P=NP proof can provide guidance on how we should combine our axioms in order to reach theorem T? We suddenly have not a proof-checker, but a proof-generator! Anything that we can state in a formal language, we can simply ask the prover to prove -- it will either give a proof, or say that a proof of size < N doesn't exist. (That wouldn't be a disproof, and it's a Goedel/halting problem kind of argument that we may never really know how large N needs to be.)
Finding new proofs is a large part of what's considered creative in mathematics. It's hard to over-state how math might change with a tool like that available. The field has seen any number of revolutions before -- e.g., the effort of hundreds who worked on the algebraic roots of polynomials pretty much only survives in homework exercises nowadays -- but automating proofs would be Big.
(Finding interesting conjectures is valuable, too, but I doubt Erdos would be nearly as famous if he'd only posed his questions without his resume of theorems behind them.)
What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated.
You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack.
I believe the intent regarding human creativity is that humans often end up with a practical need to deal with some real-world instance of a size-able NP-complete problem. We don't know any way to efficiently find the optimal solution so we creatively deal with what we can figure out (the traveling salesman's optimization problem, placed into the real world, might count). Are our creative guessworks and heuristic discoveries essential? Or can automation based on P == NP eliminate the need for them - and do better than we do on these problems.
I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good.
If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.
In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"?
Scott Aaronson:
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...
The general feeling is that creativity is hard, and even exponentially hard. When people try to do things creatively they feel like they aren't doing that much better than trying all possibilities and rejecting the ones that don't work.
If someone proved P=NP then unless we're mistaken about how hard we have to work to think creatively, it's likely that computers will end up being better than us at it, using this algorithm that I suspect would be difficult to backport to our brains. :)
Then again, it's possible that skilled practitioners of any creative field have stumbled across this polynomial time algorithm and don't know it, but that seems unlikely.
In regards to mathematics, creativity is displayed foremost in finding connections between different notions and finding logical arguments to support a claim. Mathematical discovery is not in the claim, but in the construction of the proof of the claim.
Mathematical statements are generally easy to state. If P=NP were true, then a valid proof could automatically and efficiently discovered. This would be a kind of creativity automated by technology.
AFAIK the thinking is that if P=NP then we might be able to automate the creation of theorems because we'd be able to take a problem who's solution is known to be quickly verifiable and because we know it's therefore quickly solvable we might be able to automatically develop the theorem that solves it. So his proof suggests that human creativity can't be automated.
While I agree P != NP doesn't say anything about human creativity, but the reason it can't be automated is, I think, different: creativity is closely tied to libido and biological evolution, which in turn can't be simulated in machines in full.
Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS.
Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon before Vinay has a Wikipedia entry? For those who are qualified to evaluate this, I suspect a consensus as to validity will develop within weeks if not days. If thumbs up, he must be worthy of one of the outstanding large-cash-value math prizes. Perhaps even the Nobel?
Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.
"Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "
While the author of this paper does not appear to be a crank, nowhere in the entire paper does it discuss why the fundamental barriers of naturalization, algebrization, and relativization don't apply to the work, making it seem unlikely that those barriers have actually been overcome.
From what little I understand, those barriers prevent only certain proof strategies from working. So for instance, the Razborov-Rudich barrier concerns a class of combinatorial proofs (the so-called natural proofs); this paper uses two techniques - statistical mechanics and model theory - which I gather are out of the province of RR.
I'd like to say congratulations to Vinay Deolalikar for getting to this point and putting the paper out there. As randomwalker and others have said, this appears to at least be a legitimate attempt. It must take some seriously thick skin to work on a paper that a) is in an area so full of failed attempts and error filled proofs; and b) that EVERYONE is going to read and try to tear apart.
Looking at his page at HP Research, he has several other publications in legitimate areas, and seems to be a well qualified researcher.
He may be wrong in this paper, but there's no reason to suspect its a hoax or that he's some kind of kook (as many other comments have sort of implied).
a) Complicated academic proofs take (and should take) months if not years to verify, and will only be "front-page news" after verification. This is hardly the first unverified proof of the [edit: possible (in)]equality of P and NP.
b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies.
We have for some time thought that P≠NP, but boy do people like those unicorns and fairies.
Well, assuming this proof holds up (and there are already links in the comments to other proofs that P != NP) they have proven what most people already assume, that the two are not equivalent. The consequences of P != NP are mostly just that people can stop spending time looking for ways for P to equal NP. Which is valuable, but doesn't have much "real-world practical usage"
Emphasizing the "assuming this isn't a hoax" part, even if it is correct, I don't think it is a life-changing deal.
Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything.
I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.
I think that whether P is NP or not could turn out to be undecidable and in fact one could add either equality or inequality as an independent axiom. The theory of computational complexity is about asymptotic results as the size of the instances goes to infinity and involves `there exists` statements whose meaning when applied to infinite sets is typically ambiguous. For instance, it turned out to be a matter of choice whether or not you want the set of all subsets of real numbers between zero and one to equal or to be strictly larger than the set of so called measurable sets. And whether or not a set is measurable can be characterized in a very concrete way about the possibility of approximating it by unions of intervals. So the question of whether or not there exist non measurable sets turned out to depend on `what you mean by set`in a way which people hadn´t thought about before. I suspect the question whether or not P is NP will depend on what we mean by P and NP in ways which so far no one thought about.
I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.
Because it hasn't undergone the proper level of review in order to be published in one. As it stands, there is no reason to take it seriously until it has been. There have been several posts of such papers here before, and I would highly advise the level of skepticism expressed by a fellow HNer with submissions like this c.f. : http://news.ycombinator.com/item?id=893877
[+] [-] randomwalker|15 years ago|reply
* As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.)
* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)
* While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347295), this isn't one of them. The author is a legit computer scientist: http://www.hpl.hp.com/personal/Vinay_Deolalikar/
* On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag.
* Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004.
* On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago.
* It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry.
* This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)
* If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier.
* Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning.
* If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking.
Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.
[+] [-] Confusion|15 years ago|reply
[+] [-] miloshh|15 years ago|reply
Though I was just reading the synopsis, and the statistical physics part seems to be proven: "The 1RSB ansatz of statistical mechanics says that the space of solutions of random k-SAT shatters into exponentially many clusters of solutions when the clause density is sufficiently high. This phase is called 1dRSB (1- Step Dynamic Replica Symmetry Breaking) and was conjectured by physicists as part of the 1RSB ansatz. It has since been rigorously proved for high values of k. It demonstrates the properties of high correlation between large sets of variables that we will need."
I did not dig into the references yet, though.
[+] [-] bdr|15 years ago|reply
[+] [-] pmiller2|15 years ago|reply
[+] [-] zulfikar_ramzan|15 years ago|reply
[+] [-] zulfikar_ramzan|15 years ago|reply
[+] [-] Q6T46nT668w6i3m|15 years ago|reply
Regardless, from reading the synopsis of the proof, I'm skeptical to the point of disinterest.
(I apologize for not providing a link -- but the only URL I was able to find from Google: http://www.cs.umd.edu/~gasarch/papers/poll.pdf is broken.)
[+] [-] zacs|15 years ago|reply
Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP
Dear Fellow Researchers,
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
Comments and suggestions for improvements to the paper are highly welcomed.
Sincerely,
Vinay Deolalikar Principal Research Scientist HP Labs
http://www.hpl.hp.com/personal/Vinay_Deolalikar/
[+] [-] tzs|15 years ago|reply
There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.
[+] [-] Eliezer|15 years ago|reply
http://scottaaronson.com/blog/?p=456
[+] [-] lkozma|15 years ago|reply
"The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound."
How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?
[+] [-] jeffcoat|15 years ago|reply
Let's talk math: In some very formal, reductionist sense, what we're doing when we do math is to start with a set of axioms, operate on them using a fairly small set of logical rules, and arrive at theorems that seem interesting.
If we do this very carefully -- much more carefully than a human would ever normally do, showing 100% of our work -- it's trivial to check such a proof automatically. You just look at each step, and verify that that step follows from the axioms + logical rules you're using + previous steps. This checking is clearly (handwave) polynomial: at worst, at each step N, you have to examine every axiom, every logical rule, and each prior step to make sure that step N+1 is legal.
So proof checking is in P.
Let's say I have a set of axioms, and a logic, and I want to know whether a theorem T is true given that system. One strategy I could use is to decide to only consider proofs of length less than N, and generate every legal theorem that I can reach in fewer than N logical steps. When I'm done, I check my list of proven theorems and see if any of them match T. Since I can always my answer in polynomial time, I know this is in NP.
The try-everything-possible algorithm has the downside of being a bit exponential (since we expect N to be very (very!) large for any interesting theorem) and so also a bit useless.
But what if a P=NP proof can provide guidance on how we should combine our axioms in order to reach theorem T? We suddenly have not a proof-checker, but a proof-generator! Anything that we can state in a formal language, we can simply ask the prover to prove -- it will either give a proof, or say that a proof of size < N doesn't exist. (That wouldn't be a disproof, and it's a Goedel/halting problem kind of argument that we may never really know how large N needs to be.)
Finding new proofs is a large part of what's considered creative in mathematics. It's hard to over-state how math might change with a tool like that available. The field has seen any number of revolutions before -- e.g., the effort of hundreds who worked on the algebraic roots of polynomials pretty much only survives in homework exercises nowadays -- but automating proofs would be Big.
(Finding interesting conjectures is valuable, too, but I doubt Erdos would be nearly as famous if he'd only posed his questions without his resume of theorems behind them.)
[+] [-] dasht|15 years ago|reply
What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated.
You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack.
I believe the intent regarding human creativity is that humans often end up with a practical need to deal with some real-world instance of a size-able NP-complete problem. We don't know any way to efficiently find the optimal solution so we creatively deal with what we can figure out (the traveling salesman's optimization problem, placed into the real world, might count). Are our creative guessworks and heuristic discoveries essential? Or can automation based on P == NP eliminate the need for them - and do better than we do on these problems.
[+] [-] jacoblyles|15 years ago|reply
If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.
[+] [-] astrofinch|15 years ago|reply
In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"?
Scott Aaronson:
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...
[+] [-] lunchbox|15 years ago|reply
[+] [-] moultano|15 years ago|reply
If someone proved P=NP then unless we're mistaken about how hard we have to work to think creatively, it's likely that computers will end up being better than us at it, using this algorithm that I suspect would be difficult to backport to our brains. :)
Then again, it's possible that skilled practitioners of any creative field have stumbled across this polynomial time algorithm and don't know it, but that seems unlikely.
[+] [-] brg|15 years ago|reply
Mathematical statements are generally easy to state. If P=NP were true, then a valid proof could automatically and efficiently discovered. This would be a kind of creativity automated by technology.
[+] [-] mmaunder|15 years ago|reply
[+] [-] spektom|15 years ago|reply
[+] [-] JabavuAdams|15 years ago|reply
Perhaps it's a legacy from the idea of a life-force or vis viva.
[+] [-] mojuba|15 years ago|reply
[+] [-] johnswamps|15 years ago|reply
[+] [-] jackfoxy|15 years ago|reply
Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon before Vinay has a Wikipedia entry? For those who are qualified to evaluate this, I suspect a consensus as to validity will develop within weeks if not days. If thumbs up, he must be worthy of one of the outstanding large-cash-value math prizes. Perhaps even the Nobel?
[+] [-] sidww2|15 years ago|reply
Edit: Also the Goedel prize
[+] [-] mzl|15 years ago|reply
[+] [-] agravier|15 years ago|reply
[+] [-] sidww2|15 years ago|reply
"Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "
[+] [-] tshtf|15 years ago|reply
http://www.hpl.hp.com/personal/Vinay_Deolalikar/
[+] [-] mmaunder|15 years ago|reply
[+] [-] bramcohen|15 years ago|reply
[+] [-] long|15 years ago|reply
[+] [-] simonista|15 years ago|reply
[+] [-] vide0star|15 years ago|reply
[+] [-] dalton|15 years ago|reply
Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal.
As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof.
Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem
[edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.
[+] [-] tzs|15 years ago|reply
Looking at his page at HP Research, he has several other publications in legitimate areas, and seems to be a well qualified researcher.
He may be wrong in this paper, but there's no reason to suspect its a hoax or that he's some kind of kook (as many other comments have sort of implied).
[+] [-] ynniv|15 years ago|reply
b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies.
We have for some time thought that P≠NP, but boy do people like those unicorns and fairies.
[+] [-] macrael|15 years ago|reply
[+] [-] mjschultz|15 years ago|reply
Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything.
I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.
[+] [-] xtacy|15 years ago|reply
[+] [-] uptown|15 years ago|reply
http://en.wikipedia.or/wiki/P_versus_NP_problem
http://www.claymath.org/millennium/P_vs_NP/
[+] [-] benhalllondon|15 years ago|reply
[+] [-] gill1109|15 years ago|reply
[+] [-] jarsj|15 years ago|reply
[+] [-] noahlt|15 years ago|reply
[+] [-] aswanson|15 years ago|reply
[+] [-] unknown|15 years ago|reply
[deleted]
[+] [-] unknown|15 years ago|reply
[deleted]
[+] [-] akshayubhat|15 years ago|reply
[deleted]