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
