Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-015 | 27th January 2005 00:00

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

TR05-015
Authors: Andrej Bogdanov, Luca Trevisan
Publication: 31st January 2005 14:39
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