Notes on Levin's Theory of Average-Case Complexity

Abstract 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. Acknowledgement and Warning: Much of the text was reproduced from expositionary material contained in [1], which in turn was based on [4]. Thus, much of the technical exposition is 10 years old; I would have written some things differently today. \Lambda Written while visting LCS, MIT. 0 1 Introduction The average complexity of a problem is, in many cases, a more significant measure than its worst case complexity. This has motivated the development of a rich area in algorithmic research- the probabilistic analysis of algorithms [11, 13]. However, this line of research has so far been applicable only to specific algorithms and with respect to specific, typically uniform, probability distributions. The general question of average case complexity was addressed for the first time by Levin [15]. Levin's work can be viewed as the basis for a theory of average NP-completeness, much the same way as Cook's [2] (and Levin's [14]) works are the basis for the theory of NP-completeness. Subsequent works [7, 18, 8] have provided few additional complete problems. Other basic complexity problems, such as decision versus search, were studied in [1]