Details

Autor(en) / Beteiligte

• Köbler, Johannes
• Schuler, Rainer

Titel

Average-case intractability vs. worst-case intractability

Ist Teil von

• Lecture notes in computer science, 1998, p.493-502

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

1998

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 show for C ∃ {P(PP), PSPACE} that C is not tractable in the average-case unless C=P.