The Philosophy of Computational Complexity

Tyler Cowen asks: Has there been progress in philosophy? He cheats a bit, pointing mainly to progress in science in his 16 answers. Perhaps that is the point.

Philosophy's successes rapidly create new fields, leaving them only to tackle the new frontier. So over time it appears they've done no work. I am sympathetic to this view, and some AI researcher friends of mine also occasionally feel similarly aggrieved as their successes spawn new fields (search, vision, natural language processing), but they are left hanging the bag marked 'problems on which we've made no progress'.

I like Tyler's 16 answers (some more than others), but I think there's a 17th significant omission, which is the tremendous advances we've made in our understanding of computational complexity. This is, in my estimation, the field in which we have made the most progress in the past 50 years (the field did not really exist 50 years ago, and it's been 46 years since Karp's seminal paper). I would go so far as to say that we currently lie on the cusp of a potential scientific revolution, akin to where theoretical physics was in 1899.

First, computational complexity is not well-understood outside of computer science, and this is a pity. Philosophers in particular should pay more attention to computational complexity! Second, among its most natural audience - other computer scientists - I've frequently heard expressions of derision pointed in its direction. The sentiment I've heard most is that the basic structure that complexity research gives us is useful (for example we deeply care if we're using an O(n log n) algorithm or an O(n^2) algorithm in practice), but the more complicated complexity classes are off the rails. The last significant advance we had was in classifying the NP-complete problems. But we KNOW that P!=NP. Why do we need a proof? The final crux of the argument comes from an appeal to that favorite jackass of armchair physicists, Richard Feynman: Feynman apocryphally had trouble understanding why it was an open question at all! As Scott Aaronson has said multiple times, if we were physicists, we would have long declared P!=NP to be a "law of the universe" and moved on[3]. But I care. First, because the theory is important as-is. But if you're not swayed by analogy to the practical consequences of advancements in theoretical physics, I'll give you two solidly practical reason to care. First, all of cryptography depends crucially on our understanding of complexity. Second, the computational complexity of markets are a crucial theoretical design criterion, one that has historically been underemphasized in market design, but will increasingly become more relevant as our markets get more computationally complex.

P and NP in 2 minutes

A brief introduction to the problem at hand: P is the class of problems that have efficient polynomial-time solutions. NP is the class of problems that have efficient polynomial time verifications of correct solutions.

I'll give you an example: multiplying two numbers together is in P. If you increase the number of digits in my input, I have to do more but not that much more work (strictly speaking, about n^1.425 work), where n is the number of digits in the larger input. n^1.425 is a polynomial, and thus this entire problem is "in polynomial time", the proof is by construction.

Here's an example of a problem that is in NP: factoring a number. We don't have a constructive algorithm that will give us a number's factors in polynomial time (it is an open question if there is one), but if a genie were to present you with the factors, you can very easily verify if the purported factors are indeed correct, by multiplication. Thus, factoring is in NP.

Now there are some problems in NP that are "as hard" as all other problems in NP, because a solution can be used to bootstrap solutions to all other NP problems. The classic example is the traveling salesman problem. If you had a genie that could always solve traveling salesman problems, you can easily translate any other NP problem (such as factoring) into an instance of the traveling salesman problem, give it to your genie, take the resulting solution, and use that to get the factors. We thus call traveling salesman "NP complete". There are a surprisingly large number of practical problems that are NP complete, and identifying a wide set of them basically kicked off this field.

The question now comes around: Are NP-complete problems solvable in polynomial time? This may seem like a surprising question, because the instinctive answer is "Of course not! Why on Earth would you think it would be so?" But a proof has been surprisingly elusive, and meanwhile, we've built more and more systems that implicitly rely on P!=NP, and its various downstream consequences, so it would be nice to know for sure.

The Computational Universe and the Physical Universe

P!=NP is the biggest open question today, and not just because of the cliched joke that if P=NP, we'd solve the other 5 outstanding Clay Millenium Prize Problems. It's the biggest outstanding question because it has the chance to reveal very fundamental flaws in our entire scaffolding of theoretical understanding of our computational universe. Many different---and currently very plausible---advances to answering the P=NP question could very well be akin to the Michelson-Morley experiment, revealing gigantic flaws in our understanding of the computational universe, just as that experiment pretty much put the kibosh on luminiferous aether[5]. Anyone who confidently asserts that P!=NP is dangerously close to Lord Kelvin's assertion in 1900 that "There is nothing new to be discovered in physics now. All that remains is more and more precise measurement."

Let me elaborate on where we currently are in our understanding of our computational universe: Over the past fifty years, we've built up our understanding on top of a house of cards, and each year we add another level of cards atop. At the base are a few fundamental open questions on which we have reasonable educated guesses (I will not resist this opportunity to snark back at physicists; these are what physicists would call "laws"). Many of those cards on the top are attempts to collapse the house of cards, and in an attempt at a meta-proof by contradiction, each failed attempt is yet another clue that perhaps the foundation is sound after all.

But to me, the important insight behind understanding the relevance of the P!=NP problem is that it's not merely a binary question. It's more a question of several different worlds that we could be living in, all of which are distinct and profoundly different.

As Scott Aaronson lays out in NP-complete Problems and Physical Reality, questions about the computational nature of our universe are fundamentally questions about the physical nature of our universe. In a sense, the P!=NP question is the heir (in magnitude) to the implied question posed by the Lorentz transformation[5]. An answer to the P!=NP question that constructively resolved the underling computational model of our universe would be as impactful as the theory of special relativity. Essentially, the core question of our era is: "is cryptography possible?"

Understanding the physical structure of our universe matters because it determines the structure of how we will inhabit the universe. Liu Cixin's The Dark Forest poses that it is the physical reality of relativistic acceleration that explains the Fermi paradox: since kinetic payloads accelerated to relativistic speeds cannot be detected in advance, preemptive first strikes are the Nash equilibrium strategy. The only winning move is not to play, and stay "dark" in the forest of the universe. I find this solution intriguing enough to be the basis of a science fiction universe, although I am skeptical that this is the universe that we do live in. Many uncertainties remain in the detailsof how decentralized one can make one's communication web, which we do not yet fully understand[4]. Nevertheless, these questions depend very deeply on the exact details of the technological limits our physical universe (e.g. does relativistic acceleration necessarily leave energy signatures that can be traced ex post facto?).

What is the computational structure of our universe? Given how little we know of our universe, I've found the best way to approach this question is to try to understand five different parallel worlds, first introduced by Russell Impagliazzo in A Personal View of Average Case Complexity, each with different computational complexity properties. The core question then becomes: which of these five worlds of Russell Impagliazzo do we live in? He named his five worlds Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania.

Algorithmica

This is the P=NP world that people typically think of. This is the one where we have a constructive algorithm that efficiently solves NP-hard problems. We use this algorithm to bootstrap answers to the other Clay problems, all of physics and mathematics, and then shortly after, ascend to Godhood as Arthur C. Clarke-esque beings of pure energy without corporeal form. I will not elaborate further on this world, except to note that nobody really believes that this is the world we live in[1]. Nevertheless, until proven otherwise, this is potentially the world we live in. If we were truly contemplating Algorithmica and Not Algorithmica as binary possibilities, I too would take the Feynman stance. So let's move on to more interesting possibilities.

Heuristica

The best start to describing this world is to begin by directly quoting Impagliazzo:

Heuristica is the world where NP problems are intractable in the worst-case, but tractable on average for any samplable probability distribution[8].

In essence, you have to do an equivalently hard amount of work to find an instance of an NP-hard problem where solving requires super-polynomial time. Thus, NP-hardness is no longer useful to bootstrap cryptographic one-way functions. I like to think of this world as the one in which we realize that "NP-hardness" as a notion is practically useless. In this world, what truly matters is the scaffolding provided by the heuristic analyses themselves. "Is this problem NP hard" becomes replaced with "Is this problem NP-heuristicable". Carrying forward Aaronson's analysis in NP-complete Problems and Physical Reality, if you have a problem instance that is non-NP-heuristicable, there was probably some underlying computational or physical process that did a "hard" amount of work to generate that problem instance! It is almost certain that in this world, there would be no practical cryptography, as attacker and defender would simply be locked in a computational arms race. It is, of course, possible that cryptographic one-way functions exist in "some other" way than NP-hardness but all of that depends on reifying precisely how the NP-heuristics work. For all practical purposes, in this world, cryptography would revert to the stone age, and we would start over. But there's a silver lining: we would get to efficiently solve all naturally-occuring NP-hard problems that weren't pre-constructed to be hard by well-resourced computational adversaries. This is a fun but dystopian universe: there are no hard problems, but there are also no secrets.

Pessiland

Impagliazzo names this world as such because it's truly the worst of all worlds. In this world, NP-hard problems exist, NP-hard instances are easy to find and naturally occur everywhere, but finding matched pairs of NP-hard instances with known easy "keys" is hard. Let's build some intuition using the traveling salesman problem: in this world, TSP is still hard to solve. But it is hard to generate hard instances of TSP with known solutions ("keys"). Whatever process is used to generate the instance while retaining the key ends up selecting for the subset of problems that are not hard to crack. Thus, you cannot bootstrap any cryptographic one-way function using this process[6]

I.E. The universe is full of naturally occuring NP-hard instances (e.g. all of math and physics, all computational modeling problems like traveling salesman, circuit minimization, etc.). But somehow, generating instances of NP-hard problems with known keys is hard. In a sense, the heuristics work very well for instances we generate from known keys, but not for any natural instances from the wild.

This is a garbage world. We don't get any benefit from solving NP-hard problems that we want to solve, and we don't get any cryptographic benefit from NP-hardness either. In this world the Z3 theorem prover still doesn't work well, but now neither does Amazon.com --- all ecommerce today relies upon public-key cryptography to keep our payments secure.

Minicrypt

Minicrypt is a world where a modest amount of cryptography is possible (hence the "mini"). Specifically, one-way functions exists[6], but public-key cryptography does not[7]. One-way functions can be used to bootstrap secure channels, but the actual secret generator must be shared over secure channels a priori. This world is well described in Vernor Vinge's A Fire Upon the Deep. In that universe, the chief trade goods are physically transmitted one-time pads. These one-time pads are small, but necessary to bootstrap cryptographically secure computation, as public-key cryptography does not exist.

You can also get a good intuition for this world because it is one that we've speculated at length on due to quantum computers: the discrete logarithm problem (which is the basis for public-key cryptography) is efficiently solvable by quantum computers (which don't exist yet) via Shor's Algorithm. If you imagine a world where we've built quantum computers but we haven't made any advances in devising public-key cryptographic schemes that aren't Shor's Algorithmable, you're in minicrypt.

However, in this world you could still use quantum cryptography to do non-public-key cryptography, but you'd still have to physically ship the quantum bits to the destination (due to the no-cloning theorem). So there's a lot of physically shipping around quantum cryptography starter packs. There's a lot of sci fi movies that are essentially set in minicrypt, because you'd have to get the correct quantum bits into the secure mainframe before you can upload the plans for the death star.

Cryptomania

This is the classic P!=NP world, except we now have proofs that we live in this world, as opposed to just educated guesses. Our house of cards is stabilized, and all our existing theoretical scaffolding is sound. Importantly, we don't live in minicrypt, pessiland, or heuristica.

That said, there are a couple caveats. To quote Impagliazzo again,

However, blind acceptance of the existence of public key cryptosystems as a de facto complexity axiom is unwarranted. Currently, all known secure public key cryptosystems are based on variants of RSA, Rabin, and Diffie-Hellman cryptosystems. If an efficient way of factoring integers and solving discrete logarithms became known, then not only would the popular public key cryptosystems be broken, but there would be no candidate for a secure public-key cryptosystem, or any real methodology for coming up with such a candidate. There is no theoretical reason why factoring or discrete log should be intractable problems.

Minicrypt or Cryptomania?

Lance Fortnow says that "most computer scientists would say Cryptomania or Minicrypt". I'll go one further, and put my money where my mouth is: I'll bet you twenty one million bitcoin that we live in Cryptomania or Minicrypt!

Answering this binary question alone would give us very different worlds. That said, there are other low probability worlds we might live in. Here's one, which I name Polynomia:

Polynomia: In this world, we have a constructive polynomial time algorithm that solves NP-complete problems, except the exponent is some ridiculously large number so as to render the algorithm practically useless. In this world the house of cards we've built up has collapsed, but in a way that leaves nothing but useless rubble to throw out. We begin the computer-scientific enterprise anew.

There's a good reason that Impagliazzo doesn't waste time on this world, because it's really not a serious possibility[2]. I bring it up because it serves as a useful guidepost as to why some people give the Feynman answer of "just declare it a law of physics and move on". If you were to phrase the question as "do we live in Minicrypt/Cryptomania or Polynomia?", the derisive answer is a lot more sympathetic! But as I hope I've made clear today, that's not the actual question.

Acknowledgements

Thanks to Justin Jaffray, Jason Reed, and Jennifer Gillenwater for helpful suggestions to this post. Thank's also to Dave Moore for suggestions to this post.

Edit History

June 6th: Impagliazzo's Worlds was mentioned before it was first introduced, due to some paragraph movement in editing. Fixed. Thanks to Chris Purcell for bringing it to my attention.

Footnotes

[1]: In Bill Gasarch's poll of prominent members of the theoretical research community, we have 9 respondents (out of 100) who said that P=NP would be the result. Of all respondents, 62 left comments. I categorize the following 6 commenters as either supporting a Polynomia view, or posing that if P=NP, it would be because of Polynomia and not Algorithmica: Jamie Andrews, Yuri Gurevich, David Isles, Donald Knuth, Vladik Kreinovich (who in turn cites Levin as the true originator of his position), Clyde Kruskal. I do not have high confidence in my reading of these comments; there's a lot of in-jokes there.

[2] But maybe I'm wrong! Don Knuth (see question 17) holds the clearest pro-Polynomia view. It's unclear how much of his view is genuinely pro-Polynomia versus a Polynomia-must-be-taken-more-seriously, you underestimate the demons of the shadow at your own peril, etc. etc.

[3] Newsflash to my economist friends: physics envy is everywhere, even amongst the current masters of the universe, computer scientists.

[4] Details such as: if you onion route your messages, can you communicate without revealing your true location? If you set up automated retaliation "submarines" that return fire, can you layer a level of mutually assured destruction that returns you to a stable non-first strike equilibrium?

[5] The history of the Lorentz transformation is very interesting: we essentially had the equations that described the strange behavior of light without understanding why, until the theory of special relativity. The Michelson-Morley experiments were giant WTFs in 1887, which pretty conclusively shot the existing physics theories about luminiferous aether. Special relativity only came around in 1905. For 18 long years, we had no idea what was going on, even after we had the equations to describe it precisely.

[6] "One way function" is the standard term in cryptography, but it is poorly named for giving the right intuition. We essentially talk about functions that are easy in two ways if you know a key, but only easy in one direction if you don't know the key. This is useful in cryptography, because you share the decryption key with your buddy, and then freely use the encryption scheme. If someone else gets hold of the encryption scheme, they cannot use it to decipher the decryption key.

[7] Public key cryptography refers to algorithms that can bootstrap a shared secret key where the participants are only talking over open channels, and have not previously established the shared secret. The classic example is Diffie-Hellman key exchange.

[8] If your question is why can't I have a uniform distribution over all of the problem inputs that give worst-case complexity? The answer is that the magical Impagliazzo's demon makes sampling from this probability distribution NP-hard, so you're back to putting in large amounts of work to generate instances that require large amounts of work to crack.