P and NP

I really hope Vinay Deolalikar takes away the $1M Clay prize. That's the heart speaking. I really doubt he will. That's the head speaking.

Perhaps you know that Deolalikar, a researcher at HP Labs (one of the most-respected research places in the world) has just claimed to have answered one of the knottiest open questions in computer science and mathematics, the P=NP problem. He claims P is not equal to NP. (This is not the place to attempt an explanation of what that means, but some of the links below attempt that, and if you leave a comment with your email I can give it a shot too).

He has made his proof available online (PDF, 650K). I am in no way competent to understand, far less judge, his paper, though plenty of mathematicians are at work examining it (Richard Lipton, for one.) But I will admit that I am, right off the bat, sceptical.

Why?

For one thing, Deolalikar says he worked alone, "without the knowledge of others". Mathematics, and indeed much of science, simply does not work that way any more. It nearly never happens that a scientist plugs away for years on his own and then produces a stunning new result. Science depends on collaboration and criticism and bouncing your ideas off your colleagues.

For another, the sciences are littered with the corpses of proofs offered for various hard problems. Fermat's Last Theorem, which Andrew Wiles famously solved in 1993, was one such. I began a post about Fermat with these lines: "For many years, Edmund Landau, a German mathematician, had a form letter that looked like this: "Dear Sir/Madam: Your proof of Fermat's Last Theorem has been received. The first mistake is on page _____, line _____." Landau would assign the job of filling in those blanks to one of his students. They must have been busy, because crank "proofs" of Fermat were something of a cottage industry; if I recall right, Orissa was a minor breeding ground for them."

There's more, and much of it's explained far better than I can by Scott Aaronson here (not about Deolalikar specifically). Aaronson, incidentally, has offered $200K of his own money on top of the Clay prize to Deolalikar if the proof stands.

Like I said, I hope to hell it does stand. If it does, it's a truly fabulous result. All of us who've studied some mathematics and computer science know something about P vs NP, about how complex an issue it is and yet how surprisingly beautiful, almost magnificently challenging it also is.

I'm trying to draw analogies here: If Deolalikar has solved it, it would be as if he came home from the 2012 Olympics with 50 individual gold medals; or as if he had found an easy way to beat gravity; or as if he had found a peaceful, lasting solution to the Kashmir issue. A proof of P vs NP would be exactly as earth-shaking as those.

And that's also why I am sceptical. Though I dearly wish I wasn't.