Boaz Barak in a comment last week mentioned one of my favorite survey papers, Russell Impagliazzo’s A Personal View of Average-Case Complexity presented at the 1995 Complexity Conference. In that paper he 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.
The paper goes on to give one of the better justifications for Levin’s definition of average-case complexity.
Original by Lance Fortnow: http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html