Average-case intractability vs. worst-case intractability

We show that not all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms unless the Arthur-Merlin classes MA and AM can be derandomized to NP and various subclasses of P/poly collapse to P. Furthermore, other complexity classes like P(PP) and PSPACE are shown to be intractable on average unless they are easy in the worst case.

Authors

• Johannes Köbler
• Rainer Schuler

Keywords

No keywords are indexed for this paper.