Impagliazzo's Five Worlds

The natural proofs barrier showed us something unsettling: the assumption that makes cryptography possible, that pseudorandom function families exist, is the same assumption that blocks our strongest proof technique for circuit lower bounds. The hardness we want to prove shields the problem from our proofs.

But that cryptographic assumption is not a single thing. There is a spectrum of assumptions about hardness, from "no hardness exists at all" to "hardness is so structured you can build public-key cryptography on it." In 1995, Russell Impagliazzo wrote a paper called "A Personal View of Average-Case Complexity," which he cheerfully admitted was propaganda for a question rather than a collection of theorems, making the spectrum precise: five possible ways the complexity-theoretic universe could be structured, which tell you exactly when the barrier applies and when it doesn't.

Grouse and Gauss#

Impagliazzo frames the question through a story. Professor Grouse assigns the young Gauss a problem: sum the integers from one to a hundred. Gauss famously solves it instantly, and Grouse becomes obsessed with revenge, with inventing problems the prodigy can't solve. The five worlds describe how the quest plays out. Can Grouse find hard problems at all? Can he generate problems he can solve but Gauss can't? Can he arrange for the whole class to solve problems Gauss cannot? Impagliazzo deliberately leaves the computational model unspecified; the worlds are an informal guide, not a formal partition.

Algorithmica#

In Algorithmica, P equals NP, or something morally equivalent holds, like NP contained in BPP. Every problem whose solutions are easy to check is also easy to solve: verification becomes solution, so Grouse can never stump Gauss with any problem he can grade.

Optimization problems we currently attack with heuristics would have exact, efficient algorithms: VLSI design, protein folding, scheduling, all solvable once the objective can be stated precisely. Compilers would derive methods from specifications, and proofs of theorems could be found in time polynomial in their length.

But no computational secret could exist. Any code could be reverse-engineered from input-output pairs; cryptography would be impossible, not because we haven't found the right scheme, but because the mathematical foundation for secrets wouldn't exist. The natural proofs barrier would not apply, since pseudorandom functions couldn't exist, and we wouldn't need circuit lower bounds anyway.

Heuristica#

In Heuristica, P does not equal NP, so hard instances exist in the worst case, but NP problems are easy on average for every efficiently samplable distribution: no distribution you can draw from by an efficient process puts enough weight on hard instances to make a problem difficult on average.

This is the gap the paper was written to illuminate: worst-case hardness does not mean problems are hard in practice. Grouse might stumble onto a hard instance, but finding one takes far longer than solving a typical problem. Still, Heuristica is not Algorithmica in disguise: if solving one problem takes twice as long as thinking it up, and each solution leads to a new problem, the costs compound, roughly doubling at each step, and a few iterations cross from feasible to infeasible.

Pause and try: why can't one-way functions exist in Heuristica?

A one-way function must be easy to compute and hard to invert on a random input. But "pick a random $x$, output $f\left(x\right)$" is an efficient process, so the outputs form a samplable distribution, and finding a preimage is an NP search problem: a candidate preimage is a certificate you check by applying $f$. Heuristica says every such problem is easy on average, so some efficient algorithm inverts $f$ on typical outputs. No one-way functions, no pseudorandom functions, and the natural proofs barrier is inert.

Pessiland#

Pessiland is, in Impagliazzo's assessment, the worst of all possible worlds: NP problems are hard on average, but there are no one-way functions, easy to compute yet hard to invert on a random input.

Hard instances are everywhere, but you cannot harness the hardness. To use a hard problem, you would want to generate an instance together with its solution, a process mapping a random seed to a problem-solution pair. If that process were one-way, you would have a one-way function, which Pessiland forbids; so any generation process can be inverted and the solution extracted. No cryptography, no pseudorandomness, no secure communication. Grouse can pose problems Gauss can't solve, but Grouse can't solve them either. The humiliation is mutual.

Minicrypt#

What would it take to make hardness useful? Minicrypt: one-way functions exist, but public-key cryptography does not.

If $f$ is one-way, pick a random $x$, compute $y=f\left(x\right)$, and publish $y$ as a challenge: find any $x^{\prime }$ with $f\left(x^{\prime }\right)=y$. You know the answer, because you chose $x$; the adversary, given only $y$, cannot find one. For the first time, you can generate hard instances that you have already solved, and Grouse finally has the upper hand.

One-way functions yield pseudorandom generators, and from there digital signatures, private-key encryption, and commitment schemes: two people who already share a secret key can communicate securely. But Minicrypt has sharp limits. Strangers cannot agree on a secret over a public channel, secure public elections are impossible, and anonymous digital money is not known to be achievable. The gap between Minicrypt and Cryptomania is the gap between private and public trust. And sufficiently strong one-way functions are exactly what the natural proofs barrier needs: here, pseudorandom functions exist and the barrier kicks in.

Cryptomania#

In Cryptomania, public-key cryptography is possible. Two parties who have never communicated can agree on a shared secret using only a public channel: each publishes a value derived from private information, and together the public values yield a secret no eavesdropper can compute, despite seeing everything sent.

This takes structured hardness beyond bare one-way-ness. RSA uses factoring, Diffie-Hellman uses discrete logarithms, and more recent schemes use lattice problems; what they share is exploitable algebraic structure. Here Grouse achieves complete victory: he and a confederate can publicly agree, in full view of Gauss, on a problem they can both solve but Gauss cannot. Secure elections, multi-party computation, digital cash: the full apparatus of modern cryptography. This is the world we believe we inhabit, and the protocols securing every web connection assume it.

The boundaries are the open problems#

Five worlds, ordered by how much hardness exists and how exploitable it is. The boundaries between them are the deepest open problems in the field: P versus NP, whether average-case hardness exists, whether one-way functions exist, and whether public-key cryptography follows from private-key primitives.

The Heuristica-Pessiland boundary hinges on what "hard on average" even means, and the naive answer, superpolynomial expected running time, is the wrong one. An algorithm that is linear except on a $2^{-n}$ fraction of inputs, where it takes exponential time, has small expected running time, but the expectation of the square of its running time is exponential, so composing it with polynomial post-processing can blow the total up. Levin's definition fixes this: a problem is polynomial on average if, for any time bound $T$, the fraction of length-$n$ inputs requiring more than $T$ steps shrinks polynomially in $T$. That definition is closed under reductions and composition, and for distributional problems, a problem paired with an input distribution, Levin proved completeness: if any complete one is easy on average, all of average-case NP is.

Which world do we live in?#

The honest answer is that we don't know. Most complexity theorists believe P does not equal NP, ruling out Algorithmica, after decades of failed algorithms and structural results suggesting such algorithms would collapse entire hierarchies. The practical success of cryptography suggests at least Minicrypt, probably Cryptomania: RSA has held for decades. But Impagliazzo warned that this confidence is fragile, since all known public-key systems at the time relied on factoring or discrete logarithms, and Shor's algorithm later showed quantum computers break both. The community has migrated toward lattice-based schemes, standardized by NIST in 2024, but our confidence that any specific function is one-way still comes from the failure of known attacks, not from proof.

Heuristica and Pessiland are the hardest to rule out. Random 3-SAT, for example, is easy outside a narrow critical threshold, and no proof exists that any natural distribution makes an NP problem hard on average. Strong opinions, weak theorems; none of the boundaries has been unconditionally resolved.

But the map has deepened. In 2020, Liu and Pass showed that one-way functions exist if and only if a single problem is hard on average: approximating, for a given string, the length of the shortest program producing it within a given time bound. That is time-bounded Kolmogorov complexity, and it pins the Pessiland-Minicrypt boundary to one computational task. The five worlds remain a map of our ignorance, and a research program for resolving it.

If you remember three things#

1. The five worlds order computational hardness by structure: Algorithmica (none), Heuristica (worst-case only), Pessiland (average-case but unusable), Minicrypt (one-way functions), Cryptomania (public-key cryptography).
2. Every boundary between adjacent worlds is a famous open problem, and none has been unconditionally resolved: strong opinions, weak theorems.
3. Useful cryptography begins exactly where one-way functions do, and so does the natural proofs barrier: the same hardness that powers secrets blocks the proofs.