Hacker Newsnew | comments | ask | jobs | submitlogin
zacs 1347 days ago | link | parent

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/



leif 1347 days ago | link

Somewhere, 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 1347 days ago | link

The font was specified to indicate that this proof, indeed, fits into the margin.

-----

baddox 1347 days ago | link

But is it truly marvelous?

-----

contextfree 1347 days ago | link

It's not big and professional like GNU's fonts.

-----

ratsbane 1347 days ago | link

Sounds a little like the line in Watson and Crick's first paper about DNA. They said "It has not escaped our notice..." to introduce the idea that the subject of the paper might be the secret to life, the universe, and everything.

-----

mkramlich 1347 days ago | link

If he can also prove it in 7pt font THEN I'll be impressed. Until then, meh.

-----

pclark 1347 days ago | link

I'm not academic - can you explain why he mentioned the font sizes? Why are they relevant?

-----

xsmasher 1347 days ago | link

I 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.

-----

leif 1347 days ago | link

Yeah, basically I found it funny juxtaposing the announcement of such a magnificent result (should it end up proving true) with such a mundane, utilitarian comment.

-----

fmora 1347 days ago | link

True, some of those intellectuals must have poor eyesight due to a lifetime of reading.

-----

robryan 1347 days ago | link

It does feel a little intentional on the part of the author to give off a "all in a days work" type attitude.

-----

wensing 1347 days ago | link

Happy to see it in my collegiate font of choice, Book Antiqua.

-----

celoyd 1347 days ago | link

Book Antiqua is a knockoff of Palatino, which in turn is the titling variant of Aldus: http://en.wikipedia.org/wiki/Aldus_(typeface) . It should read a little more smoothly.

-----

JeanPierre 1347 days ago | link

If this proof is up for review, that would mean there could be errors in it, right?

-----

zacs 1347 days ago | link

As another commenter mentioned, it will likely take months or even years to verify.

-----

brg 1347 days ago | link

At 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 1347 days ago | link

If a proof has been reviewed there might still be errors in it...

-----

eru 1346 days ago | link

Indeed. 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.)

-----

Aaronontheweb 1347 days ago | link

10 and 12pt fonts - in Comic Sans

-----

sidww2 1347 days ago | link

I'm curious - how do you know this mail was sent to the aforementioned people in complexity theory?

-----

drx 1347 days ago | link

Greg 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/

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.

-----




Lists | RSS | Bookmarklet | Guidelines | FAQ | DMCA | News News | Feature Requests | Bugs | Y Combinator | Apply | Library

Search: