Average-Case Intractability vs. Worst-Case Intractability
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:
Kontaktadresse:
koebler@informatik.hu-berlin.de,
schuler@informatik.uni-ulm.de
Ps-File: Average-Case Intractability vs. Worst-Case Intractability
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
zuletzt geändert:
31.10.05
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English