Richard J. Lipton's blog was where the action was last year when Deolalikar announced he had a proof of arguably the most important problem -- Is P equal to NP? -- in theoretical computer science. Lipton has an update of sorts on the status of Deolalikar's work: nothing new on the paper itself (at least in the public domain), but plenty of lessons from those heady days of Public Science. Here's one:
... there may be substantial contributions, perhaps new conditional results, that can possibly come from [Deolalikar's] work. This may be where the worry most applies. If there is something in Vinay Deolalikar’s long paper, then this is worth attending to, and the first onus is on the author.
10 Comments:
I am a PhD student in Theoretical Computer Science. Multiple papers are uploaded into arxiv every month, claiming to solve the P vs NP question. It was really amusing why this particular paper got so much attention. An overwhelming majority of the complexity theory researchers do not even consider it as a serious attempt at the problem.
Hi Sayan
You say "An overwhelming majority of the complexity theory researchers do not even consider it as a serious attempt at the problem." yet "this particular paper got so much attention". Any idea why so? Just curious, as an outsider. As an aside, its interesting that a candidate proof of P=NP is not easy to see whether valid or not :-)
Hi Vijay,
Perhaps the best commentary on Deolalikar's paper is this blog post by Scott Aaronson (who is a professor at MIT).
http://www.scottaaronson.com/blog/?p=458
Scott makes 8 points, some of them may seem a bit technical to outsiders, but I guess you will be able to appreciate point #5, #6 and #8.
A disclaimer: I have not looked at the paper myself.
Regarding your last comment, may be I didn't understand what you meant to say, but Deolalikar claimed to prove P != NP.
Thanks much Sayan for the Scott Aaronson link. Understood a little bit (which I will soon forget, sadly, a la Scott with Conrad) and also enjoyed the link to Dawkins's narrow escape from death by pendulum.
Cheers
Vijay
@Sayan: I'm sure you know that there was enough in Deolalikar's paper to cause a stir -- there was enough in it that several leading lights in the field (perhaps not Scott Aaronson, but many others participated in the comment threads at Lipton's blog last year) didn't lump it with all those "multiple papers ... uploaded into arxiv every month." Which is probably why Lipton is hoping that some key insights may still be salvaged from all that work. Unfortunately, after causing a stir, Deolalikar decided to go into a shell ...
I think Deolalikar's background helped him to get the publicity that he got. Lipton is an old hand and very good, so he might have thought this was a good point of departure to try and revive this problem. And he has succeeded! P=NP issue is the dream problem of everyone over 50 in computer science and Lipton and many of us are in this category. We grew up on this problem!
@Abi: Perhaps my first comment was too harsh. Let me rephrase it in the following way. Deolalikar claimed a proof that P != NP. Some great names went through the paper and found fatal flaws. Within two weeks, there was a consensus in the community that Deolalikar's proof does not work.
Now it is very common for researchers to make mistakes. Even great mathematicians sometime come up with errorneous proofs. However, once the bug is found, the proper thing to do is to acknowledge the mistake and retract the claim.
The fact that Deolalikar has not yet acknowledged that he made a mistake shows him in poor light.
Cheers.
Sayan
@Sayan. I don't see how your comment at 8:58 pm is a 'rephrasing' of your earlier comment. The two comments say very different things.
@Ankur: Guilty as charged :-)
@Abi:
I wrote a comment here but it grew so lengthy that I decided not to post it. The following are mostly the _other_, remaining points (!!)
@Sayan:
You said:
"However, once the bug is found, the proper thing to do is to acknowledge the mistake and retract the claim.
The fact that Deolalikar has not yet acknowledged that he made a mistake shows him in poor light."
Hasty conclusion. Check out Deolalikar's note on his page.
BTW, Scott Aaronson writes on both QX (quantum phys/mech/theory/phil/info/whatever) and CCT (computational complexity theory). Looking at what he says about QX, I can't be too sure how immediately one may go along with him on whatever he says for any proof for any position on the P-vs-NP problem. He is skeptical in principle. And, as an aside, more acerbic than helpfully expert. (E.g.: He doesn't cite any principle why the lower bounds should matter to settle the proof, does he? How do you know that the matter is germane to a position on the problem let alone to a proof? Obviously, it's all hunches he is talking about. Keep them that way---hunches. Even if written in a sharp way.)
@Gautam:
The problem with the P-vs-NP is that it is not well-defined. I used to think that I had a good solution strategy. However, once I began working a bit towards translating it into the CCT terms, and so browsed a few papers (20+), and so ran into people like Aaranson, I decided not to pursue it. Also see next paragraph.
As to the Aaranson vs. Deolalikar issue. It looks more like Pepsi/Coke, East-Coast/West-Coast thing to me. In contrast, Lipton seems hell-bent on sitting on the fence, i.e. thinking that no solution would ever be possible. (Given where he has already gone, it beats me why he cannot simply go one step ahead and name the solution, at least the strategy.) However, chances are, with his experience, Lipton is a better academic than Aaranson. Yet, note: both are simply shrewdly playing the game to enhance the value of the problem. Unless they make it big, how can their own research programs become big? So, on second thoughts, both Lipton+Aaranson vs Deolalikar seems to be one of those Pepsi/Coke sort of things.
As to Deolalikar's next version: Fingers kept crossed.
--Ajit
[E&OE]
Post a Comment