Antonio E. Porreca

A relatively serious proof that P ≠ NP?

09 August 2010

Note: I’ve stopped updating this post, now that I’ve collected quite a lot of comments. For the latest news, I suggest checking my tweets and, in particular, the Polymath wiki page (edited by more people than just yours truly). Maybe I’ll have another post in the next few days, if something shocking happens.

The news seems to have originated from a post on Greg Baker’s blog. The author of the claimed proof of P ≠ NP is Vinay Deolalikar, principal research scientist at HP Labs (though “[t]his work was pursued independently of [his] duties as a HP Labs researcher, and without the knowledge of others”). Judging from his past publication history, we can’t afford to immediately dismiss the author as a crank this time.

It seems that a preliminary version of the paper, dated 6 August (note: there’s a new version with “minor updates” here here), was circulated by Deolalikar to “several leading researchers in various areas”, rather amusingly in both “10pt and 12pt fonts” (apparently, the proof does not relativise to 11pt). According to Baker, Stephen Cook commented “This appears to be a relatively serious claim to have solved P vs NP”. The story started spreading when someone uploaded the paper to Scribd without the author’s knowledge.

The paper is very long (103 104 107 pages in the 12pt version) and involves “several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics”. So, before engaging in a serious reading, I’m going to wait for someone more qualified than me to make a preliminary evaluation. In particular, the word “physics” sounds pretty scary to me in this context.

What do computer scientists and related people on the web think about it? Here is a list of people who commented on Deolalikar’s paper (until 10 August).

The proof also made it to Gerhard Woeginger’s P-versus-NP page and, somehow, to BitTorrent (?). Nature news has an article on this story: Million-dollar problem cracked?.

On a side note, I’m genuinely surprised by the amount of buzz on Twitter generated by this story (mostly deriving from Slashdot and Hacker News I think). Independently of the actual correctness of the proof, I believe this is a good thing, as it suggests that there’s enough public interest for the most important open problem in computer science.