Would You Bet Your Life?
How sure are you that P=NP is impossible?
Groucho Marx is not a theorist, but was one of the great comedians of all time. He was in many hilarious movies, such as “A Night at the Opera,” “Horse Feathers,” and my personal favorite “Duck Soup.”
Today I have a simple question about P=NP: how sure are you that P is not equal to NP?
I thought of Groucho because of his famous TV show called, “You bet Your Life.” It was one of the most successful shows on TV—it ran for over ten years. It had nothing to do with actually “betting your life”—it was a simple quiz show that allowed Groucho to joke with the contestants.
A Million to One?
I once had a long discussion with Ken Steiglitz about P=NP, while I was still at Princeton. Ken is terrific and has many wonderful results, which I plan on discussing in a future post. I did tell one story about Ken and professional wrestling in an earlier post.
Ken was and still is sure that P must not be equal to NP. Okay, I said to Ken, what are the odds that they are equal? Ken said that he thought the odds were a million to one. I immediately suggested a bet. I did not ask him to “bet his life,” but I did ask for a million to one bet. I would put up one dollar. If in say ten years P=NP had not been proved, then he would win my dollar. If P=NP was proved in that time frame, then I would win a million dollars from Ken. Ken said no way. After more discussion the best bet I could get out of Ken was 
Two to one. That was the best he would do. Somehow that does not sound like a sure thing to me. Even a hundred to one was out of the question. Yet Ken was sure that they could not be equal. I do not think that Ken is unique in feeling that P=NP is “impossible,” but not willing to actually make a bet that reflects it being impossible.
Open Problems
The open problem is what odds would you give? Would you bet a million to one? Would you bet your life?
I think there’s a few problems here with this approach:
1. In ten years P vs. NP might not be solved. Which would make the guy bet, not on the problem itself, but on the capacity of people to solve it.
2. P=NP might be true or not(I think it’s false, for no other reason than it would make things less interesting), but betting on something like this is like betting against “God”. He could cheat and you’ll be left without your money.
Robin Hanson has written extensively on related topics. See, e.g.:
http://www.overcomingbias.com/2008/08/suspiciously-va.html
On P = NP: I’d accept a small bet at 10:1 odds that this is not provable – either P \neq NP or it’s independent of the usual axioms.
Whether factoring is in BPP is perhaps an even more interesting question for researchers in quantum computing. I wonder what odds you could get?
This is similar to one of the following two options.
– You get 1 billion dollars with probability 1
– You get 2 billion and 1 dollars with probability 0.5
– You get 1000000 billions with probability 0.01
Which one do you choose? It really doesn’t make sense to bet a million to one even if the odds were more than a million to one. Our bets also depend on how much utility does the money we win or how much damage can a loss cause.
Even if I believed a million to one odds, I don’t have a million dollars to give if I got that unlucky.
My personal odds are around 1:4, although given the difficulties presented by the oracles I believe it’ll need some wild new development from the mathematical logic folks.
Original poster’s logic makes no sense; how can you tie someone’s idea on the possibility of something to his finances? That’s ridicoluous. His well-being depends on his finances, and if there is an iota of possibility that he could lose that, he will not take that bet. He has nothing to gain for the immense risk he is taking either. People in finance call unforseen events the Black Swan; they protect themselves from it by gambling with a _portion_ of their money, minimizing against the possibility of losing their shirt if things go south.
The problem is people don’t have linear utility for bets on that scale: I imagine losing a million dollar bet would force Ken into bankruptcy and generally ruin his life: On the other hand, winning a dollar would have essentially zero change on his life. Even if he believed that it was 1000000 to 1 that P != NP, any positive probability on P=NP would seem to preclude taking your bet.
Now 100 to 1, thats a bet I would take.
This is all good. But I would bet million to one sun will rise tomorrow…dick
Or that Earth is not flat.
Although I’ve stared at the problem for a while now, I do have to admit I really don’t understand P=NP at all. But I do have some type of inkling that it answers a bunch of crucial questions about the what is really feasible with a computer and the upper bounds of some real possible algorithms. In that sense, I am hoping that if it were true that it would show us that we are barely tapping into the immense underlying power of our current machines. That there are so many more things we could calculate in a reasonable period of time, then we can even imagine now. I’d like to think that there are some really cool, previously unknown algorithms out there still left to be found.
So personally, right now at least, I’m hoping that it is proven true, so I’d definitely avoid betting on this 🙂
It’s interesting to think about when bets at a million to one odds actually are reasonable.
The million to one bet that the sun will rise tomorrow isn’t reasonable. If it doesn’t, both you and the other party probably have far more significant other problems (e.g., being dead). So one of you has no reason to enter into the bet.
(Incidentally, your odds assume a timescale for the sun not to rise of on the order of 3,000 years. For sufficiently broad interpretations of the sun not rising, that may actually be too ambitious. For example, if a supervolcano like Yellowstone erupts, the sun may not rise for quite some time. Nuclear winter is probably quite likely over that timescale, too.)
The million to one bet that the Earth is not flat isn’t reasonable, either. There, what you have to worry about is that the other party probably doesn’t have a very firm grip on reality.
What about on a sequence of 20 coin tosses all being heads? I wouldn’t accept that, either: I’d suspect something funny was going on with the coin. In fact, even if I was able to inspect the coin at length for fairness, I’d still worry about that.
I like your comment. But the basic question I tried to raise is this: if the conventional wisdom is so sure that P and NP are different, then shouldn’t the odds be pretty high? Perhaps not a million to one, but pretty high?
I entirely agree with you, a fact I perhaps did not make sufficiently clear earlier.
Indeed, I suspect this is quite a general phenomenon, not limited to P \neq NP: many scientists claim high confidence in some conjecture or hypothesis, but when asked to bet, their betting behaviour is not consistent with their qualitative statements of confidence, indicating a lower true confidence.
If this is correct, then it seems to me that the obvious conclusion is that some type of herding behaviour is going on, not justified by the available evidence, but rather driven by other factors. It’s easy to make up stories to account for such herding behaviour. E.g., stating a strong belief that factoring is not in BPP is certainly helpful if you want more support for quantum computing. Given that there’s little penalty if you’re wrong, but some reward for the statement, it would not be surprising if people ended up systematically overstating their belief. There is no need to attribute this to malice, either, since many people will derive their belief not directly from the evidence, but rather from signals given by other people; a small systematic bias will naturally be amplified.
I should say that I don’t think this is an accurate account of what’s going on! There are many other incentives at play here, and one would need to think them through carefully. This is intended as a simple model of how such biases potentially might arise, not as an account of what’s actually going on!
A further corollary, if you believe the analysis in my last comment has much truth in it, is that if you want to prove major results, then you should be more contrarian than is conventional, spending considerable time trying to disprove widely-believed conjectures. However, as the analysis indicates, while this may be a good strategy at making a major discovery, it’s potentially a risky career strategy (you’ll be outside the herd).
To Michael: You are essentially engaging in a million-to-one type bet when you purchase a lottery ticket.
Michael:
It’s curious to note that a coin with a constant probability for heads (say 0.2), may be used as an ‘fair coin’ using two or more tosses. So if you’re worried about the coin, that can be fixed 🙂
There’s no reason to assume a constant probability of heads. That can potentially be manipulated between coin tosses. It’s not difficult to imagine a magnetized coin having its toss influenced by the application of invisible magnetic fields, for example.
If the “manipulation” is known and reasonably nice then a martingale (i.e., a fair game) can still be constructed by a generalized Dynkin formula.
You are not taking this into account:
http://en.wikipedia.org/wiki/Kelly_criterion
I agree with what previous comments have said: taking 1,000,000 to 1 odds you have everything to lose and essentially nothing to gain. I wouldn’t bet 1,000,000 to 1 on the sun rising if my maximum bet were limited to my net worth: the trouble of collecting the bet is not worth the few cents I would win.
Flipping the question around: what are the lowest odds at which you would take the bet? Did you take the bet at 2-to-1 odds?
I first want to second the above comments about betting not necessarily reflecting belief about the odds. I presume everyone here has health insurance, even though that means paying more than the expected cost (if you paid exactly the expected cost, the insurance company would go out of business). Variance matters, as does the absolute value of the worst option and the absolute value of the best option.
The other problem with answering this is that I have no internal sense of what
versus 
means. I am very certain that 
, but it is sufficiently unlikely that I can’t put an accurate number on it.
If someone proves P=NP (and, presumably, comes up with a solution for NP-complete problems), a lot of stuff that we rely on may change dramatically.
One example might be cryptography — if P=NP some of the cryptographic algorithms we rely on for, say, the protection of our money or our national security — our lives, in a sense — would become breakable. In this sense we’re all already betting with pretty high stakes that P!=NP, or at least that P=NP won’t be proved.
” if P=NP some of the cryptographic algorithms we rely on for, say, the protection of our money or our national security — our lives, in a sense — would become breakable. ”
No. see dick’s earlier post : http://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem/#more-2910
I’m surprised so few people have said what odds they’d be willing to take. I’ll restate mine: I’d take a small bet, at 10 to 1.
Note that there’s not much point in stating your bet anonymously: the whole point is to put as much skin in the game as possible. If you’re not willing to put even your full name to your (hypothetical) bet, then I don’t see why others should take you seriously.
This post makes the same mistake as your old “When Min-Max Is Wrong” by failing to take the expectation of utilities. I assume you are aware of the economic views in this matter — so may I ask why you *ignore* them? (I wouldn’t necessarily expect you to agree with that community’s view, of course, but ignoring it is odd.)
As for P vs NP, I would gladly go into a $1:$1000 bet. (But note, for instance, that I wouldn’t go into a $1000 : $1000000 bet.)
To clarify my position further, I would go into a $1 : $900 bet that finding a satisfying assignment for a circuit with n input wires and poly(n) size (say, n^5 for concreteness) takes 2^{n – o(n)} time. That is, the problem is not only exponential but it is very strongly exponential.
In my experience, the most interesting inconsistencies between human assessments of probabilities and betting behavior is most readily seen at lunch, with people of strong political views (any inclination will do), for small but painful stakes, reasonable odds, and short-term, easily resolvable events. Heck, sometimes I’ll make a proposition and offer to take EITHER side just to witness the discomfort.
I think this post is mainly related to an issue which is not about P=NP. It mainly demonstrates the illusion of being able to assign probabilities in many cases of uncertainty.
The realization that there are questions we can ask but cannot answer is quite shocking by itself. Trying to assign probabilities (even subjective probabilities) in cases of uncertainty widens a little the class of questions that we can answer (and reduces, of course, the quality and usefulness of the answers). But adding probabilities widen the class of questions we can answer only by a little, while enlarging the kind of questions we can ask by much.
Apropos how shocking it is to dicover that there are matters depending on luck, I remember playing once the game ‘Risk’ with a gifted 4 years old child who played as good as I did. The only difference between us was that when he did not like the outcome of the dices he blamed himself for not practicing dice rolling enough. So he did not understood that the outcomes are genuinly uncertain and are a matter of luck. Assigning probabilities works for dice rolling but for many questions involving uncertainty they make only little sense.
I agree to some extent. The issue I was trying to get across is the computer scientists are betting that P=NP is false in many ways, even though I would argue there is little real evidence. The betting is seen in funding—try to get funded to work on P=NP or even factoring—impossible. Also seen in what papers are favored in conferences, and so on. It also seen in the fraction of papers that would be wiped out if P=NP.
Also the bet is seen in the complete lack of any plan “B” for security if P=NP really was true.
Dear Dick,
Some sporadic comments: 1) When you tackle a problem, certainly a mathematical conjecture the belief on which direction is correct does not make a very big difference. If you want to prove a conjecture you investigate what a counter example will look like, when you try to disprove a conjecture you investigate what are the scope of methods which can prove it. Often you go back and force between the two directions even if you have a firm belief on what direction is correct.
2) It is true that the common belief (and also my belief) is that NP is not equal to P. You say that there little real evidence for this belief, what do you mean?
3) What do you mean by plan “B”?
Gil,
Thanks as always for your comments. As someone (you) who solved a famous open problem that all (most?) guessed the wrong way, I think you know what I am getting at. I think we need more of the “try both sides” of the P=NP question to finally make real progress.
Personally, I am not convinced by any of the current “evidence” that P=NP must be false. I think I will do whole post on what this consists of in the near future.
But it seems that the evidence is pretty weak: part is we have tried hard and failed; part is if P=NP in a practical way, then would be too powerful; part is there are thousands of “equivalent” statements of the problem; part is the problem has been open a long time.
All of this is evidence for sure that the problem is hard, fundamental, and is likely to require new and exciting insights to solve. But I do not see that it says which way the problem goes?
We certainly have collected enough evidence to state that it is unlikely there exists an O(n^2) algorithm for SAT, or even an O(n^k) algorithm for small k, for that matter.
People then wrongly infer from this that P=NP is unlikely. Most of the arguments against P=NP—such as “this is why theorem proving in math is hard”—hold equally well in a universe where SAT is Θ(n^100) .
I remain very much on the fence on this one.
What evidence is that? The SAT solver people would disagree, but perhaps you had some other evidence in mind.
I haven’t seen something evidence of the form “P=NP implies very unlikely event”, such as “there are more than 100 primes between 2^100 and 2^100 + 2^k” for k=~ 10. This statement is not prima-facie impossible, but given the distribution of primes numbers it is highly unlikely.
Rather what the “good evidence” against an O(n^2) algorithm for SAT is how well we have explored this space in search of a solution. This is not unlike the strong belief that it is unlikely Fermat had a short proof of his “theorem”.
I don’t see SAT solvers as evidence of an O(n^2) algorithm. They still run into some (rare) hard cases which seem very complex. On the other hand SAT solvers are weak empirical evidence in favor of P=NP.
If anyone is willing to put up $1,000, I would take 1,000 to 1 odds that P will not be proved equal to NP within the next 10 years. For clarity, if P is not proved equal to NP within the next ten years, you pay me $1K. If it is, I will pay you $1M. Any takers?
According to the Kelly criterion,
http://en.wikipedia.org/wiki/Kelly_criterion
assuming I think my odds of losing are (say) 1 in a million, I should give million to one odds only if I’m betting a small fraction of my bankroll. If I’m putting all my assets in one bet, I should give only even money, if I have it right.
Why not use a prediction market (e.g. something like InTrade)? Then, people can put their money where their mouth is.
If he were to lose $1m on a bet, his wife would probably kill him. Accordingly, a bet of $1m is equivalent to betting his life.
I wouldn’t bet my life because that would mean that I should commit myself to work on the problem among dust books till I die or prove a result. And I like sunbathing and stuff, you know.
Anyway My bet is 50:1 that PNP. Even of on a 2:1 bet, that would be a good chance to meet again your old pal, like Stephen Hawkins did when betting a porno magazine, if you catch my drift.
Sorry for two typos:
1) “dust” for “dusty”
2) Including HTML brackets as text where i should have written “P!=NP”
Lost bet there…
Luke G, why is 20:1 an upper limit? Is it the result of a kind of calculation? If not, I would have chosen a prime number like ehm… 19 or 23. They look SO MUCH better than unprimes, you know…
Big bets like this aren’t reasonable if you have to maintain a cash balance for a possible payout. I’d see no reason anyone would even give 100:1 odds, because even with certainty of winning, they’ve only increased their bankroll by 1% while having a lot of cash tied up over the course of the bet. I’m 99.9% sure P=NP won’t be proved, but I might only give 10:1 odds.
To get odds significantly higher than 20:1, you’d have to allow leveraging bets (i.e. betting more than the cash you have to keep on hand). Betting your life, as your title suggests, isn’t practical of course, but it sure would allow people to express more certainty 🙂
(Though I’m fairly certain P!=NP, I enjoy reading thoughts on P=NP. It’s always nice to think about things from other perspectives.)
From the ongoing responses I reach to the conclusion that Clay Institute’s award for “P vs NP” is not fair!
It should be
Award Prize (P=/NP) << Award Prize (P=NP)
I have a proto-argument that I’d like to make rigorous, one that maybe follows on from Gil Kalai’s point:
Suppose you are hazarding the probability of an event or assertion A, one like P vs NP or maybe one with more overt physical content, where:
(a) Your evidence is based on a finite information structure—the part of the word you can observe, and
(b) The truth value of A is the same in every possible “pocket universe”.
My contention is that the only scientifically meaningful probability you can assign is 0 or 1—*if* (c) cosmologists such as Alex Vilenkin are right that there are (countably) infinitely many (fully?) independent regions of space. Suppose you assign probability e > 0. By (a) and (c) the finite configuration on which your assignment is based gets infinitely many trials. Hence you must believe with statistical certainty that your configuration gives rise to A somewhere. But by (b), if A holds anywhere then it holds everywhere. So you must say e = 1.
Is this too far-out to be meaningful? At least (b) applies to “P != NP” since it’s a universal—maybe now we should say “multiversal”. From reading David Deutsch’s /The Fabric of Reality/ and related sources, I know there are serious efforts to use parallel universes to give denotation to conditional-probability [Bayesian] assertions.
This argument makes no objection to “betting” such as this post describes—over human lifetimes or longer. It only tries to obstruct making such betting into a scientific framework.
Love the idea. The problem I have is how do we apply this argument to any uncertain event? Like a coin toss?
Yes, that’s the rub. It could be applicable in quantum/cosmology domains, but I don’t know them well enough. So by “made rigorous” I meant more “made applicable”. (Also, “word” was a typo for “world”.)
A complexity-class example which I’ve observed to get a closer to 50-50 split when talking about it is TC^0 versus NC^1, say specifically the standard DLOGTIME-uniform versions of these classes. I think they’re equal, but there’s some de-randomization intuition for their being different—which someone related to me second-hand a few years ago, but we’ve been unable to reconstruct…!?
On an unrelated note: here are a few more arguments why bets at odds such a 10^6 to 1 are unlikely between rational agents:
1. Bounded rationality/Behavioral economics: I think the ratio between someone’s net worth and their mental cost of engaging in such a bet is a small constant << 10^6. Engaging is a bet where I will owe you a large sum of money involves deliberation, stress, estimation of odds, remembering the bet, etc., all of which have a mental cost. It will not be worth it for me if all I gain is a millionth of my current savings.
Of course I could be gaining other things such as the thrill of placing the bet, a good story to tell, etc.
2. Inability to estimate probabilities: our brains aren't good at assigning likelihoods to events when the probabilities are so small. For me 10^6 and 10^7 differ in the number of zeroes, but I don't really have a good intuitive sense of how many is 10^6. With likelihoods, it becomes even harder. So rationally, I shouldn't trust any likelihood of this kind that I come up with. Gut feeling can be trustworthy, but not at scales the gut is not evolved for.
Exception: if I compute the likelihood (say) by multiplying my estimates of something, I could have more confidence in them.
3. Events outside the scope of the bet: likelihood of other party being able to enforce the bet if I lose, your likelihood of other party being able to take my money even if I win, likelihood of the value of dollar collapsing, etc. become significant factors which may have more impact than the probability of the event itself.
These are also reasons why a prediction market cannot accurately work for such small probabilities: e.g. (1) if my gain from the bet is primarily non-monetary, the number that pops out from the bet is likely to be extremely error-prone.
While the above arguments as stated are for 10^6 to 1 odds, I personally think they remain largely valid even for C to 1, for a much smaller C (say 1000).
Prof Lipton–I will be happy to put up $100 that P = NP will not be proved in 10 years versus $1 maintaining the opposite. I think you have my contact info.
The betting is seen in funding—try to get funded to work on P=NP or even factoring—impossible.
I assume you have first- or second-hand evidence, so I can’t really argue. All I can say is that I would have no problem recommending to fund a proposal for factoring as long as the proposal made a clear case for what techniques would be tried, and why there is hope they would work. For that matter, I would say the same whether one was trying to prove P=NP or the opposite.
As many people have commented, asking the question in financial terms is problematic. But there is a simple measurement of a different kind of utility that can be seen in the behaviour of many computer scientists: the amount of time they are prepared to risk wasting.
By that I mean that if P=NP then devoting a huge amount of time to attempting to prove the opposite is giving up on other things that one could do with that time. (For simplicity I’ll ignore the fact that wonderful results have come out of failed attempts to prove that P does not equal NP.) So the fact that so many people are prepared to put so much effort into proving that P does not equal NP while making almost no effort at all to find a polynomial-time algorithm for SAT is an illustration of their confidence, and a better one than the amount of money they would be prepared to bet. It would be interesting to try to deduce from this behaviour what people’s subjective perception is of the probability that P=NP. I haven’t thought about how one might do that.
In a way, I’m not really saying anything different from what you are saying when you say that computer scientists are betting heavily on P not equalling NP.
As a final remark, I once worked very hard indeed on a problem in Banach spaces called the distortion problem. I had a heuristic argument in favour of a positive answer and devoted all my attempts to proving that. Eventually, Ted Odell and Thomas Schlumprecht found a counterexample. Two interesting features of this example were (i) that my attempts to prove a false result led me to build up a certain expertise that I was able to use for other problems, and (ii) that in this case the conventional wisdom was that the answer was negative, as indeed Odell and Schlumprecht showed it to be. Anyhow, that experience leaves me wary of putting all my eggs into one basket, though I have to say that with P and NP I go with the majority.
To conclude, I wouldn’t bother with a financial bet, but the ratio of time I would spend trying to prove that P=NP to the time I would spend trying to prove they are different is about 1:1000.
What did you feel when Odell and Schlumprecht have given an counterexample to your heuristic argument in favour of a positive answer ? In the absence of such an counterexample are you continue to work in favour of a positive answer ?
I felt slightly silly. I had hoped that there would be a rather general Ramsey principle that would imply a positive solution, and the example of Odell and Schlumprecht proved that that principle didn’t exist. I never understood their example well enough to get a good feel for why there should be a counterexample, beyond the fact that there was one.
Dick, your September 13th comment looks as though it’s addressed to me, when it in fact isn’t (since my comment was written three days later). I’m not sure why that is, or whether it’s possible to move yours.
I would bet my life to one dollar that sun will rise tomorrow. Why? Because if it does not, i am dead either way, and so are you.