Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-037 | 29th June 1998 00:00

Average-Case Intractability vs. Worst-Case Intractability

RSS-Feed




TR98-037
Authors: Johannes Köbler, Rainer Schuler
Publication: 30th June 1998 21:46
Downloads: 1437
Keywords: 


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



ISSN 1433-8092 | Imprint