Algorithmica: P = NP or something “morally equivalent” like fast probabilistic algorithms for NP.
Heuristica: NP problems are hard in the worst case but easy on average.
Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparently do not get any cryptographic advantage from the hardness of these problems.
Minicrypt: One-way functions exist but we do not have public-key cryptography.
Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.
Read more at:
What about your love of role-playing games — has that influenced your work at all?
It may not have influenced all my research, but it certainly did influence my five worlds paper. I’ve always had a general interest in fantasy and science fiction and coming up with different possible worlds — what would things be like if everything was different?
Why are role-playing games such a compelling way to explore hypothetical worlds?
People who are into speculative fiction have always invented worlds. Tolkien is most famous for it, and he had such a massive imagination that his world actually felt lived in. For those of us who aren’t as imaginative, the best way to achieve that is to invite people into your setting, and a game is a way of doing that. Now it’s not just my world. It may have started how I imagined it, but just like in any collaboration, because of everyone else’s contributions it’s evolved way past that.
Read more at Impagliazzo’s interview
