The really big news from Hewlett Packard this week was not the dismissal of CEO James Hurd but the announcement by HP Labs researcher Vinay Deolalikar that he has settled the central question in theoretical computer science.
That central question is called the “P versus NP” problem, and for those who already know what that means, his claim (of course) is that P does not equal NP. For those who don’t already know what that means, “P versus NP” is a problem about the difficulty of solving problems. Here‘s a very rough and imprecise summary of the problem, glossing over every technicality.
Deolalikar’s paper is 102 pages long and less than about 48 hours old, so nobody has yet read it carefully. (This is a preliminary draft and Deolalikar promises a more polished version soon.) The consensus among the experts who have at least skimmed the paper seems to be that it is a) not crazy (which already puts it in the top 1% of papers that have addressed this question), b) teeming with creative ideas that are likely to have broad applications, and c) quite likely wrong.
As far as I’m aware, people are betting on point c) not because of anything they’ve seen in the paper, but because of the notorious difficulty of the problem.
And when I say betting, I really mean betting. Scott Aaronson, whose judgment on this kind of thing I’d trust as much as anyone’s, has publicly declared his intention to send Deolalikar a check for $200,000 if this paper turns out to be correct. Says Aaronson: “I’m dead serious—and I can afford it about as well as you’d think I can.” His purpose in making this offer?
I could think of only one mechanism to communicate my hunch about Deolalikar’s paper in a way that everyone would agree is (more than) fair to him, without having to invest the hard work to back my hunch up.
On the one hand, this seems like quite an effective way for Scott to communicate the strength of his hunch, which is obviously something he very much wants to do. On the other hand, I’m a little baffled by Scott’s remark (in the comments to the linked post) that “If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it.” I’m sure that if P≠NP has indeed been proved, it will dramatically change the life of a complexity theorist like Scott Aaronson, but I’m not sure why it will change it in a way that makes $200,000 less valuable.
But that’s of course his call. I just wanted to share this and invite your comments.