Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

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

Average-Case Intractability vs. Worst-Case Intractability

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


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.


Ps-File: Average-Case Intractability vs. Worst-Case Intractability