Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] The Probability of P=NP

Expand Messages
  • Lance
    Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P≠NP (if it s independent it s still equal or unequal
    Message 1 of 1 , Dec 4, 2009
      Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P≠NP (if it's independent it's still equal or unequal in whatever model of set theory we happen to live in). So I responded that I was highly confident that Prob(P=NP)=0.

      Not good enough for Dean, a professor in the Wharton statistics department, who said "But you aren't willing to give a number? Good Bayesians / Game Theorists have to bet on everything!"

      A good Bayesian puts a probability p on every future event E where one would be indifferent to taking a small bet that pays off 1-p if the event is true and loses p if the event is false. 

      As a computational complexity theorist we tend not to be Bayesians, rather look at worst-case performance under that assumption that everyone is working against us. But I've been talking with economists a bit recently so lets take the Bayesian approach.

      Richard Lipton asked if one would bet their life that P≠NP. In some sense I have since the vast majority of my research becomes trivial or uninteresting if P=NP. But how much one bets isn't really the right question since that involves taking risk into account as well as beliefs. 

      So what odds do I give? The problem is that I could only bet conditional on P v. NP being solved in some reasonable amount of time which would alter my beliefs since a proof that P=NP requires only an algorithm but a proof that P≠NP requires showing no algorithm can work. And the no trade theorem comes into play: If someone were to offer me a bet on P v. NP, I'd secretly suspect that they knew an algorithm or a proof I hadn't seen yet. But suppose that I could make a bet against a magical oracle would reveal the correct answer once a bet is made.

      Still I can't in my heart give a positive probability to P=NP. So the probability of P=NP is zero, but in the measure theory sense that because an event has probability zero it doesn't mean it can't happen, only that it won't.

      Posted By Lance to Computational Complexity at 12/04/2009 06:26:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.