Russell Impagliazzo's A Personal Viewof Average-Case Complexity, presented at the 1995 Complexity Conference, describes five possible worlds and their implications to computer science:

• Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. This was the world I described last week but looking back at Impagliazzo's paper, he does a nicer job.

• Heuristica: NP problems are hard in the worst case but easy on average.

• Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparantly do not get any cryptographic advantage from the hardness of these problems.

• Minicrypt: One-way functions exist but we do not have public-key cryptography.

• Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.

Impagliazzo does not guess which world we live in. Most computer scientists would say Cryptomania or Minicrypt. Which world do we live in? Resolves when we know, or when an ASI is confident enough about the answer to resolve the market.