Theoretical Computer Science
cc.complexity-theory conditional-results average-case-complexity
Updated Sat, 21 May 2022 18:20:31 GMT

Status of Impagliazzo's Worlds?

In 1995, Russell Impagliazzo proposed five complexity worlds:

1- Algorithmica: $P=NP$ with all the amazing consequences.

2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the average-case.

3- Pessiland: There exist average-case $NP$-complete problems but one-way functions do not exist. This implies that we can not generate hard instances of $NP$-complete problem with known solution.

4- Minicrypt: One-way functions exist but public-key cryptographic systems are impossible

5- Cryptomania: Public-key cryptographic systems exist and secure communication is possible.

Which world is favored by the recent advances in computational complexity? What is the best evidence for the choice?

Russell Impagliazzo, A Personal View of Average-Case Complexity , 1995

Impagliazzo's Five Worlds, The Computational Complexity blog


About a year ago I co organized a workshop on complexity and cryptography: status of Impagliazzo's worlds, and the slides and videos on web site may be of interest.

The short answer is that not much has changed in the sense that most researchers still believe we live in "Cryptomania" and we still have more or less the same evidence for this, and not much progress on collapsing any of the worlds for one another.

Perhaps the most significant piece of new information is Shor's algorithm that shows that at least if you replace P with BQP, the most commonly used public key cryptosystems are insecure. But, because of Lattice based cryptosystems, the default assumption is that we live in cryptomania even in this case, though perhaps the consensus here is a bit weaker than the classical case. Even in the classical case, there seems to be much more evidence for the existence of one-way functions ("Minicrypt") than the existence of public key encryption ("Cryptomania"). Still, given the effort people have spent in trying to break various public key cryptosystem, there's significant evidence for the latter as well.

Comments (1)