I am back in Atlanta after attending Valiant’s birthday celebrations, STOC 2009 and Impagliazzo’s Worlds workshop. Another upcoming workshop at Center for Computational Intractability is “Barriers in Computational Complexity” workshop from August 25-29, 2009. Today’s post is a brief introduction to the five Impagliazzo’s Worlds [Impagliazzo’95].
Algorithmica is the world in which 
Heuristica is the world where NP problems are intractable in the worst case but tractable on average.
Pessiland is the world in which there are hard average-case problems, but no one-way functions. As the name suggests this is the worst possible world.
Minicrypt is the world in which one-way functions exist, but public-key cryptography is impossible.
Cryptomania is the world in which public-key cryptography is possible.
Open Problems : An obvious open problem is which world do we live in ? Does Pessiland exist ?
References :
- [Impagliazzo’95] Russell Impagliazzo : A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147 [ps]
My Brain is Open 
“Another upcoming workshop at Center for Computational Intractability is “Barriers in Computational Complexity” workshop from August 25-29, 2009. Today’s post is a brief introduction to the five Impagliazzo’s Worlds [Impagliazzo’95].”
Where else can I read about it?