Which Computational Universe Do We Live In?

“In 1995, Russell Impagliazzo of the University of California, San Diego broke down the question of hardness into a set of sub-questions that computer scientists could tackle one piece at a time. To summarize the state of knowledge in this area, he described five possible worlds — fancifully named Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania — with ascending levels of hardness and cryptographic possibility. Any of these could be the world we live in.”

-Erica Klarreich, “Which Computational Universe Do We Live In?” Quanta Magazine. April 18 , 2022.

Quanta has some really interesting content. Let’s hope we live in Cryptomania.