Andrej Bogdanov, Luca Trevisan

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

more >>>