Average-Case Complexity Forum

Average case analysis always seemed more relevant than the worst case. Indeed, although NP-complete problems are generally thought of as being computationally intractable, some are easy on average; and some are complete in the average case, indicating that they remain difficult on randomly generated instances. Motivated and guided by the desires to distinguish (standard, worst-case) NP-complete problems that are "easy on average" from those that are "difficult on average," the study of average-case NP-completeness opens a new front in complexity theory. This forum provides an overview of the recent research on average complexity, and shows the subtleties in formulating a coherent framework for studying average-case NP-completeness. It also provides an up-to-date list of works published in the area.

Average-Case Computational Complexity Theory, an introduction.
Average-Case Intractible NP Problems, a survey of average-case NP-complete problems.
An up-to-date list of research and survey articles in average complexity.
Structural properties of sets that are not in P but in AP under every p-time computable distribution, a survey.

Advisory Board: Yuri Gurevich, Steven Homer, Leonid Levin.
Editor: Jie Wang.
Please send comments to wang@cs.uml.edu.

This material is based upon work supported by the National Science Foundation under Grant No. 9424164 and under Grant No. 9820611. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).