TR05-015 Authors: Andrej Bogdanov, Luca Trevisan

Publication: 31st January 2005 14:39

Downloads: 1803

Keywords:

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).