P != NP?

A 100+ page paper by Vinay Deolalikar, a Principal Research Scientist at HP Labs has been making waves in the computer science / math blogosphere, primarily because it claims to have solved one of the most famous problems in theoretical computer science, by proving that "P is Not Equal to NP."

My brief (and only) encounter with this problem was through a popular talk [[slides, though these from an earlier lecture (ppt, 16.6 MB) are better]] by Prof. Avi Wigderson, so I won't say anything more about the paper.

But I am interested in how other scientists react to a major new development such as this one. The community of mathematicians and theoretical computer scientists have organized themselves to verify Deolalikar's proof; as Richard Lipton quotes Yuri Manin, "A proof only becomes a proof after the social act of 'accepting it as a proof'."

If Deolalikar's proof survives expert scrutiny, he will win the US $ 1 million Clay Mathematics Institute Millennium Prize, and blogs and wikis [see below] will have given us a ring-side view of history being made.

This, I think, is the best of "Public Science."

* * *

Here are the blogs to follow: Richard Lipton at Gödel's Lost Letter and Suresh Venkatasubramanian at The Geomblog. And this page on the Polymath wiki aggregates the discussion on Deolalikar's paper. Terry Tao's Buzz is worth following too.

* * *

A few early reactions from bloggers:

• Scott Aaronson is skeptical that the proof will survive scrutiny, and makes this bet:

  If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.

• Daniel Lemire "[finds] it interesting that:

  ... Deolalikar did not submit the paper to a journal, as far as I know. He didn’t even post it on arxiv like Perelman. Yet, he is receiving much attention. His name is being tweeted several times a minute. Many of the most influential theoretical computer scientists are reacting to the paper. He is getting the best peer review possible.