One of the most interesting things about the recent claim of a proof that P does not equal NP (see this post on the ice tea blog for a list of problems people are having with the proof, as well as this page hosted on the polymath project) is the amount of interest this paper has drawn. Certainly a large part of this has to do wit the fact that current there are (a) more computer science bloggers than ever before and (b) so many tweeters tweeting the night away. Also, of course, Slashdot can cause all hell to break lose.
But I wonder if there isn’t something else going on here. Privately I have spoken to colleagues who are much more qualified to understand this proof and they are generally skeptical of the claim. This seems completely rational to me, considering the long list of claims that either P=NP or P does not equal NP that have been shot down over the years (a fascinating list at the P-versus-NP page.) That their priors are well tilted toward skepticism seems fairly natural. So, my guess is that for the hard-core complexity theorists their really isn’t that much interest in taking time out of what they are working on understanding the paper…unless someone who they really respect tells them they should do so (I think the Optimizer’s post is a good example of this. Plus, please, people, stop emailing Scott, he needs to get some work done 😉 )
Yet still there is a lot of interest. I’d like to suggest that the reason for this is that the paper involves an unusual diversity of topics in attempting to make a proof. Indeed the paper (an updated version is available here) consists mostly of a lot of review of the fields which are claimed to be needed to understand the proof. These include work on random instances of k SAT, finite model theory, Hammersly-Clifford theorem, and more. Now there are people in theoretical computer science who have enough breadth to skip these review chapters, but I would say that they are in the minority. And even more interestingly there are people who probably are experts in just one of these areas who can read and nod their head at section of the proof, but don’t know the other sections. Okay well maybe I am projecting here, but I know when a group of AI people heard about the paper they were very interested that it used some of the concepts they use everyday. So maybe the reason that this particular P not equal to NP paper has grabbed this much attention is that it samples from a wide group of people who see parts they understand and therefore gets these people to try to understand the full proof. Okay that and the fact that the paper isn’t really “cranky.”
Now as to whether or not the proof is actually correct, well I’m not as rich as Scott, but I would bet that some of the points raised in objection are actually problems, so I’d need some pretty stellar odds before I’d bet that the proof is correct.
Oh and one other thought: it seems that the paper was actually “leaked” after Deolalikar sent the paper to a group of respected complexity theorists. I sure hope that whoever leaked the paper consulted the NyTimes ethicist before leaking it. Or maybe it was WikiLeaks who leaked the paper? Have they no shame?!?!
update:. Note that some people did ask the author for permission before posting about it. See this comment
O brave new quantum world!
It does put a dent in the theory that you must publish in large prestigious and respected conferences to attract any attention.
Apparently, if you work is intriguing enough, a mere email is enough to become famous.
Heck. At this point, will he even bother with conventional peer review?
Even we engineers care about *this* particular proof — over on Shtetl Optimized, Leonid Gurvits has framed Deolalikar’s proof strategy in a way that naturally establishes its relevance to practical quantum systems engineering.
So even if Deolalikar’s proof requires minor (or major) repairs, it already points toward methods and results that have considerable practical importance. Good!
@Suresh: Indeed I thought a bit about it too, but decided since at least two blogs had already posted, well…the cat was out the bag. Maybe _I_ need to write the NYTimes ethicist (who I ALWAYS disagree with) about what I did 🙂
@Suresh @dabacon
You have to wonder what motivated whoever leaked the document. If I received such a document, I would not post it online without permission. What do I have to gain?
I’d be very interested in knowing how the leak happened. No reputable scientist would leak a private communication without permission. That’s just not done.
I mean. Are we going to start having to sign NDAs?
For me, I was completely uninterested, seeing as how many claimed P ≠NP proofs are out there, until I heard that Cook was taking it seriously. At that point, I started getting excited, not necessarily because I thought it had been proved, but because we could at least learn something from it…
I agree with Chris about “big names” being “possibilists” (though I’m still waiting for someone to say “maybe” before starting a serious read of the paper, it’d be a lot of work for me). And I must admit, the euphoria is contagious.
It’s a good point about the leak issue. I don’t know if Deolalikar was prepared for such a firestorm, given that he did the right thing by circulating among a small group first. I’ve been as guilty as anyone of helping disseminate the paper, and I’ve been wondering whether I did the right thing.
Daniel, while you do have a point there, I suppose conventional publishing and peer review are still needed for valid papers that don’t have such an immediate appeal to the community.
Unless, of course, we intentionally change everything to some kind of organised community-based online refereeing system (and I think there is some possibility of success for that).
May I suggest a theoretical variant of the leaking affair? Assuming the dates I see here are reliable, the pnp12pt.pdf file was already online on 6 August. So…
Dick Lipton says that he was given a copy of the paper, and he did check with Vinay before talking about it in public. He is currently in contact with him as well.
Here’s an angle on the Deolalikar proof that I haven’t seen anywhere else …
(1) Everyone seems to agree (AFAICT), that viewed solely as an oracular assertion, “P≠NP” isn’t much use: it tells us only what we already strongly suspect (and many proofs assume). That is why, as Dick Lipton often reminds us, the “proof technology” is often what is really interesting about almost any proof.
(2) And so it would be truly wonderful, as Scott Aaronson’s blog reminds us, if Deolalikar’s (or any) proof of P≠NP embodied a proof technology that was eventually understood to “shine so brightly that the stars became vastly harder to see.” But that is asking a lot!
(3) That is why (for me) a particularly interesting aspect of Deolalikar’s manuscript is the dedication that he added between the first and second versions. Deolalikar’s added dedication includes the passage:
“This work is dedicated to my late parents: my father Shri. Shrinivas Deolalikar, my mother Smt. Usha Deolalikar, and my maushi Kum. Manik Deogire, for all their hard work in raising me; and to my late grand parents: Shri. Rajaram Deolalikar and Smt. Vimal Deolalikar, for their struggle to educate my father inspite of extreme poverty. This work is part of my Matru-Pitru Rin.”
“I am forever indebted to my wife for her faith during these years.”
This passage touches upon issues that (it seems to me) are of first importance to all mathematicians. Namely, how is mathematics going to be done on a planet with 10^10 people on it, given that (say) 10^7 of those people are hard-working family-supporting mathematicians?
It is mighty sobering to reflect that problems of the caliber of P≠NP are exceedingly few in number, compared to the immensely many mathematicians that our planet will be supporting (in every future except the most dystopian ones).
Since that sobering future is already 70% here, we might as well plan seriously for the remaining 30%. It is the business of engineers, in particular, to contemplate challenges like this very seriously … and to discern opportunities and enterprises within them.
That is why I would be *very* grateful to anyone who might care to discuss the Hindu concept of Matru-Pitru Rin, both specifically in relation to proofs of P≠NP, and more broadly in relation to the global-scale pursuit of mathematics. Also, Deolalikar’s dedication includes a Sanskrit passage that would be fun to read in translation.
Perhaps there is a Sanskrit-literate fan of Quantum Pontiff who can help?
This is a follow-up to John Sidles’ comment. Let me state clearly that I read this blog (and several others) just to get experts’ opinions about Deolalikar’s paper, and am not at all qualified to comment on the science. Rather my aim is to respond to his queries about the Sanskrit text.
On page 2 there are three lines in Sanskrit. They comprise two separate quotations having nothing to do with each other. In romanized script the first line says:
sharanyam sarva satvaanaam shreshtou sarva dhanushmataam
The next two lines (lines 2 and 3) say
karmanyevaadhikaaraste maa phaleshu kadaachana
maa karmaphalaheturbhoormaa te sangostvakarmani
Lines 2 and 3 are poem no. 2.47 of the Bhagavadgita. There are many translations into English available, and with this clue interested parties can find them. I give below my own translation into contemporary idiomatic English:
“Only action is within your power, not its rewards. Let not anticipation of reward be your motive, nor let your attachments deter you from action”.
Basically this says that doing your duty (in the case of many of us, doing our best to advance knowledge) is its own reward, not any material returns. On the flip side, anticipation that you won’t get rewarded should not deter you from doing your duty.
I have never seen the first line before. Here is a literal translation:
“I bow to the omnipotent, to the best, to the great archer”
This particular expression “dhanbushmataam” seems to connote Lord Shiva, the destroyer in the Hindu trilogy, as being “the great archer”. But I will double check and if corrections are needed, I will post them.
I can’t say anything very profound about the notion of trying to prove that P!=NP in particular, or doing mathematics in general, as a part of discharging one’s debt to one’s parents. I would say only that anyone brought up in a traditional Hindu environment, as I was and as I suspect Deolalikar was, would try to excel at whatever line he has chosen.
M. Vidyasagar, please let me thank you, with heartfelt sincerity, for your wonderful post.
My devoutly Christian relatives praise you as a Samaritan … my devoutly Jewish relatives praise you as a lamed-vavnik … my devoutly libertarian relatives assert that you posted out of self-interest (however, their views are very unpopular at family reunions) … and my Neanderthal relatives—who are by far the majority—praise you as a mighty shaman and sharer-of-knowledge!
Even though I am joking, my thanks are utterly sincere.
Because your post was wonderful. 🙂
Here Tao’s latest comment on Lipton’s blog:
1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP?
2. Does Deolalikar’s proof, after major changes, give a proof that P != NP?
3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?
After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No†(as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are addedâ€. But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days). It seems clear that one has to maneuvre extremely carefully to pursue this approach without triggering (in spirit, at least) the natural proofs obstruction, and one has to do something clever, non-trivial, and essential to separate k-SAT from things like k-XORSAT. So it is now clear that one should be quite skeptical of this approach a priori. But it would still be good to have an explicit explanation of this skepticism, and in particular why there could not conceivably be some independence-like property of random k-SAT that distinguishes it from simpler random structures, and which could be incompatible with P. I think we are getting close to such an explanation but it is not quite there yet.
If nothing else, this whole experience has highlighted a “philosophical†barrier to P != NP which is distinct from the three “hard†barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “globalâ€) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)
Somehow I first became aware of this attempt by a tweet from the physicist Sean Carroll. My immediate reaction was, “come on, Sean, there are a hundred of these every year and they’re always wrong.” Then I checked my email.. and the blogs… and Facebook… and found that a lot of real computer scientists I respect were taking it seriously. Lesson: even physicists are sometimes worth paying attention to!
@M. Vidyasagar : Thank you for the translations!
John – Mr. Vidyasagar (which btw means “ocean of knowledge”!) has already translated the two Sanskrit quotations in Dr. Deolalikar’s paper. You had also specifically asked what “Matru Pitru Rin” means. The words “Pitru Rina” (or Pitru Runa) mean the debt that a person owes to his or her ancestors, and by using the words Matru (feminine) in conjunction with Pitru (masculine), Dr. Deolalikar is emphasizing that the debt to our ancestors is both to one’s mother and father, and to both patrilineal and matrilineal lines. While Pitru Runa has a much more profound meaning in Hindu scriptures (e.g. in Taittiriya Aranyaka, 2.10.1), this particular reference to Pitru Runa was most likely meant as a dedication of the paper to his parents and his aunt (maushi), acknowledging a debt of gratitude that he is where he is today, thanks to their sacrifices and nurture.
Ram K., thank you for yet another excellent reply on this topic … both Deolalikar’s dedication and your post helo to reminds us of the debt that all of scientists, engineers, and mathematicians owe to previous generations, which we can only repay by creating similar opportunities for coming generations.
———————————–
As for my own surname “Sidles”, ours has been a farming family for many generations, in which tradition holds that our name it is indo-European for “stared mighty long at the hind-end of a plow-horse.” 🙂
Hi John,
Well, I didn’t want to hijack this thread and turn it into a discussion of names and/or obligations, but now that you have done it …
Like many South Indians of my generation, I write my family name first and given name last (like the Chinese and Japanese). So “Mathukumalli” is actually my family name, representing the village from which my ancestors hailed about two hundred years ago, while “Vidyasagar”, which as Ram K. informs means “ocean of knowledge”, is the moniker that my mother hung on me. Talk about parental expectations!
Thank you for the kind words above, and also for the “plug” on Scott Aaronson’s blog. If I ever live up to my mother’s aspirations, I want you to be my publicist! 🙂
Vidyasagar , it’s natural to admire big-hearted posts … yours was one.
When it comes to articles by students and/or non-specialists that are obscurely written, that are wrong, and are immediately recognizable to experts as wrong … *that* class is undoubtedly large.
Far more interesting (to everyone) is the small-but-elite class of articles by students and/or non-specialists, that are obscurely written, that are right … and were eventually recognized by experts as right … *that* is an elite class.
In CS and QIT, three ignored-works-by-students that come to mind are Ralph Merkle’s early work on public key cryptography, Hugh Everett’s early work on many-worlds quantum mechanics, and Stephen Wiesner’s early work on quantum money (and I would put Troy Schilling’s thesis under Abhay Ashtekar, Geometry of quantum mechanics, in this class too).
These cases remind us that it does happen that students and/or outsiders do have very good ideas … even transformational ideas.
But these cases also illustrate the worth of academic traditions and norms. Authors have an absolute obligation to help readers by respecting norms of behavior and presentation, by writing clearly, and by responding constructively to criticism.
It’s tremendously good—for students especially—to work with coauthors and students; their criticisms and questions are invaluable. Also, never turn down an opportunity to present your work … pretty much everyone appreciates that speakers have learned more from preparing their lectures, than audiences ever have learned from listening to them.
That’s perhaps the main reason that mathematicians and scientists attend so many lectures, and contribute so many respectful questions from the audience … it’s to earn those invaluable opportunities to prepare to be on the other side of the podium.
So if you think you have a good idea … but haven’t yet written it up in clear detail … and found coauthors interested to pursue and develop that idea … and devised effective idioms for lecturing upon and teaching these idea … then you haven’t yet begun the toughest portion of your work, and probably your ideas won’t receive much attention.
Everyone needs some privacy and and has some private ideas—students especially—but nonetheless, working for prolonged periods in isolation and/or secrecy is nearly always a bad research strategy. If you strongly prefer to work in isolation and/or secrecy, then consider becoming a novelist, not a scientist, mathematician, or engineer!
None of the above are my own ideas; these opinions are so widely held in academia as to be nearly universal.
I attended a talk this saturday by Prof. Narendra S. Chaudhari on a possible proof for P=NP. A polynomial time algorithm O(N^13) for solving the 3SAT problem. from various angles this seemed to be the answer for the famed problem. In this non-DFS approach the key issue seems to be the representation step that inherently avoids the exponential time complexity. Please check out the paper published in Indian Journal of Mathematics and Slides of the talk by this unassuming man at http://dcis.uohyd.ernet.in/~wankarcs//index_files/seminar.htm.
Very very exciting times when there are two serious attempts one by Deolalikar at P != NP and a constructive proof of Chaudhari for P=NP.