Hacker News new | comments | show | ask | jobs | submit login

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.


Vinay Deolalikar Principal Research Scientist HP Labs


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

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

But is it truly marvelous?

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

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.

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

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.

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.

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

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

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

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.

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

10 and 12pt fonts - in Comic Sans

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

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

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.

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

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

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

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.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact