August 10th, 2010


P != NP

For those playing along at home - this wiki has good discussion of Vinay Deolalikar's recent paper in which he claims to prove P != NP.

The wiki is pretty interesting. They're essentially crowd sourcing the task of verifying his proof. Already there's a fair number of objections. I have a gut feeling that Deolalikar's proof will ultimately be found lacking.

But, it's still really cool that he published it in this way and wrote it with an eye towards the layman. If you take a look at the paper it's surprisingly readable. (This is not to say I really understand it, but I at least get a sense of the terrain.) Contrast w/ Andrew Wiles's proof of Fermat's Last Theorem, which like 10 people in the world actually understand.

I always thought P != NP would turn out to be undecidable...

Man I hope some Qualified Professionals hurry up and review his paper for reals. If it's right, it may take months before we know. If it's wrong, the error could be found at any moment. Got to be nerve-wracking that.