More often than I can remember, I’ve been asked some form of the following question: “If you computer scientists can’t prove P=NP or P!=NP, then why aren’t we justified in believing whichever one we want? And why is the ‘consensus’ that P!=NP anything more than a shared prejudice — something you repeat to each other so your work won’t seem irrelevant?”
It’s time to assume the mantle of Defender of the Faith. I’m going to give you ten arguments for believing P!=NP: arguments that are pretty much obvious to those who have thought seriously about the question, but that (with few exceptions) seem never to be laid out explicitly for those who haven’t. You’re welcome to believe P=NP if you choose. My job is to make you understand the conceptual price you have to pay for that belief.
Without further ado:
- The Obvious Argument. After half a century, we still don’t know any algorithm for an NP-complete problem that runs in subexponential time. For Circuit-SAT, the canonical NP-complete problem, we don’t know any algorithm essentially better than brute-force search. In math, if decades of research fail to turn up an object, and there’s no a priori reason to suppose the object exists, it’s usually a good strategy to conjecture that the object doesn’t exist. We can all list counterexamples to this thesis, but the examples are much more numerous (though usually less famous, for obvious reasons).
- The Empirical Argument. While the argument based on decades of mathematical work can stand on its own, in the case of P versus NP we also have half a century of evidence from the computer industry. In a few cases — like linear programming and primality testing — people wanted fast ways to solve a problem in practice, and they came up with them, long before the problem was proved to be tractable theoretically. Well, people certainly want fast ways to solve NP-complete problems in practice, and they haven’t been able to invent them. The best-known satisfiability algorithms — such as DPLL, GSAT, and Survey Propagation — work surprisingly well on certain instance distributions, but croak (for example) on instances derived from factoring or automated theorem proving.
- The Bayesian Argument. Why can’t we turn the last two arguments on their heads, and say that, if our failure to find a fast SAT algorithm is evidence that P!=NP, then our failure to prove P!=NP is likewise evidence that P=NP? The answer is, because lower bounds are harder to prove than upper bounds. Assuming P=NP, it’s difficult to come up with a good reason why an efficient algorithm for NP-complete problems wouldn’t yet have been discovered. But assuming P!=NP, we understand in great detail why a proof hasn’t yet been discovered: because any proof will need to overcome specific and staggering obstacles. It will need to “know” how 3SAT differs from 2SAT, how quadratic programming differs from linear programming, and how approximating set cover within o(log|S|) differs from approximating it within log|S|. It will need to “look inside” computations in a way that doesn’t relativize. It will need to argue that NP-complete problems are hard, not because they look like random Boolean functions, but because they don’t look like random Boolean functions. While we have no reason to think such a proof is impossible — indeed, we have proofs satisfying some of the desiderata — we do have reason to think it will be extremely difficult.Whatever your “naïve prior probability” was that P=NP, the above considerations, together with Bayes’ Rule, suggest revising it downward.
- The Multiple-Surprises Argument. Here’s a point that’s not often stressed: for P to equal NP, not just one but many astonishing things would need to be true simultaneously. First, factoring would have to be in P. Second, factoring would have to be as hard as breaking one-way functions. Third, breaking one-way functions would have to be as hard as solving NP-complete problems on average. Fourth, solving NP-complete problems on average would have to be as hard as solving them in the worst case. Fifth, NP would have to have polynomial-size circuits. Sixth, NP would have to equal coNP. And so on. Any one of these statements, by itself, would overturn much of what we think we know about complexity.
- The Hierarchy Argument. This argument goes back to the early days of P versus NP. We know that P is strictly contained in EXP by the time hierarchy theorem. It follows that either P is strictly contained in NP, or NP is strictly contained in PSPACE, or PSPACE is strictly contained in EXP. Likewise, since NL is strictly contained in PSPACE=NPSPACE by the space hierarchy theorem, either NL is strictly contained in P, or P is strictly contained in NP, or NP is strictly contained in PSPACE. But if some of these separations hold, then why not all of them? To put the point differently, we know that collapse is not the general rule of the Complexity Zoo: even between P and EXP, there really are infinitely many distinct species. Indeed for some pairs of species, like E and PSPACE, we know they’re not equal even though we don’t know if either one contains the other! The burden of evidence, then, is on those who believe that two seemingly-distinct species are the same, not on those who believe they’re different.
- The Known-Algorithms Argument. We do have nontrivial efficient algorithms for several problems in NP, such as matching, stable marriage, minimum spanning tree, matrix inversion, planarity testing, and semidefinite programming. But every one of these algorithms depends, in a crucial way, on some special combinatorial or algebraic structure of the problem being solved. Is this just a fancy way of repeating that we don’t know yet how to solve NP-complete problems? I don’t think it is. It’s possible to imagine a situation where we knew “generic” techniques for achieving exponential speedups, which worked for objects as complicated as Turing machines, and the only problem was that we didn’t yet know how to apply those techniques to prove P=NP. But this is nothing like the actual situation.
- The Known-Lower-Bounds Argument. It could be that the dream of proving superpolynomial lower bounds on circuit size is no more than that: a pipe dream. But the fact remains we can prove superpolynomial lower bounds, albeit in weaker models of computation that are easier to analyze. To give some examples, superpolynomial lower bounds have been proven on the sizes of resolution proofs, monotone circuits, constant-depth circuits, read-once branching programs, and multilinear formulas.
- The Self-Referential Argument. If P=NP, then by that very fact, one would on general grounds expect a proof of P=NP to be easy to find. On the other hand, if P!=NP, then one would on general grounds expect a proof of P!=NP to be difficult to find. So believing P!=NP seems to yield a more ‘consistent’ picture of mathematical reality.
- The Philosophical Argument. If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)
- The Utilitarian Argument. Suppose you believe P!=NP. Then there are only two possibilities, both of which are deeply gratifying: either you’re right, or else there’s a way to solve NP-complete problems in polynomial time. (I realize that I’ve given a general argument for pessimism.)
There are several questions that the above arguments don’t pretend to address: first, why is P versus NP a reasonable question? Second, even if P!=NP, why should we expect there to be a proof in ZF set theory? Third, even if there is a proof, why should we expect it to be within reach of the human intellect? I’m really not cut out for this C. S. Lewis role, but look for further installments of Mere Complexity as the need arises…