Initial Reaction to New P!=NP Paper

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.

Advertisements
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

One Response to Initial Reaction to New P!=NP Paper

  1. Pingback: decencyisarelativething » Initial Reaction To New P!=Np Paper | Reflections on Operations …

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s