Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ic.2003.05.002 | Information & Computation |
Keywords | Field | DocType |
various subclasses,polynomial-time hierarchy,arthur-merlin class,worst-case intractability,poly collapse,worst case,complexity class,efficient average-case algorithm | Complexity class,Discrete mathematics,Combinatorics,NP-complete,PSPACE,Hierarchy,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
190 | 1 | Information and Computation |
ISBN | Citations | PageRank |
3-540-64827-5 | 3 | 0.39 |
References | Authors | |
54 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Rainer Schuler | 2 | 3 | 0.39 |