P != NP

[armrha]

Big news this Sunday was a paper released that claims to be a serious proof on the P = NP problem. Big enough to bring me out of livejournal limbo for at least a day. It's a draft paper by Vinay Deolalikar, and I think it's been pulled for the moment while they are addressing some typographic errors and some incorrect methods in the paper, but its

Comments

[babydoc3]

I was just talking about this problem to my algorithms class last week. I have a joke that anyone who solves it will get an automatic A.

I am not surprised it was proven false. If it was true, somebody would have found a polynomial time algorithm for one of the many NP-complete problems by now.

It's not world changing news, but it's at least as big as the proof of Fermat's last theorem, which got quite a bit of coverage in the mainstream press.

Thanks for posting this. Big news indeed!