Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Johannes Köbler and Rainer Schuler
To appear in the Proceedings of the Conference on Mathematical Foundations of Computer Sciences (MFCS), 1998.

Abstract:

We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we get that PP=P if all sets in P(PP) are efficiently decidable on average.