Average-Case Intractable NP Problems

Jie Wang
UNC Greensboro

Abstract:

The notion of NP-completeness has provided a rigorous mathematical definition for measuring intractability of NP problems. But this measure applies only to worst-case complexity. Being NP-complete does not indicate that a problem is intractable on the average case. Indeed, some NP-complete problems are ``easy on average,'' though some may not be. Levin [Lev86] initiated the study of average-case NP-completeness to measure average-case intractability. He showed that a bounded tiling problem under a simple distribution is average-case NP-complete. Since then, several additional average-case NP-complete problems have been shown within Levin's framework. This paper is intended to provide a comprehensive survey of average-case NP-complete problems that have been published so far, and the techniques of obtaining these results.

Jie Wang
Mon Feb 3 15:13:50 EST 1997