On the theory of average case complexity
Proceedings of the twenty-first annual ACM symposium on Theory of computing, 1989•dl.acm.org
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 …
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 …
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.