Average-Case Intractability vs. Worst-Case Intractability

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

Authors

• Johannes Köbler
• Rainer Schuler

Keywords

No keywords are indexed for this paper.