A relatively serious proof that P ≠ NP?

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

• Richard Lipton thinks this is a “well written paper, by a serious researcher” and “who knows—perhaps this is the solution we have all have been waiting for”.
• Lance Fortnow is laconically cautious: “Much ado about an unverified proof”.
• Dave Bacon thinks “this a fairly serious attack by a serious researcher”.
• Scott Aaronson is willing to supplement the million dollar Clay Millennium prize by $200,000 if the proof turns out to be correct, though he remarks that “even if this attempt fails, it seems to introduce some thought-provoking new ideas”.
• Daniel Lemire doesn’t comment directly on the contents the paper, but on some reasons why Deolalikar gets so much attention: well-written paper, and enough reputation to be considered as a peer.
• Suresh Venkatasubramanian seems to think that understanding this paper does indeed require knowledge of many fields. He’s also proposing a collaborative effort to identify any issue with the current version of the proof.
• William Gasarch would bet that Deolalikar “proved something very interesting, but not P ≠ NP”: we just haven’t made enough progress on that problem yet.
• Bruce Schneier also bets that the proof is flawed, despite the author being a “respected researcher”.
• Ryan Williams is quite sceptical (his technical comments here, here, here and here).
• Richard Lipton and Ken Regan highlight some technical issues with the proof.
• In the mean time, Geomblog reports that the analysis of Deolalikar’s proof moved to a new wiki, in collaboration with the Polymath project.
• Terence Tao says “[t]his is a serious effort, but one which sits somewhat orthogonally to the existing work on this problem”, so a sensible evaluation might require quite some time.
• András Salamon is also “sceptical”, as “the technique used is unlikely to work to prove the desired result”. However, “the paper is definitely worth reading” anyway.
• More detailed comments by Ryan Williams on the Polymath wiki.
• In another post, Dave Bacon comments on the reasons behind the interest drawn by the paper (it’s very broad in scope and contains a lot of review). And, by the way, he and his colleagues are sceptical too.
• Charanjit Jutla thinks there’s a “huge (unfixable) gap”.
• As of 10 August, 22:58 UTC there isn’t any mention of the P ≠ NP paper on Deolalikar’s home page anymore (though the paper itself is still available in its third version).

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.