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

The paper goes on to give one of the better justifications for Levin's definition of average-case complexity.

"Impagliazzo does not guess which world we live in."

ReplyDeletebut does he tell us which one _he_ lives in?

;)

ReplyDelete