In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.