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.
Please send comments to email@example.com.
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