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. (C) 2003 Elsevier Inc. All rights reserved. [References: 57]