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?













