Why Believe That P=NP Is Impossible?
A list of reasons for believing that P=NP is impossible
David Letterman is not a theorist, but is a famous entertainer. I do not watch his show—on too late, but I love to read his jokes in the Sunday New York Times. He is of course famous for his “lists” of the top ten reasons for
Today I plan to follow David and try to list the top reasons why people believe that PNP. I am not planning on being funny—I have tried to faithfully capture some of reasons that people give for believing this.
The list I have put together has many reasons: they range from solid theorems, to social, to analogies to other mathematical areas, to intuition. I have tried to be inclusive—if you have additional reasons please let me know.
One thing that is missing from my list is experimental evidence. A list for the Riemann Hypothesis might include the vast amount of numeric computation that has been done. Andrew Odlyzko has done extensive computation on checking that the zeroes of the zeta function lie on the half-line—no surprise yet. Unfortunately, we do not seem to have any computational evidence that we can collect for the P=NP question. It would be cool if that were possible.
It may be interesting to note, that numerical evidence in number theory, while often very useful, has on occasion been wrong. One famous example, concerns the sign of the error term in the Prime Number Theorem: It was noticed that is never positive for even fairly large ; hence, the conjecture arose that
is impossible. Here are the number of primes less than , and is equal to
This would have been an interesting fact, but John Littlewood proved a wonderful theorem that showed that not only was possible, but that took on both positive and negative signs infinitely often. At first the bounds were huge for the first so that , today I believe it still is open what is an explicit .
Belief vs Proof
As scientists, especially theorists and mathematicians, what does it mean to believe X when there is no proof that X is true? I think that there are plausible reasons that you may or may not believe something like PNP without any proof—I plan to list some of those in a moment. But at some level beliefs are unique to each individual, perhaps the sum total of all their personal experiences.
However, I think that listing potential reasons for believing an unproved statement X can help guide a field. As I posted earlier, if the theory field is really convinced that P=NP is impossible, then this conviction will be manifest itself in many ways: what is funded, what is published, and what is thought about.
While this is a reasonable use of a belief, there are some dangers. The main danger is that if the belief is wrong, then there can be negative consequences. If most believe that some unproved X is true, then:
- Few may work on disproving X, which could potentially delay the final resolution of the problem.
- The field may build an edifice that is deep and rich based on X, but the foundation is faulty. If many theorems of the form: “If X, then Y” are proved, then when X is finally disproved a great deal of hard work will become vacuous.
- Finally, even if X is true, by thinking about both X and its negation, the field may discover other nuggets that would otherwise have been missed.
Three Choices, Not Two
Before I present the list I want to be clear that in my mind there are three choices—actually there are many more as I have pointed out before, but let’s stick to three:
- PNP: Let this mean that P is really equal to NP, that there is a practical polynomial time algorithm for SAT. Note, even this does not imply there are practical algorithms for all of NP, since the running time depends on the cost of the reduction to SAT.
- PNP: Let this mean that there is a polynomial time algorithm for SAT, but the exponent is huge. Thus, as a theory result, P does equal NP, but there is no practical algorithm for SAT.
- PNP: This will mean that there is no polynomial time algorithm for any NP-complete problem.
As I pointed out in my previous post there are even other possibilities. But let’s keep things manageable and only use these three for today.
A “Why PNP is Impossible” List
Here are some of the reasons that I have heard people voice for why they believe that PNP is impossible:
- PNP would be too good to be true. Some have said that it would end human creativity.
- PNP would imply that thousands of NP-complete problems are all in P. Since they are “different” problems, the argument is that it is hard to believe there is a universal method to solve all of them.
- PNP would put an end to modern cryptography, which is based on even stronger assumptions than PNP.
- PNP would go against results that are known already for finite automata and pushdown automata. In the first case nondeterminism can help decrease the state size exponentially; in the latter case, nondeterminism adds power to pushdown automata.
- PNP would go against known results from recursion theory. In particular, the analog of the polynomial time hierarchy is the arithmetic hierarchy, which is known to be strict.
- PNP would go against known results from set theory. In particular, the analog of the polynomial time hierarchy is the strict hierarchy of descriptive set theory. Mike Sipser did some pretty work on this connection.
- PNP would make for some . The brilliant work of Wolfgang Paul, Nick Pippenger, Endre Szemerédi and William Trotter shows that , which is a far distance from proving that there is no , but it at least shows that is impossible. That is nondeterminism does help for Turing Machines.
- PNP would show that there is a general search method that is much better than brute force. For SAT, for example, the best known results are that -SAT can be solved in exponential time . Rainer Schuler, Uwe Schöning,, Osamu Watanabe have a beautiful algorithm with a upper bound, while the best is around .
- PNP would imply that tautologies could be checked in polynomial time. There are beautiful results for specific logics, such as resolution, that prove exponential lower bounds on the proof length of tautologies. There are also lower bounds on even stronger logics: polynomial calculus, cutting planes, and constant-depth Frege systems. See this for a paper by Pavel Pudlák on such results.
- PNP would imply that thousands of NP-complete problems are all in P. These problems have been attacked by very different people, with different backgrounds and tools. The fact that no one has found a polynomial time algorithm for any of the problems is strong evidence that there is no such algorithm.
A Comment On The List
I do want to point out that the some of the list would change if we replace PNP by PNP. For example:
- PNP would be not too good to be true, since no practical use could be made of the result.
- PNP would not put an end to modern cryptography—crypto-systems would still be safe.
What are your major reasons for believing PNP is impossible? Have I missed some interesting reasons?
Some people would include observations like: no one has found an algorithm for PNP, so it is unlikely to exist. I find this pretty weak—science problems can be open for a long time, and further why is this biased towards PNP and not other possibilities. Scott Aaronson’s own take on a list includes reasons like this.
Another reason mentioned sometimes is PNP would help solve all problems. Note, this is not true for PNP, and even if PNP the encoding of your question could be impractical. For example, consider the encoding of the question into SAT: Is there a formal proof of the Riemann Hypothesis in Peano Arithmetic of length at most bits? This is about the length of a pretty complex proof, and the encoding of such a problem might be impossible even if PNP.
I would like to give a special thanks to Paul Beame, Jonathan Katz, and Michael Mitzenmacher for their kind help with this post. As always any errors are mine, and any good insights are theirs.
Finally, this is the post of this blog, and I would like to thank all of you who read it. Thank you very much. Powers of two are very important to computer scientists, but there will not be another power of ten for a long time. So thanks again.