UPDATED: A wiki page has been created on the polymath project wiki to discuss the proof as well as provide background on P=NP and a really thorough round-up of recent articles and discussion on the problem.
The internet is abuzz with news and analysis of Vinay Deolalikar’s paper claiming to prove P!=NP. Some interesting links are posted below:
- Vinay’s paper.
- A newly created Wikipedia article on Vinay.
- Richard Lipton offers a preliminary analysis of the paper on his blog Gödel’s Lost Letter and P=NP. This blog post is generating a lot of great discussion of the paper and his blog in general provides some good background into the P=NP problem.
- Scott Aaronson has offered a supplement of $200,000 if Vinay wins the $1,000,000 Clay Millennium Prize for his proof. One assumes from Scott’s post that he does not believe he will have to pay up.
UPDATE: Richard Lipton and Ken Regan have co-authored a blog post on Richard’s blog outlining some possible issues with the proof.
Mainstream media has started to publicize the news as well. AOL News has a glossary of important terms for the problem.