Average case analysis always seemed more relevant than the worst case. Indeed, although NP-complete problems are generally thought of as being computationally intractable, some are easy on average; and some are complete in the average case, indicating that they remain difficult on randomly generated instances. This talk is intended to provide an overview of the recent research on average complexity of NP-complete problems. We will describe some of the subtleties in formulating a coherent framework for studying average complexity and techniques of obtaining average-case NP-completeness results.