Heuristica

Are you complex enough?

In 1995, computer scientist Russell Impagliazzo summarized five possible worlds that we could be living in: Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania.¹ Each world makes a progressively stronger hypothesis about the existence of “hard” problems—those that cannot be solved with an algorithm whose runtime scales polynomially with the input size. For instance, Algorithmica is a world in which P = NP, where there are no hard problems. In Pessiland, hard problems exist, but their “hardness” is not sufficient to provide cryptographic guarantees, i.e. there are no one way functions (OWFs). In between Algorithmica and Pessiland is Heuristica, where hard problems exist, but most instances of these problems can be solved efficiently using heuristics (avgP = distNP). Much of the effort in computational complexity theory research goes into determining which world we live in, or, towards the same end, showing which worlds do not exist.

My favorite is Heuristica. In Heuristica, there are problems that are hard in the worst case, but tractable on average for any samplable distribution. As an example, the subset sum problem in NP asks whether there is a non-zero subset of a given set of integers that sum up to zero. Though an efficient algorithm for this problem may not exist, one may be able to come up with a useful heuristic that is correct on most inputs but fails to evaluate some edge cases (hard instances) efficiently. One way to think of these hard instances is as curated adversarial examples in machine learning (see picture below).²

Practically, I think of certain classes of machine learning algorithms as efficient heuristics that can approximate solutions to problems in most instances, with the error loosely bounded by the difference between training and testing distributions; thus, buying into Heuristica is, in some sense, believing that developing heuristics such as machine learning algorithms is the theoretical best we can do for many problems.

What is even more fascinating about Heuristica is that it is somewhat paradoxical:

Here, there exist hard instances of NP problems, but to find such hard instances is itself an intractable problem! In this world, Grouse might be able to find problems that Gauss cannot answer in class, but it might take Grouse a week to find a problem that Gauss could not solve in a day, and a year to find one that Gauss could not solve in a month.³

Now, does this imply that we won’t see any hard instances of NP problems in the real world? If the real world is some active agent, then it must mechanistically invent such a hard instance through a process as hard as actually solving it (the above example with Gauss and Grouse where Gauss takes less time assumes that Gauss has some polynomial advantage over Grouse). Thus, these hard instances can be thought of as adversarial inputs and it’s unclear why the world would be an adversary. On the other hand, if we believe that everything comes up by chance, then the chances of seeing hard instances of NP problems are so small that we might as well ignore them. In both cases, I am reasoning about the real world as a gigantic Turing Machine with memory (space) bounded by the number of atoms in this universe.

There is something satisfying about understanding which world we live in. In fact, it goes beyond understanding the current world and defines the limits of what we can aspire to.⁴ For example, if we know that we live in Algorithmica, Heuristica, or Pessiland, we know that the field of cryptography is cooked. At the same time, it is sort of magical to NOT know: we can simultaneously encompass the different experiences of being citizens in all of these worlds. We may not want to know because, after all, we may end up in Pessiland.

1. Most of this piece is inspired by this class I took with Avishay Tal and Hongxun Wu during my masters.

2. 2015 paper: https://arxiv.org/abs/1412.6572.

3. Impagliazzo’s paper: https://ieeexplore.ieee.org/document/514853.

4. Another idea about the limits of what we can do that received the 2007 Gödel Prize: Natural Proofs.