Publication Details
Title: On the Theory of Average Case Complexity (Revised Edition)
Author: S. Ben-David, B. Chor, O. Goldreich, and M. Luby
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-55.pdf
Overview:
This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP under reductions which preserve average polynomial-time; a proof that if all distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); definitions and basic theorems regarding other complexity classes such as average log-space.
Bibliographic Information:
ICSI Technical Report TR-89-055
Bibliographic Reference:
S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the Theory of Average Case Complexity (Revised Edition). ICSI Technical Report TR-89-055, September 1989
Author: S. Ben-David, B. Chor, O. Goldreich, and M. Luby
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-55.pdf
Overview:
This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP under reductions which preserve average polynomial-time; a proof that if all distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); definitions and basic theorems regarding other complexity classes such as average log-space.
Bibliographic Information:
ICSI Technical Report TR-89-055
Bibliographic Reference:
S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the Theory of Average Case Complexity (Revised Edition). ICSI Technical Report TR-89-055, September 1989