commentary, computer science, gambling, people, prediction markets, trends

Where is the betting market for P=NP when you need it?

12 Comments

HP research scientist Vinay Deolalikar has constructed the most credible proof yet of the most important open question in computer science. If his proof is validated (and there are extremely confident skeptics as you’ll see) he proved that P≠NP, or loosely speaking that some of the most widespread computational problems — everything from finding a good layout of circuits on a chip to solving Sudoku puzzles to computing LMSR prices in a combinatorial market — cannot be solved efficiently. Most computer scientists believe that P≠NP, but after decades of some of the smartest people in the world trying, and despite the promise of worldwide accolades and a cool $1 million from the Clay Mathematics Institute, no one has been able to prove it, until possibly now.

Scott Aaronson is a skeptic, to say the least. He made an amazing public bet to demonstrate his confidence. He pledged that if Deolalikar wins the $1 million prize, Aaronson will top it off with $200,000 of own money. Even more amazing: Aaronson made the bet without even reading the proof. [Update: I should have said “without reading the proof in detail”: see comments] (Perhaps more amazing still: a PC World journalist characterized Aaronson’s stance as “noncommittal” without a drip of sarcasm.) [Hat tip to Dan Reeves.]

As Aaronson explains:

The point is this: I really, really doubt that Deolalikar’s proof will stand. And while I haven’t studied his long, interesting paper and pinpointed the irreparable flaw… I have a way of stating my prediction that no reasonable person could hold against me: I’ve literally bet my house on it.

Aaronson is effectively offering infinite odds [Update: actually more like 2000/1 odds: see comments] that the question “P=NP?” will not be resolved in the near future. Kevin McCurley and Ron Fagin made a different (conditional) bet: Fagin offered 5/1 odds (at much lower stakes) that if the question is resolved in 2010, the answer will be P≠NP. Bill Gasarch says that he, like Aaronson, would bet that the proof is wrong… if only he were a betting man. Richard Lipton recounts a discussion about the odds of P=NP with Ken Steiglitz.

But beyond a few one-off bets and declarations, where is the central market where I can bet on P=NP? I don’t even necessarily want in on the action, I just want the odds. (Really!)

My first thought was the Foresight Exchange. It does list one related contract — Good 3SAT Algorithm by 2020 — which should presumably go to zero if Deolalikar’s proof is correct. It hasn’t budged much, consistent with skepticism (or with apathy). My second thought was the PopSci Predictions Exchange (PPX), though sadly it has retired. InklingMarkets has a poll about whether P=NP will be resolved before the other Clay Institute prize questions, but not about how it will be resolved or the odds of it happening. (The poll is one of several markets sponsored by the Woodrow Wilson Center’s Science and Technology Innovation Program — hat tip to Vince Conitzer.) I don’t see anything at longbets, and anyway longbets doesn’t provide odds despite it’s name.

In 1990 Robin Hanson provocatively asked: Could gambling save science?. That question and his thoughtful answers inspired a number of people, including me, to study prediction markets. Indeed, the Foresight Exchange was built largely in his image. P=NP seems one of the most natural claims for any scitech prediction market.

All these years later, when I really need my fix, I can’t seem to get it!

2010/08/14 Update: Smarkets comes the closest: they have real-money betting on whether P=NP will be resolved before the other Clay Institute prize questions. They report a 53% chance as of 2010/08/14 (for the record, I would bet against that). What’s missing is when the award might happen and how the question might be resolved, P=NP or P≠NP. I also don’t see a graph to check whether Deolalikar’s proof had any effect.

If it wasn’t clear in my original post, I found Aaronson’s bet incredibly useful and I am thrilled he did it. I believe he should be commended: his bet was exactly what more scientists should do. Scientists should express their opinion, and betting is a clear, credible, and quantitative way to express it. It would be as shame if some of the negative reactions caused him or others not to make similar bets in the future.

I just wish there were a central place to make bets on scientific claims and follow the odds in the vision of Robin Hanson, rather than every scientist having to declare their bet on their own individual blogs.

12 thoughts on “Where is the betting market for P=NP when you need it?”

  2. Yup, we created one as Lev said. We thought about different ways for a proven/not proven bet but couldn’t come up with language that was independently verifiable and fair so we settled on next winner of Clay Prize. Any suggestions welcome and we’ll put up something on Smarkets.

  3. Thanks Lev and Jason. You’re right: that’s close and the best so far. It would be nice to know how and when but understood those are trickier, Jason. Is it possible to see a graph of historical prices to see if the odds have gone up since Deolalikar proof become known?

  5. Pingback: Tweets that mention Where is the betting market for P=NP when you need it? » Oddhead Blog -- Topsy.com

  6. I disagree with the infinite odds part since he gains something from from being right. Here’s how I put it in the comments of Scott’s blog:

    We can compute Scott’s probability of the proof’s correctness if we make an assumption about the value to him of conveying his certainty to us. Let’s say that’s $100. Then Scott thinks there’s a 0.05% chance the proof is right (or fixable).

    (The $100 estimate was probably low given the huge publicity Scott has gotten. Nonetheless, all signs are that Scott’s prediction will be vindicated.)

  7. Even more amazing: Aaronson made the bet without even reading the proof

    In his followup post, Aaronson says that he “spent a sleepless night with Deolalikar’s manuscript” before making the bet, so I don’t think this is the case.

    You weren’t the only one to jump to this conclusion, though. Aaronson adds in a comment: “that I would (try to) READ the proof before making such an offer, I considered too obvious to be worth stating. I’d forgotten about so many people’s tendency to give everything I write the least charitable interpretation possible.”

  8. Thanks Mike. Is that market open to only Mitre employees?

    Thanks Dan: good point. I agree Aaronson’s bet does not imply he is infinitely confident and I agree with your rough calculation. By “offering odds” I meant literally his risk/profit ratio in cash. I think you’re right it makes more sense to assess the “profit” even though it’s not cash.

    Gareth: thanks for the clarification: I should have said “without reading the proof in detail”. I was amazed at Aaronson’s confidence, and did not mean to imply he was careless or reckless (apologies to Aaronson if it came across that way). In fact, I believe his bet was exactly what more scientists should do. Scientists should express their opinion, and betting is a clear, credible, and quantitative way to express it. It would be as shame if some of the negative reactions caused him or others not to make similar bets in the future.

    I just wish there were a central place to make bets on scientific claims and follow the odds in the vision of Robin Hanson, rather than every scientist having to declare their bet on their own individual blogs.

  9. Note that “Good 3SAT algorithm” is equivalent to “Exponential Time Hypothesis is false”. ETH implies P ≠ NP but it is entirely possible that there is a good 3SAT algorithm but P ≠ NP.

  10. My previous comment probably only made sense to theoretical computer scientists. David’s comment “which should presumably go to zero if Deolalikar’s proof is correct” in the original post is wrong; it has the implication mixed up. In plain English: even if someone proves that P ≠ NP, it is entirely possible that “Good 3SAT algorithm” could still pay out 1. On the other hand, if “Good 3SAT algorithm” is settled to have value 0, then we would know that either P ≠ NP or that the Foresight Exchange was a very inefficient market.

  11. Thanks for the clarification Andras. I don’t quite understand. If “good” means polynomial time, how could P≠NP and “good 3SAT” both be true? “Good 3SAT” implies P=NP, no? Or are you referring to the language about randomization in the text of the 3SAT claim?

Comments are closed.