Insider Baseball and P=NP

One consequence of p=np

Rich DeMillo is the past Dean of the College of Computer at Georgia Tech. He is also the past CTO of Hewlet-Packard–actually, he was also their first CTO. He is a famous computer security expert and expert software engineer. He was my boss–till recently–so I will not have to be so careful what I say about him. By the way CTO is not the Chief Theory Officer, but the Chief Technology Officer. As CTO he was no doubt the only one in the country (the world?) of a huge company that has a “lifetime” membership to the Journal of Symbolic Logic.

A Consequence of P=NP

One of Rich’s favorite comments is “that’s insider baseball.” When we talk about the impact of some planned research, he might say: “that’s just insider baseball.” As you might have guessed he is an avid baseball fan, especially loves the Yankees. (As a long time Met fan this is hard to type.) Clearly, research results with a inward impact–insider baseball– are not as desired as those with a outward impact. So if you wanted, when he was Dean, to get support from the College of Computing you had to avoid the insider baseball tag.

There are many potential consequences of a proof that P=NP, and I will discuss many of them in other posts. You may have guessed that one is a kind of “insider baseball” consequence. A proof that P=NP would destroy about half of all the research done in the last two decades in computer theory. About half of all published research papers, half of all Ph.D. theses, half of all books published in computer science, and more would be relics. They would be useless. Work that thousands of scientists the world over have toiled for years to prove would disappear overnight.

I find this possibility cool yet scary. On the one hand, it would be cool to see our field change so dramatically. Clearly, such a change would also open many new research directions. On the other hand, such a dramatic event would destroy the work of many. It would make “famous” theorems uninteresting, it would obsolete papers, theses, and books. Such a change would be unprecedented in science.

Some might say that this change is a kind of “insider baseball” issue. This has a certain amount of true to it. The biggest immediate losers would be theory researchers. The initial disaster would be felt most by my friends and colleagues. However, I think that the effect would potentially be much wider than that. I think that Rich might agree that it would be much more than just insider baseball. Of course not just researchers would be affected. Funding agencies like NSF and Darpa would have to completely redirect their research portfolios. They would have to fundamentally change what they fund.

I believe that this type of consequence of P=NP sets our problem aside from even the most important open problems from other fields. For example, many consider the Riemann Hypothesis as one of the most important problems in all of mathematics. However, I would argue that no matter how important a solution to the Riemann Hypothesis would be, it would not obsolete so much of mathematics. A solution would not destroy the work of thousands of researchers, thus it would not have the same type of impact as a solution to P=NP. This certainly, is the case with the recent solution to the Poincare Conjecture by Perelman. His solution has opened many doors, but it did not destroy the work of thousands of researchers. P=NP is unique in this regard.

Open Problems

As long as the CW is that P is not equal to NP there is little interest in preparing for the “arrival” of a proof that P=NP. I claim that this is at best naive, and at worst stupid. We should, in my opinion, start to examine what happen if there was a proof that P=NP. This could potentially be quite cool research. One example question is: can we make crypto-systems safe if P=NP? If P=NP the systems in use today all are broken, so it seems reasonable to start to plan for their replacement. Even if you think that P=NP is unlikely, it could happen.

A last point. Even if someone proved that P=NP but the proof yielded a completely impractical algorithm I think the effect would be tremendous. First, for instance, a security person would worry that the algorithm could eventually be made practical. So even an algorithm that was terrible would change the landscape completely. Second, how could one stand up in front of an audience at a theory conference and talk about an approximation algorithm to an NP-hard problem? It might be the case that the approximation algorithm was really fast, but the impact of the talk would be weaker. Today we can say “…since it’s NP-hard we must turn to an approximation approach…” In a future with P=NP what would we say?