Towards a Theory of Average Case Complexity

TitleTowards a Theory of Average Case Complexity
Publication TypeTechnical Report
Year of Publication1989
AuthorsBen-David S, Chor B, Goldreich O, Luby M
Other Numbers503

This paper takes the next step in developing the theory of average case complexity, a study initiated by Levin. Previous works have focused on the existence of complete problems [Le,Gu,VL]. We widen the scope to other basic questions in computational complexity. For the first time in the context of average case complexity, we show the equivalence of search and decision problems, analyze the structure of NP under P reductions, and relate the NP versus average-P to non-deterministic versus deterministic (worst case) exponential time. We also present definitions and basic theorems regarding other complexity classes, such as average log-space.

Bibliographic Notes

ICSI Technical Report TR-89-004

Abbreviated Authors

S. Ben-David, B. Chor, O. Goldreich, and M. Luby

ICSI Publication Type

Technical Report