Contents
Next: Introduction
Up: Average-Case Computational Complexity Theory
Previous: Average-Case Computational Complexity Theory
Average-Case Computational Complexity Theory
Jie Wang
UNC Greensboro
Abstract:
NP-complete problems are generally thought of
as
being computationally intractable.
However, NP-completeness is a worst-case concept.
Indeed, some NP-complete problems are ``easy on average,''
though some may not be.
How is one to know whether an NP-complete problem is
``difficult on average''?
The theory of average-case computational
complexity, initiated by Levin about ten years ago,
is devoted to studying this problem.
This paper provides an overview of the main ideas
and results in this important new subarea of complexity theory.
Jie Wang
Tue Feb 4 13:48:58 EST 1997