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.

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.

`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.

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.

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.

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

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 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.

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.

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.

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.

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.

[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.