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.
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).