Despite many years of intensive effort, there are no known efficient algorithms for NP-complete problems, where by efficient we mean algorithms that are fast in the worst case. Due to this striking gap in our knowledge, the search for algorithms that are ``efficient'' according to various more modest criteria has attracted increasing attention.
One particularly interesting criterion is that of requiring
problems be solvable quickly ``on
average.''
That is, can one
solve NP-complete problems via algorithms that,
although possibly very slow on some inputs, are
fast on average with respect to some underlying probability
distributions on instances.
Algorithms that are fast on average have been found for several
NP-complete problems, such as the vertex 
-coloring
problem [Wil84]
and the Hamiltonian path
problem [GS87], under
commonly used distributions on graphs.
However, there also are NP-complete problems that have so far resisted such ``average case" attacks. Are these problems difficult on average? What does it mean for a problem to be difficult on average, and how is one to know whether a problem is difficult on average? In his seminal paper [Lev86], Levin initiated the study of these questions. Two fundamental and robust notions were defined along lines similar to (standard, worst-case) NP-completeness theory. Namely, he introduced the notion of average polynomial time for measuring ``easiness" on average and the notion of average-case NP-completeness for measuring ``hardness" on average. Levin then showed that a tiling problem is average-case NP-complete if each parameter of an instance is randomly selected. This framework has been studied and enhanced by a number of researchers and several more average-case NP-complete problems have been found. Such average-case completeness results, as indicated by Levin [Lev86], may not only save misguided ``positive" efforts-such as trying to find fast-on-average algorithms for problems that probably lack them-but might also be used in areas (like cryptography) where hardness on average of some problems is a frequent assumption.
This article is intended to present systematically the current state of knowledge on average-case complexity, and is centered around three fundamental concepts: average polynomial time, reductions/completeness, and feasible distributions.
