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 to .
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.
The open problem is what odds would you give? Would you bet a million to one? Would you bet your life?