P, NP and All That

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.

Print Friendly, PDF & Email
Share

13 Responses to “P, NP and All That”


  1. 1 1 Bennett Haselton

    Has a researcher ever published a paper and then offered a cash prize to the first person who can find any mistake in it?

    If a paper is considered more reliable after a certain number of people have looked at it and been unable to find anything wrong, then offering a prize could be a way of speeding up that process, as well as signaling the author’s confidence in the paper.

    For a paper announcing P != NP, it’s probably not necessary, as so many people will review it for free anyway.

  2. 2 2 Henry

    Is Scott’s reputation to honour his pledges worth $200,000? If not, isn’t his pledge non-credible?

  3. 3 3 John Faben

    Why is it that everyone always picks factoring as their example of an NP problem that’s not in P, when it’s one of the few ‘difficult’ problems that we don’t know is NP-complete? (in fact, we’d be pretty surprised if it was, as we know quantum computers can do factorisation in polynomial time)

    It seems very likely that, assuming P != NP (it’ll be nice to be able to write papers without including that caveat, if Deolalikar is proved right!), factoring is in one of the intermediate classes, but actually we don’t know anything about it. Deolalikar’s proof could be correct, and factoring could still be in P.

  4. 4 4 Howard M

    Maybe I am missing something, but in your explanation of P versus NP, didn’t you get it backwards, e.g. instead of “factoring, being NP, must also be P” should read “factoring, being P must also be NP”?

  5. 5 5 Steve Landsburg

    Howard: I believe I’ve stated this correctly. What we currently know is that factoring is NP. *If* P=NP, then factoring must also be P. What Deolalikar has asserted is that P does *not* equal NP, so we are *not* forced to conclude that factoring is P (though, as John Faben points out, factoring might still be P for some other reason).

  6. 6 6 AC

    His wager may be “irrational” in a sense, but I’m sure he isn’t trying to claim the proof would make $200,000 less valuable.

  7. 7 7 Martin

    HP’s ex-CEO is Mark Hurd, not James Hurd.

    Let’s hope that this is the end of the Hurd mentality at HP.

  8. 8 8 James D. Miller

    “claim (of course) is that P does not equal NP.”

    Why of course? If it’s for Bayesian reasons how do you get your priors? If it’s for frequency reasons what other class of proved or disproved proofs are you comparing it do?

    Isn’t the set of possible problems involved in P and NP so huge and the sample we have looked at so non-randomly distributed that we can’t draw strong inferences from available evidence?

  9. 9 9 JRF

    Is it really a bet if there’s no requirement for somebody else to take the other side?

  10. 10 10 Nick

    Its called a reward not a bet.

    The guy wins $1m straight off the bat if he’s correct anyway. Plus the greatest geek bragging rights on the planet…

  11. 11 11 John Faben

    James “of course”, because the universe we live in just doesn’t look like the sort of universe in which P = NP. There are a *lot* of good Reasons to Believe – my favourite (although by no means the most convincing) being the meta-argument that if P were equal to NP this should imply that finding a proof that P = NP would be easy, and no-one has managed it yet.

    Scott Aaronson has a list, and puts most of them better than I could:

    http://www.scottaaronson.com/blog/?p=122

  12. 12 12 jj

    My first thought on Scott Aaronson’s offer was that I hope he isn’t married…

  13. 13 13 Bob

    jj, Ah, yes, the stable marriage problem.

    (No, I am not familiar with this “humor” you speak of.)

  1. 1 Tweets that mention P, NP and All That at Steven Landsburg | The Big Questions: Tackling the Problems of Philosophy with Ideas from Mathematics, Economics, and Physics -- Topsy.com
  2. 2 கேள்வியின் நாயகனே… « ப்ளீஸ், ஒரு நிமிஷம் வெயிட் பண்ணுங்க…
  3. 3 Weekend Roundup at Steven Landsburg | The Big Questions: Tackling the Problems of Philosophy with Ideas from Mathematics, Economics, and Physics

Leave a Reply