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.
Related questions
@PARROTFEVER does that post imply that people living in (say) Heuristica can causally interact with (say) Cryptomania? If not, just define "live in" as "can causally interact with".
@JavierPrieto Only one of these universes is actually logically possible, though. We just don't know which one yet. So even if some kind of maximal multiverse existed, there still would not be any possibility of people from different computational universes existing.
@JosephNoonan How so? Couldn't this be independent of ZFC or whatever axioms you're using? More generally, couldn't there be different Tegmark IV universes where different sets of axioms apply?
@JavierPrieto They could be independent of ZFC, but even that wouldn't make it possible for there to be some universes where they're true and some where they're not. There are two interpretations that can be taken for statements independent of ZFC: The first is that the statement is true or false, but ZFC just isn't strong enough to prove it. In this case, everything I said previously applies. The second is that the statement has an indefinite truth value because we haven't defined what a set is specifically enough to determine what the answer is (e.g., if you consider the ZFC axioms to be a definition of what a set is, then we would have to conclude that statements like the Continuum Hypothesis are just too vague to have a truth value, because our definition of "set" isn't specific enough to say whether they are true or false). This latter interpretation doesn't make any sense for questions about computational complexity, though - if you print out the infinite list of all Turing machines and run them, either you do eventually get one that solves NP problems in polynomial time, or you don't. But even if it did make sense, it would still be true in all possible universes. You wouldn't have some worlds where P=NP and some where P≠NP. Instead, it would just be true in all worlds that P vs. NP is too vague of a question to have a definite answer. And if you made the question more specific (by adding more axioms), it would case the case in all universes that adding one set of axioms makes P=NP and another makes P≠NP.
couldn't there be different Tegmark IV universes where different sets of axioms apply?
No. It doesn't matter how broad your conception of the multiverse is, there are no universes where different mathematical axioms apply, at least not in the modern sense of what a mathematical axiom is. That's because mathematical axioms don't describe anything about the physical world, they only describe abstract concepts like sets. As an example, spacetime in our universe is better described by Reimannian geometry than Euclidean geometry. You might be tempted to say that this means that the Euclidean axioms are false in our universe, but could be true in another universe. The problem with this is that the Euclidean axioms aren't meant to be axioms that describe how physical space works. They describe the geometry of ℝ^n, and they describe it just as accurately in our universe as they would in a universe where physical spacetime is Euclidean. The idea behind a Tegmark IV multiverse is that different universes can be described by different mathematical structures, but that only changes facts about what concretely exists in those universes - it doesn't change math at all. Questions in computational complexity theory are purely abstract and don't depend on the physical structure of our universe.
@a2bb My assumption is it resolves once we actually find out. Since these "universes" reference specific mathematical conjectures, proving or disproving them would tell us which we live in. E.g., if trapdoor functions are proven to exist, we live in Cryptomania. If P=NP, we live in Algorithmica.