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.

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.


Kontaktadresse:
koebler@informatik.hu-berlin.de,
schuler@informatik.uni-ulm.de

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