## 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/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.