A personal view of average-case complexity

The structural theory of average-case com-plexity, introduced by Levin, gives a for-mal setting for discussing the types of inputs for which a problem is dicult. This is vital to understanding both when a seemingly dicult (e.g. NP-complete) problem is actually easy on almost all in-stances, and to determining which prob-lems might be suitable for applications re-quiring hard problems, such as cryptog-raphy. This paper attempts to summarize the state of knowledge in this area, includ-ing some \folklore " results that have not explicitly appeared in print. We also try to standardize and unify denitions. Fi-nally, we indicate what we feel are inter-esting research directions. We hope that this paper will motivate more research in this area and provide an introduction to the area for people new to it