Publication Details
Title: Towards a Theory of Average Case Complexity
Author: S. Ben-David, B. Chor, O. Goldreich, and M. Luby
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-004.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-004
Bibliographic Reference:
S. Ben-David, B. Chor, O. Goldreich, and M. Luby. Towards a Theory of Average Case Complexity. ICSI Technical Report TR-89-004, February 1989
Author: S. Ben-David, B. Chor, O. Goldreich, and M. Luby
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-004.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-004
Bibliographic Reference:
S. Ben-David, B. Chor, O. Goldreich, and M. Luby. Towards a Theory of Average Case Complexity. ICSI Technical Report TR-89-004, February 1989