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