On the theory of average case complexity
Shalev Ben-David, Benny Chor, Oded Goldreich · 1989
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 (i.e. NP problems coupled with \\simple distributions") under reductions which preserve average polynomial-time; a proof that if all of 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); denitions and basic theorems regarding other complexity classes such as average log-space. An exposition of the basic denitions suggested by Levin and suggestions for some alternative de nitions are provided as well.