ECCC-Report TR05-015https://eccc.weizmann.ac.il/report/2005/015Comments and Revisions published for TR05-015en-usMon, 31 Jan 2005 14:39:47 +0200
Paper TR05-015
| On Worst-Case to Average-Case Reductions for NP Problems |
Andrej Bogdanov,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2005/015We 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).
Mon, 31 Jan 2005 14:39:47 +0200https://eccc.weizmann.ac.il/report/2005/015