6 ms·
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
by zacs 16y ago
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
http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/
- JeanPierre 16y agoIf this proof is up for review, that would mean there could be errors in it, right?
- zacs 16y agoAs another commenter mentioned, it will likely take months or even years to verify.
- akshayubhat 16y agonot necessarily, PRIMES in P was accepted by the community in few weeks.
- brg 16y agoAt 66 pages, coming from a well regarding researcher, and with its professional style of writing, I'd be shocked if this wasn't reviewed and slotted for publication before the end of the year. In fact, one may argue that by FOCS we'll have had so many graduate students, reading groups, and reviewers pour over this paper that we'll have either a consensus or have found an error.
- wlievens 16y agoIf a proof has been reviewed there might still be errors in it...
- eru 16y agoIndeed. But, fortunately, this is seldom a problem in math. I mean, often people discover problems in proofs --- but if the result was beautiful enough, they are usually able to repair the proofs. It's like debugging. (And I mean it, thanks to the Curry-Howard isomorphism.)
- sidww2 16y agoI'm curious - how do you know this mail was sent to the aforementioned people in complexity theory?
- drx 16y agoGreg Baker blogged about it (and since it's a hot topic, it probably appeared in many other places) -- http://gregbaker.ca/blog/2010/08/07/p-n-np/ http://gregbaker.ca/blog/2010/08/07/p-n-np/ Also, from the blog post: "I see someone else has uploaded the paper. I should point out that in the email thread I got, Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.". I would love to see that email thread.
- leif 16y agoSomewhere, deep in a dark corner of my heart, I hope and pray that this paper is correct, just so we can keep and revere the immortal words "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts."
- acangiano 16y agoThe font was specified to indicate that this proof, indeed, fits into the margin.
- baddox 16y agoBut is it truly marvelous?
- contextfree 16y agoIt's not big and professional like GNU's fonts.
- mkramlich 16y agoIf he can also prove it in 7pt font THEN I'll be impressed. Until then, meh.
- pclark 16y agoI'm not academic - can you explain why he mentioned the font sizes? Why are they relevant?
- deleted 16y ago[deleted]
- xsmasher 16y agoI find the sentence comical in its humility and practicality; I assume leif did too. Acangiano puts it in the same league as Fermat's famous note in the margin of his copy of Arithmetica. I assume he included the paper in two font sizes to suit the reader's preference; no deeper meaning.
- Aaronontheweb 16y ago10 and 12pt fonts - in Comic Sans