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 or .

**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]

### Like this:

Like Loading...