“A Personal View of Average-Case Complexity”, 1995-06-19 (; backlinks; similar):
The structural theory of average-case complexity, introduced by 1986, gives a formal setting for discussing the types of inputs for which a problem is difficult. This is vital to understanding both when a seemingly difficult (eg. NP-complete) problem is actually easy on almost all instances, and to determining which problems might be suitable for applications requiring hard problems, such as cryptography.
The paper attempts to summarize the state of knowledge in this area, including some “folklore” results that have not explicitly appeared in print. We also try to standardize and unify definitions. Finally, we indicate what we feel are interesting research directions.
We hope that the paper motivates more research in this area and provide an introduction to the area for people new to it.
[In that paper Impagliazzo describes 5 possible worlds and their implications to computer science.
Algorithmica: P=NP or something “morally equivalent” like fast probabilistic algorithms for NP.
In the science-fiction world of Algorithmica, all optimization problems such as strong AI and math proofs and every form of algorithmic inference is trivial, all kinds of magic is possible; simply feed the data in, and out will come the smallest optimal answer or the smallest algorithm generating the data. Cryptography and privacy are impossible.
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 apparently 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. 2 parties can exchange secret messages over open channels.
Relevant followup work: time-bounded Kolmogorov complexity.]