It’s time someone said it. There exists, among a small but vocal subset of the nerd community, a strange animus against computational complexity theory, which is often rooted in factual misunderstandings, and seems wholly out of proportion to any real shortcomings that complexity theory has. Granted, every field of science has its backseat-drivers, those extralusionary intellects who feel sure they could best the experts, but haven’t expended any actual effort in solving the problems on which the experts are stuck. But, perhaps because of the unusual accessibility of its open problems, complexity theory seems (I might be wrong) to attract more such naysayers than other mathematical fields.
It goes without saying that no intellectual pursuit is automatically entitled to respect: it has to earn it by actual accomplishments. But even after complexity theory delivers spectacular accomplishments—from NP-completeness to PCPs to public-key cryptography to zero-knowledge proofs to quantum computing—the carping continues unabated. It’s this phenomenon that I’d like to understand better.
Here are the main manifestations of anti-complexitism that I’ve witnessed:
“Monday-morning quarterbacking” of complexity breakthroughs. For an example, see this thread on Lance and Bill’s blog, which is full of knowing comments seeking to minimize Ryan Williams’s recent NEXP vs. ACC breakthrough. Some of these comments are strangely off the mark: for example, the new result is taken to task for being “nonconstructive,” relying on the ability to perform diagonalization within the huge set NEXP. But we’ve known since Natural Proofs that, if you want to make progress on the P vs. NP question, then you’ll need “nonconstructive” techniques that seize on a special property of the function f being lower-bounded—and diagonalization remains one of the few examples of such a technique that we have. On the other hand, we’ve also known that, if you do use diagonalization, then you’ll need to combine it with some new ingredient to get around both the relativization and algebrization barriers. Ryan’s proof actually does all of that, which is why many of us are so excited about it.
Refusal to accept the incremental nature of complexity theory (which is shared by every other scientific field known to humankind). To me, one of the more humorous criticisms of Ryan’s breakthrough is that it “merely” shows NEXP is not in ACC, and not (for example) that the MAJORITY function is not in ACC. Granted, the statement NEXP⊄ACC is pathetically weak compared to what we believe is true. But then again, what have you done that’s advanced circuit complexity by 1% as much as this “pathetic” lower bound?
Fervent desire to see complexity theorists get their comeuppance from an “outsider.” The anonymous blog-commentariat’s pooh-poohing of the ACC breakthrough stands in contrast to the praise that same commentariat heaped on Vinay Deolalikar’s unsuccessful attempt at proving P≠NP a few months ago. Even though Vinay and Ryan are both academic researchers working at industry labs (HP and IBM respectively), from reading the comments, it appears part of the reason for the differing reactions is that Deolalikar was seen as more of an “outsider.” Now, I like to root for the underdog as much as the next American, but it’s worth remembering that every scientist starts as an outsider. It was only a decade ago that Ryan and I were both nerdy kids at Cornell, trying to get our respective crazy ideas taken seriously by professors. To paraphrase Niels Bohr, is a “scientific insider” anything more than an outsider who’s already made most of the egregious mistakes in some subfield?
Presenting obvious, universally-known limitations of asymptotic analysis as if they were new insights. Yes, I’m aware that a polynomial-time algorithm can be impractical because of huge constant factors or a whopping exponent. I’m aware that an NP-complete problem can be easy on those instances that arise in practice. Even if I have a debilitating brain injury, so that I no longer remember my own name or how to count to 10, I like to think that I’ll still be aware of these facts. To me, dismissing complexity theory because of its love affair with worst-case, asymptotic analysis is like dismissing physics because of its love affair with frictionless surfaces, point particles, elastic collisions, and ideal springs and resistors. In both cases, people make the simplifying assumptions not because they’re under any illusions that the world really is that way, but rather because their goal is understanding. And in both cases, the theory itself gives you the tools to complicate your model—to put legs and hooves on your spherical cow—until you get reasonably-accurate predictions for the practical problems that interest you. (See: D. E. Knuth, The Art of Computer Programming.)
Dismissal of complexity theory as “not real mathematics.” There’s no denying that complexity theory is young compared to (say) complex analysis, differential equations, or Lie groups. But if you were choosing an area to work on, why would that be a point against complexity? It means all the more to do and discover: instead of having the elegant, unifying theory presented to you in yellow books, you get to create it! Furthermore, we’ve seen that the connections between complexity theory and “traditional” areas of mathematics are as deep as people want to make them (and often deeper): in recent years, metric embeddings, elliptic curves, algebraic geometry, and arithmetic combinatorics have all played starring roles in complexity results. On the other hand, yes, sometimes you can achieve a complexity breakthrough the way Ryan did, not by using “deep” mathematics, but just by thinking incredibly hard about simple facts like fast matrix multiplication and the Time Hierarchy Theorem. Again, that’s a negative?
Attacks on complexity theory for over-reliance on conjectures, even though almost every field outside mathematics (and quite a few within mathematics) rely on conjectures as well. This one really gets me—and is the reason why I often point out that, if we complexity theorists were physicists, we would have declared P≠NP a law of nature decades ago, then looked back with pride on our far-reaching discovery about the workings of the universe. The problem of rigorously proving the No-SuperSearch Law would have been relegated to the mathematical physicists, much like the problem of proving the consistency of (3+1)-dimensional quantum field theory. Instead, because we complexity theorists have the custom of trumpeting what we can’t prove from the rooftops, we give our extralusionary friends the ammunition they need to regard us as dismal failures, should they so choose. “So you landed on the moon? How adorable. But tell me, why does that represent even the slightest progress toward the real goal of visiting other galaxies?” The response, which should be obvious, is that taunting mountain-climbers for being out-of-shape laggards works best when you’re at the peak of the mountain looking down at them, not at the base looking up. But then again, if you were climbing the mountain too, you’d be less likely to want to taunt other climbers, even those behind you: for then the competitive instincts common to all humans would have to contend with the feeling of being part of a great and difficult shared enterprise.