P != np
This story just broke on slashdot. Apparently a researcher at HP has submitted a paper for peer review that has claimed proof that P != NP.
A preliminary non-peer-reviewed paper is available for download at the researcher's site:
hp labs : research : SIMPL : people
It will be interesting if his proof is found to be valid. For me: I tried to sieve through the 100 page paper, but couldn't get through the abstract :)
I'm not getting my hopes up yet. I mean; hundreds of papers, if not more, have been submitted as proof on this. Just none of them ever happened to be correct.
This is a serious attempt. Several experts have expressed their enthusiasm. A Proof That P Is Not Equal To NP?
Even if the proof contains a mistake, there is probably still new ideas left in the paper. It might take months or a year to verify, though.
I'm a little confused by this issue - is there a significant group of people who believe P == NP, or is it just that we think P != NP and it's very hard to prove?
I've seen a poll about this a long time ago. Most respectable people (like professors or something) thought P!=NP, though a surprising lot of them thought that P=NP was quite likely as well.
Originally Posted by sean
But, yeah, most well informed think P != NP.
I had always been holding out for a P = NP proof, because I think it'd be much more cool. I guess this will have to suffice. :)
Damn! I had all my money on P = NP :(