Out there in the wider world—OK, OK, among Luboš Motl, and a few others who comment on this blog—there appears to be a widespread opinion that P≠NP is just “a fashionable dogma of the so-called experts,” something that’s no more likely to be true than false. The doubters can even point to at least one accomplished complexity theorist, Dick Lipton, who publicly advocates agnosticism about whether P=NP.
Of course, not all the doubters reach their doubts the same way. For Lipton, the thinking is probably something like: as scientists, we should be rigorously open-minded, and constantly question even the most fundamental hypotheses of our field. For the outsiders, the thinking is more like: computer scientists are just not very smart—certainly not as smart as real scientists—so the fact that they consider something a “fundamental hypothesis” provides no information of value.
Consider, for example, this comment of Ignacio Mosqueira:
If there is no proof that means that there is no reason a-priori to prefer your arguments over those Lubos. Expertise is not enough. And the fact that Lubos is difficult to deal with doesn’t change that.
In my response, I wondered how broadly Ignacio would apply the principle “if there’s no proof, then there’s no reason to prefer any argument over any other one.” For example, would he agree with the guy interviewed on Jon Stewart who earnestly explained that, since there’s no proof that turning on the LHC will destroy the world, but also no proof that it won’t destroy the world, the only rational inference is that there’s a 50% chance it will destroy the world? (John Oliver’s deadpan response was classic: “I’m … not sure that’s how probability works…”)
In a lengthy reply, Luboš bites this bullet with relish and mustard. In physics, he agrees, or even in “continuous mathematics that is more physics-wise,” it’s possible to have justified beliefs even without proof. For example, he admits to a 99.9% probability that the Riemann hypothesis is true. But, he goes on, “partial evidence in discrete mathematics just cannot exist.” Discrete math and computer science, you see, are so arbitrary, manmade, and haphazard that every question is independent of every other; no amount of experience can give anyone any idea which way the next question will go.
No, I’m not kidding. That’s his argument.
I couldn’t help wondering: what about number theory? Aren’t the positive integers a “discrete” structure? And isn’t the Riemann Hypothesis fundamentally about the distribution of primes? Or does the Riemann Hypothesis get counted as an “honorary physics-wise continuous problem” because it can also be stated analytically? But then what about Goldbach’s Conjecture? Is Luboš 50/50 on that one too? Better yet, what about continuous, analytic problems that are closely related to P vs. NP? For example, Valiant’s Conjecture says you can’t linearly embed the permanent of an n×n matrix as the determinant of an m×m matrix, unless m≥exp(n). Mulmuley and others have connected this “continuous cousin” of P≠NP to issues in algebraic geometry, representation theory, and even quantum groups and Langlands duality. So, does that make it kosher? The more I thought about the proposed distinction, the less sense it made to me.
But enough of this. In the rest of this post, I want to explain why the odds that you should assign to P≠NP are more like 99% than they are like 50%. This post supersedes my 2006 post on the same topic, which I hereby retire. While that post was mostly OK as far as it went, I now feel like I can do a much better job articulating the central point. (And also, I made the serious mistake in 2006 of striving for literary eloquence and tongue-in-cheek humor. That works great for readers who already know the issues inside-and-out, and just want to be amused. Alas, it doesn’t work so well for readers who don’t know the issues, are extremely literal-minded, and just want ammunition to prove their starting assumption that I’m a doofus who doesn’t understand the basics of his own field.)
So, OK, why should you believe P≠NP? Here’s why:
Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false.
What kind of tests am I talking about?
By now, tens of thousands of problems have been proved to be NP-complete. They range in character from theorem proving to graph coloring to airline scheduling to bin packing to protein folding to auction pricing to VLSI design to minimizing soap films to winning at Super Mario Bros. Meanwhile, another cluster of tens of thousands of problems has been proved to lie in P (or BPP). Those range from primality to matching to linear and semidefinite programming to edit distance to polynomial factoring to hundreds of approximation tasks. Like the NP-complete problems, many of the P and BPP problems are also related to each other by a rich network of reductions. (For example, countless other problems are in P “because” linear and semidefinite programming are.)
So, if we were to draw a map of the complexity class NP according to current knowledge, what would it look like? There’d be a huge, growing component of NP-complete problems, all connected to each other by an intricate network of reductions. There’d be a second huge component of P problems, many of them again connected by reductions. Then, much like with the map of the continental US, there’d be a sparser population in the middle: stuff like factoring, graph isomorphism, and Unique Games that for various reasons has thus far resisted assimilation onto either of the coasts.
Of course, to prove P=NP, it would suffice to find a single link—that is, a single polynomial-time equivalence—between any of the tens of thousands of problems on the P coast, and any of the tens of thousands on the NP-complete one. In half a century, this hasn’t happened: even as they’ve both ballooned exponentially, the two giant regions have remained defiantly separate from each other. But that’s not even the main point. The main point is that, as people explore these two regions, again and again there are “close calls”: places where, if a single parameter had worked out differently, the two regions would have come together in a cataclysmic collision. Yet every single time, it’s just a fake-out. Again and again the two regions “touch,” and their border even traces out weird and jagged shapes. But even in those border zones, not a single problem ever crosses from one region to the other. It’s as if they’re kept on their respective sides by an invisible electric fence.
As an example, consider the Set Cover problem: i.e., the problem, given a collection of subsets S1,…,Sm⊆{1,…,n}, of finding as few subsets as possible whose union equals the whole set. Chvatal showed in 1979 that a greedy algorithm can produce, in polynomial time, a collection of sets whose size is at most ln(n) times larger than the optimum size. This raises an obvious question: can you do better? What about 0.9ln(n)? Alas, building on a long sequence of prior works in PCP theory, it was recently shown that, if you could find a covering set at most (1-ε)ln(n) times larger than the optimum one, then you’d be solving an NP-complete problem, and P would equal NP. Notice that, conversely, if the hardness result worked for ln(n) or anything above, then we’d also get P=NP. So, why do the algorithm and the hardness result “happen to meet” at exactly ln(n), with neither one venturing the tiniest bit beyond? Well, we might say, ln(n) is where the invisible electric fence is for this problem.
Want another example? OK then, consider the “Boolean Max-k-CSP” problem: that is, the problem of setting n bits so as to satisfy the maximum number of constraints, where each constraint can involve an arbitrary Boolean function on any k of the bits. The best known approximation algorithm, based on semidefinite programming, is guaranteed to satisfy at least a 2k/2k fraction of the constraints. Can you guess where this is going? Recently, Siu On Chan showed that it’s NP-hard to satisfy even slightly more than a 2k/2k fraction of constraints: if you can, then P=NP. In this case the invisible electric fence sends off its shocks at 2k/2k.
I could multiply such examples endlessly—or at least, Dana (my source for such matters) could do so. But there are also dozens of “weird coincidences” that involve running times rather than approximation ratios; and that strongly suggest, not only that P≠NP, but that problems like 3SAT should require cn time for some constant c. For a recent example—not even a particularly important one, but one that’s fresh in my memory—consider this paper by myself, Dana, and Russell Impagliazzo. A first thing we do in that paper is to give an approximation algorithm for a family of two-prover games called “free games.” Our algorithm runs in quasipolynomial time: specifically, nO(log(n)). A second thing we do is show how to reduce the NP-complete 3SAT problem to free games of size ~2O(√n).
Composing those two results, you get an algorithm for 3SAT whose overall running time is roughly
$$ 2^{O( \sqrt{n} \log 2^{\sqrt{n}}) } = 2^{O(n)}. $$
Of course, this doesn’t improve on the trivial “try all possible solutions” algorithm. But notice that, if our approximation algorithm for free games had been slightly faster—say, nO(log log(n))—then we could’ve used it to solve 3SAT in $$ 2^{O(\sqrt{n} \log n)} $$ time. Conversely, if our reduction from 3SAT had produced free games of size (say) $$ 2^{O(n^{1/3})} $$ rather than 2O(√n), then we could’ve used that to solve 3SAT in $$ 2^{O(n^{2/3})} $$ time.
I should stress that these two results have completely different proofs: the approximation algorithm for free games “doesn’t know or care” about the existence of the reduction, nor does the reduction know or care about the algorithm. Yet somehow, their respective parameters “conspire” so that 3SAT still needs cn time. And you see the same sort of thing over and over, no matter which problem domain you’re interested in. These ubiquitous “coincidences” would be immediately explained if 3SAT actually did require cn time—i.e., if it had a “hard core” for which brute-force search was unavoidable, no matter which way you sliced things up. If that’s not true—i.e., if 3SAT has a subexponential algorithm—then we’re left with unexplained “spooky action at a distance.” How do the algorithms and the reductions manage to coordinate with each other, every single time, to avoid spilling the subexponential secret?
Notice that, contrary to Luboš’s loud claims, there’s no “symmetry” between P=NP and P≠NP in these arguments. Lower bound proofs are much harder to come across than either algorithms or reductions, and there’s not really a mystery about why: it’s hard to prove a negative! (Especially when you’re up against known mathematical barriers, including relativization, algebrization, and natural proofs.) In other words, even under the assumption that lower bound proofs exist, we now understand a lot about why the existing mathematical tools can’t deliver them, or can only do so for much easier problems. Nor can I think of any example of a “spooky numerical coincidence” between two unrelated-seeming results, which would’ve yielded a proof of P≠NP had some parameters worked out differently. P=NP and P≠NP can look like “symmetric” possibilities only if your symmetry is unbroken by knowledge.
Imagine a pond with small yellow frogs on one end, and large green frogs on the other. After observing the frogs for decades, herpetologists conjecture that the populations represent two distinct species with different evolutionary histories, and are not interfertile. Everyone realizes that to disprove this hypothesis, all it would take would be a single example of a green/yellow hybrid. Since (for some reason) the herpetologists really care about this question, they undertake a huge program of breeding experiments, putting thousands of yellow female frogs next to green male frogs (and vice versa) during mating season, with candlelight, soft music, etc. Nothing.
As this green vs. yellow frog conundrum grows in fame, other communities start investigating it as well: geneticists, ecologists, amateur nature-lovers, commercial animal breeders, ambitious teenagers on the science-fair circuit, and even some extralusionary physicists hoping to show up their dimwitted friends in biology. These other communities try out hundreds of exotic breeding strategies that the herpetologists hadn’t considered, and contribute many useful insights. They also manage to breed a larger, greener, but still yellow frog—something that, while it’s not a “true” hybrid, does have important practical applications for the frog-leg industry. But in the end, no one has any success getting green and yellow frogs to mate.
Then one day, someone exclaims: “aha! I just found a huge, previously-unexplored part of the pond where green and yellow frogs live together! And what’s more, in this part, the small yellow frogs are bigger and greener than normal, and the large green frogs are smaller and yellower!”
This is exciting: the previously-sharp boundary separating green from yellow has been blurred! Maybe the chasm can be crossed after all!
Alas, further investigation reveals that, even in the new part of the pond, the two frog populations still stay completely separate. The smaller, yellower frogs there will mate with other small yellow frogs (even from faraway parts of the pond that they’d never ordinarily visit), but never, ever with the larger, greener frogs even from their own part. And vice versa. The result? A discovery that could have falsified the original hypothesis has instead strengthened it—and precisely because it could’ve falsified it but didn’t.
Now imagine the above story repeated a few dozen more times—with more parts of the pond, a neighboring pond, sexually-precocious tadpoles, etc. Oh, and I forgot to say this before, but imagine that doing a DNA analysis, to prove once and for all that the green and yellow frogs had separate lineages, is extraordinarily difficult. But the geneticists know why it’s so difficult, and the reasons have more to do with the limits of their sequencing machines and with certain peculiarities of frog DNA, than with anything about these specific frogs. In fact, the geneticists did get the sequencing machines to work for the easier cases of turtles and snakes—and in those cases, their results usually dovetailed well with earlier guesses based on behavior. So for example, where reddish turtles and bluish turtles had never been observed interbreeding, the reason really did turn out to be that they came from separate species. There were some surprises, of course, but nothing even remotely as shocking as seeing the green and yellow frogs suddenly getting it on.
Now, even after all this, someone could saunter over to the pond and say: “ha, what a bunch of morons! I’ve never even seen a frog or heard one croak, but I know that you haven’t proved anything! For all you know, the green and yellow frogs will start going at it tomorrow. And don’t even tell me about ‘the weight of evidence,’ blah blah blah. Biology is a scummy mud-discipline. It has no ideas or principles; it’s just a random assortment of unrelated facts. If the frogs started mating tomorrow, that would just be another brute, arbitrary fact, no more surprising or unsurprising than if they didn’t start mating tomorrow. You jokers promote the ideology that green and yellow frogs are separate species, not because the evidence warrants it, but just because it’s a convenient way to cover up your own embarrassing failure to get them to mate. I could probably breed them myself in ten minutes, but I have better things to do.”
At this, a few onlookers might nod appreciatively and say: “y’know, that guy might be an asshole, but let’s give him credit: he’s unafraid to speak truth to competence.”
Even among the herpetologists, a few might beat their breasts and announce: “Who’s to say he isn’t right? I mean, what do we really know? How do we know there even is a pond, or that these so-called ‘frogs’ aren’t secretly giraffes? I, at least, have some small measure of wisdom, in that I know that I know nothing.”
What I want you to notice is how scientifically worthless all of these comments are. If you wanted to do actual research on the frogs, then regardless of which sympathies you started with, you’d have no choice but to ignore the naysayers, and proceed as if the yellow and green frogs were different species. Sure, you’d have in the back of your mind that they might be the same; you’d be ready to adjust your views if new evidence came in. But for now, the theory that there’s just one species, divided into two subgroups that happen never to mate despite living in the same habitat, fails miserably at making contact with any of the facts that have been learned. It leaves too much unexplained; in fact it explains nothing.
For all that, you might ask, don’t the naysayers occasionally turn out to be right? Of course they do! But if they were right more than occasionally, then science wouldn’t be possible. We would still be in caves, beating our breasts and asking how we can know that frogs aren’t secretly giraffes.
So, that’s what I think about P and NP. Do I expect this post to convince everyone? No—but to tell you the truth, I don’t want it to. I want it to convince most people, but I also want a few to continue speculating that P=NP.
Why, despite everything I’ve said, do I want maybe-P=NP-ism not to die out entirely? Because alongside the P=NP carpers, I also often hear from a second group of carpers. This second group says that P and NP are so obviously, self-evidently unequal that the quest to separate them with mathematical rigor is quixotic and absurd. Theoretical computer scientists should quit wasting their time struggling to understand truths that don’t need to be understood, but only accepted, and do something useful for the world. (A natural generalization of this view, I guess, is that all basic science should end.) So, what I really want is for the two opposing groups of naysayers to keep each other in check, so that those who feel impelled to do so can get on with the fascinating quest to understand the ultimate limits of computation.
