Impagliazzo’s Worlds

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 P=NP or NP \subseteq BPP.

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]