A common misinterpretation of these results was that all NP-complete
problems are hard, no chance for good algorithms. On this basis some
such problems generated much hope in cryptography: the adversary would
be helpless. Karp and others noticed that this was naive. While **
worst ** instances of NP-complete problems defeat our algorithms, such
instances may be extremely rare. In fact, fast ** on average **
algorithms were found for a great many NP-complete problems. If all NP
problems are easy on average, the P=?NP question becomes quite academic.
Even if exponentially hard instances exist, those we could ever find
might all be easy. Some problems (like factoring) seem hard for typical
instances, but nothing is proven at all to support this (crucial, e.g.,
for cryptography) belief. These issues turned out to be subtle and it
was not clear how a theory could distinguish intrinsically hard on
average problems. [Levin 86], [Venkatesan, Levin STOC-88], [Impagliazzo, Levin, FOCS-90] proposed such a
theory with first average case intractability results. Random (under
uniform distribution) instances of some problems are now known to be as
hard as random instances of any NP-problem under any samplable
distribution. A number of subsequent papers extended this area
substantially. See expositions in [Johnson
84], [Gurevich 85] and at
http://www.uncg.edu/mat/avg.html.