Echoes in the blogodome: P!=NP?

There is a paper lots of people seem to be excited about claiming to have proved P \neq NP.  It does not appear to be crankery at all, but this wouldn’t be the first time a serious researcher has thought they found a proof, only for it to eventually fall apart due to an unfixable error.

R.J. Lipton has some very preliminary comments on his blog. “I do not know what to think right now, but I am certainly hopeful.”  If there is any place on the internet to look for news on this, it’s there.

I have no comments, being too stupid to understand it, yet.  But, I have had a small pet hypothesis that descriptive complexity (aka the finite model theory approach he takes) hadn’t been explored deeply enough.  Really.  I have this book here on it in the giant stack of books I haven’t read yet, and everything!  It’s been one of those “cool, I want to learn about that!” things since Richter pulled the “oh btw, this would prove NP \neq coNP” rabbit out of a hat at the end of Math Logic II a year ago… (and they say his magic tricks involving handkerchiefs are amazing…)

Update 8/10: Sounds dead (be sure to read the comments.)

Update 8/11: It seems that there were enough interesting ideas introduced that some salvage work has started.  Very optimistically, we might still see a possible proof of NL \neq NP come of this, which would also be awesome. At this point, I’m just linking to Lipton’s blog, so I won’t make further updates here. Go there for more information.

This entry was posted in Complexity, Irresponsible rumor mongering. Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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