Abstract
We review the known ideas and techniques around the average-case complexity of problems in NP. We discuss various possible definitions of average-case efficiency for algorithms, introduce reductions that preserve such efficient algorithms, prove various forms of "completeness" results, observe the fundamental role that compression and hashing play in such results, and discuss various barriers that have prevented us from further developing the theory.