Theory Has Bet On P=NP
Theory has made a bet that PNP in many ways.
Pierre-Simon Laplace, was a famous mathematician from the century, who is known for many things. How about having a transform named after you—the Laplace transformation—pretty cool.
Today I want to discuss our version of his question: “What is the probability that the sun will rise tomorrow?” Our question is: what is the probability that P=NP? Okay, it not really the same as his question, but it is an interesting question.
You Bet Your Life?
I raised the issue of what is the right bet about P=NP in my recent post. There was a great deal of discussion, which was extremely interesting. I thank everyone who was kind enough to make a comment.
The central discussion, however, I think moved over to a discussion of beliefs vs. betting. This is a cool topic, but not exactly what I had in mind. I am not really interested in starting a betting pool on P=NP. I did want to make this point:
Theory, as a field, has placed a bet that P=NP is impossible.
Here is how the field makes that bet every day:
Money: Try sending a proposal to NSF, for example, and state that you wish to work on proving P=NP. Or even a weaker goal, that you wish to look at the possibility that factoring is in P. The chances that you will get funded are close to zero.
I tried an experiment a few years back: I wrote a reasonable—in my opinion—proposal on attacks on factoring. I am still thinking about them, and have posted on one of my ideas. The proposal got dollars. Perhaps it was poorly written, or perhaps the funds were tight that year, or perhaps my ideas were stupid, all that could have been true. But, the written reviews made it clear that I could not be funded without a “partial result.” If I had a partial result, then I probably would not need NSF funding. You either can factor or cannot factor.
The point is the field has made a huge bet that P is not equal to NP through the types of proposals that are funded. If P=NP is really closer to , then I would argue that more dollars should flow into different projects.
Eye Balls: Try sending a paper to a conference that goes against the conventional wisdom that P=NP is impossible—I think you will get nowhere. The same for journals or other places that control what we get to see. Again I think that the field has made a bet; the bet is that such papers are uninteresting. For example, would a paper that assumed that factoring was easy and then derived consequences of this assumption get attention? I think that it would not.
Mind Share: Try getting people to think out-of-the-box about P=NP, it’s hard. I started this blog mostly to do just that. I am happy that people seem to enjoy the blog; however, I would like people to think about P=NP in a serious way.
Just the other week Princeton/IAS held a meeting on Barriers in Computational Complexity. The organizers and the speakers consisted of some of the best theorists in the world. I really wish I could have been there to hear such top researchers speak on their work. However, my understanding is that the tone of the meeting was:
“How can we finally prove what we already know is true.”
My student Shiva Kintali, who was at the meeting, had two cool comments to report. The first was, One speaker mentioned that once a Nobel prize winner in physics was asked “if you can ask one bit of information from an all-powerful alien what would you ask ?” He said “I would ask if P=NP.” At this point many people in the audience said,
“We all know that bit, all we need is a proof.”
This was surprising to Shiva. The second was that in almost every panel discussion, everybody unanimously said “I believe P NP, since a world with P=NP would be hard to imagine.” The most common reason they believed P=NP is impossible, Shiva says, is that in this world, creativity would be automated.
That is a pretty strong bet that P=NP is impossible. They may be right, but let’s at least agree that they are making a strong bet.
National Security: Try getting security people to worry about a classic factoring algorithm. Good luck. I think there are national security issues here—by “national” I mean more than the US. Any country’s safety and economy is potentially at risk.
What if the “wrong people” figure out how to factor, or how to compute discrete logarithm, or in general how to solve hard problems, what will the consequences be? I think at a minimum there should be plans on how to react quickly if modern cryptography is destroyed.
This is another implicit bet. If you think that it is impossible that P=NP, then you will not plan for the failure of your crypto assumptions. Is this not a bet of a million to one? I say this because the consequences of a failure could cost hundreds of billions, perhaps trillions—the latter if national security is compromised.
I wanted to point out that we do bet every day on P=NP, whether we realize it or not. I think that given the potential for many outcomes to the P=NP question, we should be more open minded about the computational world. As I have pointed out P=NP could be true and have nothing to do with “automating creativity,” or be a practical algorithm. But it still could true.