We survey the average-case complexity of problems in NP.

We discuss various notions of good-on-average algorithms, and
present completeness results due to Impagliazzo and Levin.
Such completeness results establish the fact that if a certain
specific (but somewhat artificial) NP problem is easy-on-average
with respect to the uniform distribution, then all problems in NP
are easy-on-average with respect to all samplable distributions.
Applying the theory to natural distributional problems remain an
outstanding open question. We review some natural distributional
problems whose average-case complexity is of particular interest and
that do not yet fit into this theory.

A major open question whether the existence of hard-on-average
problems in NP can be based on the P$\neq$NP assumption or on
related worst-case assumptions. We review negative results showing
that certain proof techniques cannot prove such a result. While the
relation between worst-case and average-case complexity for general
NP problems remains open, there has been progress in understanding
the relation between different ``degrees'' of average-case
complexity. We discuss some of these ``hardness amplification''
results.

We survey the theory of average-case complexity, with a
focus on problems in NP.