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.
I find this dispute very odd. Robin Hanson ages ago came up with explanations as to why betting in science is a good idea. http://hanson.gmu.edu/gamble.html
ReplyDeleteThere are loads of prediction markets in science already. http://www.ideosphere.com/fx-bin/Claim?claim=CFsn
Now the futures in p=Np have to be set at some point int hte future. You could say "will P=NP be proven disproven by 2100" and the bets could change hands by our descendants. there are many long term financial risks that are traded like this.
suppose you come up with a proof that makes it less likely P=NP. Not proves it but just makes it less likely. The current odds are 1000 to 1 that someone will prove p=np by jan 1st 2100. You think that your proof will move the odds out to 2000 to 1. You would be a fool not to short P=NP bets and then reap a profit on the maths futures prediction market when your proof comes out.
Every use of public-key cryptography bets on P!=NP (and quantum computers not being built) over the period of time the encrypted information is considered relevant. There are even websites suggesting secure key lengths based on an estimation of a secure time-period during which keys of the suggested length should be secure. Of course these suggestions are only based on extrapolitions of Moore's law, but essentially, they also implicitly bet on P!=NP and QCs not existing. So, in fact, the bet that is being asked for has already been taken: just check what is the most valueable piece of encrypted information, that if cracked would be of serious financial value to the attacker. For example, a recent log of an SSL encrypted session of let's say Bill Gates accessing his bank account over the Internet would mean, that Bill Gates had implicitly accepted the bet of P!=NP and QC not existing with the current balance of his account.
ReplyDelete... Either you assigned an initial belief of 0 to the proposition, before you even learned anything about it, or you managed to obtain infinitely strong evidence against it.
ReplyDeleteIf neither of these, you are using something other than probabilities. "I can't find it in my heart..." hints at that.
Note that actually assigning probability zero means that if it actually does turn out P = NP, you would be unable to believe it even IF you saw and understood the proof. Even if the proof actually was constructive, gave an implementation of an algorithm that worked, and that you could easily test its ability to do stuff like crack just about any (non One-Time-Pad equivalent) crypto, ask of a particular mathematical proposition or its negation has a poof of length N or less, etc etc...
Even so, you would have to instead conclude you were hallucinating it all, or your ability to reason from that to the ability to evaluate the validity was flawed, etc... In other words, by assigning probability zero, you are effectively saying "no matter what, I am forbidden from ever admitting error on this matter" (assuming one's actually following the rules of probability)
oh, martinschwarz: Actually, pretty much all crypto other than one time pads is dependent on P != NP.
That is, other than stuff encoded via an OTP, one can generally tell the difference between a successful and non successful decryption, right? And do so in polynomial time. (For example, a successful decryption of english text looks like, well, english text. Has english words, syntax, etc...)
So being able to crack NP complete stuff would break pretty much anything not equivalent to a one time pad.
(oh, incidentally, there're some public key cryptosystems that seem to be able to survive the existence of a quantum computer, but not P = NP (well, okay, I guess if the exponent is high enough, then... but you know what I mean))
To the Bayesians who cannot understand Lance's answer: It's a bit like being asked "What's the probability that your loved one is an alien axe murderer?" There's obviously a non-zero probability for this event, but some of us can't bring ourselves to assign a non-zero probability to this event.
ReplyDeleteDon't take the Pr(P=NP)=0 statement at face value and start quoting Bayes theorem, Robin Hanson or Eliezer Yudkowsky.
In my naiive understanding of this post, maybe Lance just wants to say he much wishes P = NP not to be true.
ReplyDeleteThe probablity is more refered to belief in one's heart instead of real measure or proof...
Alien ax murderer comment: Hilarious and spot on.
ReplyDelete> To the Bayesians who cannot understand Lance's answer
ReplyDeleteTo the theorists who cannot understand Dean Foster's question:
There are many of us who are not experts in theory, have never thought seriously about how to prove or disprove P=NP, but still have an interest in the problem, maybe even working on approximate approaches to NP hard problems on a daily basis. We clearly can't expect a yes or no answer, but we're very interested to know how close to one side or the other the experts think we are. The question is a very reasonable way to get at the answer*.
We're supposed to be scientists--I would hope that we can separate our personal hopes and biases from our objective interpretations of the evidence. Answering seriously would help us better understand your field.
For the alien axe murderer crowd, help us out. Do you think it more likely that your loved one is an alien axe murderer or that P=NP? Is it more likely that your loved one is just a murderer or that P=NP? Give us some perspective, please.
* [rant] The evidential (or Bayesian) interpretation of probability is not an obscure notion reserved only for the "crazy Bayesians", and refusing to acknowledge it by claiming one only subscribes to the frequency view of probability is pretty elementary (http://en.wikipedia.org/wiki/Probability_interpretations)[/rant]
I think the last few comments have clarified the issue. So, to get some quantitative data after all, let's rephrase the question: "Lance, which one is more horrific and unbelievable: a) P = NP or b) Your loved one is alien ax murderer ?" Yes, we might need some follow-up questions.
ReplyDeletelancie, lancie, lancie, why don't you tell the story of your advisor ? I think that's worth an interesting read.
ReplyDeleteoh you mean the gold bet ? yeah, that's quite a thing. please tell us! please!
ReplyDeleteOf course, P != NP with probability 1 -- relative to a random oracle.
ReplyDeleteBennett and Gill Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1.
well, that's not the story that anon was talking about
ReplyDeleteWell, this bet "P vs NP" is too expansive "1 million $" for that.
ReplyDeleteBut what about:
(*) Multiplying two numbers is more difficult (requires at least log n more operations) than adding them?
Folks, I do not understand why we stick on "P vs NP" and the like, when we have more urge problems?
Just because we cannot approach them with "oracles" or similar?
I would bet for P!=NP, of course, but I would be much happier in a P=NP world. Then the questions, like (*) above, would attract more brains.
What are the odds on: P vs NP is solved. Don't be shy.
ReplyDeleteHere's the deal. If it is proved P=NP you give me absolutely everything you have. If it is proved otherwise, you run RAND() for a one in a million chance and if that happens I give you a penny. Deal? If not, your P is *not* zero.
ReplyDeleteI bet Lance would take Robin's bet.
ReplyDeleteI wouldn't take Robin Hanson's bet if he were betting that over the integers 1+1 equals 3. My utility of a penny (and I suspect Lance's as well) is effectively 0; it might even have a -ve utility to me since pennies are annoying to deal with.
ReplyDeleteWhat about a bet with a one in a trillion chance via RAND() that Robin gives Lance everything he has if P!=NP. Should Lance take that bet? In expectation it might be similar but at least there is no questioning the utility to Lance.
The utility of a penny may be zero or even negative, but what about the utility of P=NP? Do you think all of Lance's possessions have greater utility to Lance than a polynomial-time algorithm for 3SAT?
ReplyDeleteI'm not sure that scientific betting markets hold up when it comes to propositions that, if true, would completely change the way we understand the world. The utility of those propositions is effectively infinite, since they would require reformulating all of our existing utility functions in ways that we can't even comprehend. Therefore it is rational to accept any bet on that proposition short of the entire universe being destroyed---implying a personal probability 0 of the truth of that proposition.
ReplyDeleteI submit that P=NP is one of those propositions, and that Lance is therefore being entirely rational in giving it zero probability.
Robin, someone can refuse your bet, without revealing any useful information about their belief in P vs. NP.
ReplyDeleteA Bayesian agent must be logically omniscient; they have a probability of one or zero for all purely logical sentences, depending on whether they are either true or false. If someone is not able to ascribe such beliefs to logical statements, then they are not a Bayesian agent, by definition.
If they are not a Bayesian agent, then you cannot equate their degrees of belief with their propensity to bet, precisely because Dutch books exist against them -- their beliefs actually are (formally) incoherent.
In short, you can't use an argument which relies on the deductive closure of beliefs to reason about beliefs which are in fact not deductively closed.
A better question is: What's the probability of there not to be a solution to the P vs. NP problem? In other words, what's the probability that the problem is unsolvable?
ReplyDelete