Impagliazzo’s Multiverse

Update (July 2009): Here are links to a related post on Lipton’s blog, and a conference announcement on Russell’s possible worlds.

On the occasion of Luca’s post on his FOCS 2008 tutorial on average-case complexity here is a reminder of Russell Impagliazzo’s description of the possible universes we live in.

Being at FOCS was a splendid experience and my presentation of the paper of Ehud Friedgut, Noam Nisan and myself was well accepted. (And reported by Rahul Santhanam on “Computational Complexity“) The slides are here; Initially I felt bad for including only one out of three parts of the proof but eventually I had no time to describe any part of the proof.

Russell Impagliazzo’s multiverse – cryptography and complexity

Impaglliazzo’s paper deals with two central topics in theoretical computer science: Computational complexity studies the power of computers and cryptography studies the ability to create codes and to hide information. These two areas added beautiful new scientific insights, and the deep connections between them were described by computer scientist Shafi Goldwasser as “a match made in heaven.” The limited power of computers and the well known question “whether P=NP” are of central importance in Impaglliazzo’s classification,  as are the concepts of “one way functions” and “public keys”.


In this universe computers can quickly solve hard problems.  (In technical terms: P=NP.)  If you can quickly recognize a valid solution to a problem once the latter is presented to you,  (such problems are “in NP”), then you can apply this same method in order to actually find a solution! In this universe almost all optimization problems have a quick and automatic solution. No cryptography is possible and therefore there is no privacy.

Muhammad ibn Musa al-Khwarizmi (the term “algorithm” is called after his name, and not after All Gore as commonly believed)


In this universe computers can quickly solve  hard problems that actually emerge. There are hard cases that cannot be solved by computers, but finding these cases is just as hard. Practically, this is quite similar to the first universe. There are, however, salient differences , which Impaglliazzo explains in his paper. Still no cryptography is possible.


In this universe computers cannot solve hard problems, but the weakness of computers cannot be used to create good codes to hide information. Impaglliazzo regards this as the worst of all possible universes.


In this universe “one way functions” exist: One way functions f(x) have the property that given x it is easy to find f(x), but given y it is very hard to find x such that y=f(x). This allows some cryptography. Two people (whose traditional names are Alice and Bob), who can communicate safely for a certain amount of time, can agree on a secret unbreakable code that will allow them to correspond safely over an unsafe network for a long time.

Mini crypt by chrisdonia.


In this universe cryptography is in full power.  Our Alice and Bob can securely communicate over unsecured channels using “public keys”. Even a large number of people can perform a common task based on their private information without revealing it. In this universe computer technology both enhances and guarantees privacy.

This entry was posted in Computer Science and Optimization and tagged , , . Bookmark the permalink.

7 Responses to Impagliazzo’s Multiverse

  1. Gil Kalai says:

    A recent post on Lipton’s blog and a recent conference devoted to Russell’s multiverse are added to the post.

  2. Olle H says:

    You speak of possible worlds, Gil, but surely at most one of them is possible…?

  3. Gil Kalai says:

    Dear Olle, what I meant was that as far as we know now, all the “worlds” are possible as our world.

  4. Olle H says:

    Of course, Gil, I was just trying to be annoying. I’m glad you didn’t challenge me to a deeper discussion about the meaning of “possible”.

  5. Gil Kalai says:

    Well, in a sense we live in the mini-crypt/cryptomania world since for us one way functions do exist (e.g. factoring is hard for us).

  6. Gil Kalai says:

    A world “Obfustopia” was also considered recently, as well as some further worlds without a linear order for them. Similar classification was also suggested in learning. (I will try to gather further details. )

  7. Pingback: The different forms of quantum computing skepticism | Combinatorics and more

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s