Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-015 | 27th January 2005 00:00

On Worst-Case to Average-Case Reductions for NP Problems

RSS-Feed




TR05-015
Authors: Andrej Bogdanov, Luca Trevisan
Publication: 31st January 2005 14:39
Downloads: 1017
Keywords: 


Abstract:

We show that if an NP-complete problem has a non-adaptive
self-corrector with respect to a samplable distribution then
coNP is contained in NP/poly and the polynomial
hierarchy collapses to the third level. Feigenbaum and
Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion
under the stronger assumption that an
NP-complete problem has a non-adaptive random self-reduction.

Our result shows that the average-case hardness of a problem in
NP or the security of a one-way function cannot be
based (using non-adaptive reductions) on the worst-case complexity
of an \np-complete problem (unless the polynomial hierarchy
collapses).



ISSN 1433-8092 | Imprint