August 11, 2010

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.


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.


Samir said...

A friend of mine is a student of Wiles' and he says that Wiles pretty much worked secretly and by himself to solve Fermat's Last Theorem.

Rahul Siddharthan said...

I would argue that conjectures like P!=NP, the Riemann hypothesis, etc, will only be proved/disproved by scientists working off the beaten track, probably on their own. The reason is simply that if the proof was possible by standard methods, it would have been found by now. (It is also possible that some of these conjectures are true but unprovable.)

Of course, not every crackpot deserves attention, but Deolalikar is no crackpot and the experts seem to agree that, even if he is wrong (which is likely enough), he has raised some interesting ideas.

Dilip D'Souza said...

Good points about working in secret, both of you. Though with Wiles, remember that there was a pretty fundamental hole in the proof he first presented, which he was finally able to fill (a year later?) with help from others.

Yes, from all I've read so far, the consensus seems to be that Deolalikar's is a serious take on the question and deserves attention. Good for him, and like I said I hope it stands up. RS, have you looked at the proof, what do you think?

Rahul Siddharthan said...

It's way beyond me, but seems to be an interesting interdisciplinary approach (ie, uses ideas from statistical physics about the kSAT problem). Even the experts seem to be a bit uncertain about whether there are unfixable problems. I certainly don't have the expertise to evaluate it.

Suresh said...

Terence Tao's latest comment on Richard Lipton's blog lays out the structure of Deolalikar's "proof" (in terms that even I can understand) as well as the reasons why he thinks the proof is wrong.

Three comments:

1. I don't know much about Terence Tao other than his being a child prodigy and a Fields medal winner...but the clarity of his thinking stands out even amongst a bunch of really, really smart guys. What a guy!

2. One only wishes that all blog discourse would meet the standards on Lipton's blog - something that many others have noted.

3. It is your blog and all that, of course, but I hope you realize that maths seems to be the ultimate disinfectant for the trolls...more such posts would be deeply appreciated, at least by me.

Dilip D'Souza said...

Suresh, even I got the gist of what Tao was saying, and that must say something about the guy. I've always thought one mark of a great scientist is if he can explain complex ideas in terms us mortals can understand. Feinstein is one such.

Yes and yes, about the discourse on Lipton's blog.

And about disinfectant for trolls: well, yes, point taken and absorbed and maybe I will make an attempt to move more in that direction and earn your appreciation. Yet there remain issues I'd like to say something about ...

Chandru K said...

Posted by "Rohitvats" in another forum. Attitudes he refers to are spot-on!

"I really find this response from
Western Press, and BBC in this case, as something smacking of contempt. Same is the case with couple of comments (posted on Wiki) by other Mathematicians on the paper (except for one chap).

It is, as if, they somehow and for some reason want the proof to fail. There is some sort of arrogance and chip on the shoulder attitude that these fellows demonstrate....I'm yet to come across a case where someone has said - OK, someone has tried to do this, let us have a look and see where it stands...I mean, people don't wake one fine day and claim to have solved one of the toughest Math problems..the fellow is staking his reputation on it and would have worked long hours and years on it the case of contempt because an Indian has tried it (how can he? we are superior onleee)? Or because of professional jealousy? I don't know."

Dilip D'Souza said...

Quote above: What a mealy-mouthed reaction from a guy who has no clue of the meaning of peer criticism in science. The consensus among Deolalikar's professional peers is clearly that he has made a serious, genuine effort to solve the problem (i.e. even if his proof eventually does not stand). The discussion on the mathematician Robert Lipton's blog is, as Suresh above points out, a model for us all (i.e. not just scientists).

Yet of course there are the guys who will see racism and national insult even in this.

Suresh said...

*Sigh* I see I spoke too soon about disinfectants...

At any rate, the end seems nigh for Deolalikar's proof. More than the actual failure -- which is honourable -- it is the curious decision to send out what appears to be a half-baked manuscript which is puzzling. This, understandably, has riled many in the maths community and I don't really blame them. See the harsh (but justified, IMHO) comment by "vloodin."

Rahul Siddharthan said...

Trolls aren't so easily avoided...

Anyway, it looks like Vinay D was the victim of a premature leak: he did not intend to release it to the internet but only sent it to some experts (how many?) for comments. Once it was leaked and got huge publicity, he seems to have decided he may as well release revised versions himself... But perhaps the public scrutiny speeded the process of finding flaws.

aditya said...

Dilip, I'd say the jury is still out on whether great discoveries still can happen in isolation. Just yesterday I was reading a section of Brook's The Design of design and he was arguing the same thing! Surely, computer science, in particular, has become so vast now that great discoveries can't be a matter of isolation anymore but primitive problems (and this is one, I am sure you'd agree) still can be pondered upon and perhaps be understood, at the least, in solitude.

Chandru K said...

"Quote above: What a mealy-mouthed reaction.."

The commentator 'rohitvats', was obviously not referring to Richard Lipton or the handful of informed, respectful responses to Deolalikar's efforts. Rather, to the general attitude in the math/sci/computer community. A quick perusal of the comments sections of concerned articles( about Deolalikar) would show how dismissive and contemptuous they are.