Average Case Completeness
- Yuri Gurevich
Journal of Computer and System Sciences - A special issue with selected papers of FOCS'87 | , Vol 42(3): pp. 346-398
We explain and advance Levin’s theory of average case complexity. In particular, we exhibit the second natural average-case-complete problem and prove that deterministic reductions are inadequate.