Good explainer on Quanta magazine.

Here's GPT-4:

Impagliazzo's 5 possible computational worlds, presented in his 1999 paper "A Personal View of Average-Case Complexity," explore different scenarios based on how hard certain computational problems are. In these worlds, the feasibility of cryptography and the existence of intractable problems serve as key differentiators. These imagined universes help researchers and theorists frame discussions about the complexity of algorithms and the limits of computation.

Here's a list of key features:

Algorithmica

- Cryptography: Weak or None

- P vs NP Status: P=NP

- Intractable Problems: Few or None

- Notes and Examples: Almost all problems can be efficiently solved.

Heuristica

- Cryptography: Weak or None

- P vs NP Status: P≠NP, but no strong evidence

- Intractable Problems: Some, but often have good heuristics

- Notes and Examples: Problems like SAT might not be solved in polynomial time, but heuristics work well in practice.

Pessiland

- Cryptography: None

- P vs NP Status: P≠NP, and worst-case hard problems are average-case hard

- Intractable Problems: Many

- Notes and Examples: No public-key cryptography; problems like 3-SAT are hard on average.

Minicrypt

- Cryptography: Symmetric-Key

- P vs NP Status: P≠NP, and one-way functions exist

- Intractable Problems: Some, but limited to average-case

- Notes and Examples: Only symmetric-key cryptography possible. One-way functions exist but public-key cryptography doesn't.

Cryptomania

- Cryptography: Strong, both symmetric and public-key

- P vs NP Status: P≠NP, and trapdoor functions exist

- Intractable Problems: Many, including average-case

- Notes and Examples: Both public-key and symmetric-key cryptography are secure. Problems like factoring are hard on average.