Obama and P=NP
A stimulus package for p=np
Barack Obama is not a computer scientist, of course, but is the President of the United States. He just signed a bill that will spend $787 billion dollars to help get the United States economy going again. I know that we all hope that he is successful and somehow the economy, the country, and the world get back to “normal”.
My question today, following my previous post on a “stimulus package” for P=NP is should the government spend even ten’s of millions of dollars on research into the P=NP question? I believe that the answer is yes. I know that many of you may disagree. I thought that today I would at least raise some of the main reasons that I believe that we should have a P=NP stimulus package. I will elaborate on my position later on, but for now I want to make a few key points. (I have to teach my class soon )
I can think of many reasons why such a package would be a good idea. First, the P=NP question is a fundamental question about what we can or cannot do. Let’s imagine for the moment that there is a practical polynomial time algorithm for SAT, i.e. that P does equal NP. Then, there would be immense value in finding such an algorithm. There is even a national security issue. What if we do not discover the algorithm first, but another country does. There would be immense negative security consequences to this.
Okay. Perhaps most of you believe that this is a very unlikely scenario. Perhaps it’s a million to one. However, the cost to us would be trillions of dollars, so even at these odds one could justify spending quite a bit on P=NP research. The famous Adi Shamir (the A in RSA) recently stated at a public meeting that he thought cryptography as we know it would soon be over. His point was that Chinese computer scientists were working hard on breaking public key systems, and he thought that they might succeed in the next ten years. To me that is a scary thought and alone would justify spending a large sum of money on a research agenda. Note, the Chinese, just a few years back, shocked the crypto community with their result that broke the SHA-1 hash function.
A second reason for the stimulus package is not that a team is likely to solve the P=NP question. Questions like P=NP cannot be broken down into pieces and contracted out. You may be able to do this on some large science problems, but I do not see how one could do that on this problem. However, while hard open problems are usually solved by one researcher, they do need a community around them. Such communities require support, and that requires dollars.
Here are some concrete examples to make my point:
Hilbert’s Ten Problem
Yuri Matiyasevich solved this problem. He built on the work of Julia Robinson, Martin Davis, and Hilary Putnam. He did the last critical step, but without their work he might not have solved the problem at all. We will never know.
Fermat’s Last Theorem
Andrew Wiles solved the problem after years working alone in his attic. But he could not have done it without Frey first suggesting the connection between Fermat and elliptic curves. He also need Serre and then Ribert for showing that Frey was right. He needed many proof checkers to help find the gap in his first attempt. And finally he heed the help of his old student Richard Taylor to fill in the gap of his first incorrect proof. All of this could only work because a collection of people were thinking about the problem, were experts on the mathematical technology that he used, and were able to think about Fermat. Yes Wiles solved it, but I think it can be argued that it took a community to resolve the problem.
Three Dimensional Poincare Conjecture
Grigori Perelman wrote a series of papers in 2002 and 2003 that proved this famous conjecture. His proof used mathematical technology that was initially created by Richard Hamilton. Hamilton used the idea of the Ricci flow as a way to “smooth” out a manifold. Perelman work required many mathematicians to fill in the details left “to the reader” by Perelman. This required a strong community that understood the Ricci flow methods and much more.
There is no assurance that spending extra money will solve the P=NP. But there are many reasons for supporting additional research on this important problem. I would like to see the theory community get more resources that could potentially accelerate its solution. In any event some of the $787 billion dollars will no doubt be spent on less worthy things.