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]
About these ads

One thought on “Impagliazzo’s Worlds

  1. “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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s