On the theory of average case complexity

摘要

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: 1.⊎|the equivalence of search and decision problems in the context of average case complexity;2.⊎|an initial analysis of the structure of distributional-NP (i.e., NP problems coupled with “simple distributions”) under reductions which preserve average polynomial-time;3.⊎|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);4.⊎|definitions and basic theorems regarding other complexity classes such as average log-space.An exposition of the basic definitions suggested by Levin and suggestions for some alternative definitions are provided as well.