ECCC-Report TR10-163https://eccc.weizmann.ac.il/report/2010/163Comments and Revisions published for TR10-163en-usWed, 03 Nov 2010 11:17:39 +0200
Paper TR10-163
| Sparse Selfreducible Sets and Nonuniform Lower Bounds |
Nikolay Vereshchagin,
Harry Buhrman,
Leen Torenvliet,
Falk Unger
https://eccc.weizmann.ac.il/report/2010/163It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even in EXP that are not computable by polynomial size circuits and hence are not reducible to a sparse set. In this paper we study this question in a more restricted setting: what is the computational complexity of sparse sets that are selfreducible? It follows from earlier work of Lozano and Toran that $EXP^{NP}$ does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that NEXP does not have sparse tree-selfreducible hard sets. We also construct an oracle relative to which all of EXP is reducible to a sparse tree-selfreducible set. These lower bounds are corollaries of more general results about the computational complexity of sparse sets that are selfreducible, and can be interpreted as uper-polynomial circuit lower bounds for NEXP.
Wed, 03 Nov 2010 11:17:39 +0200https://eccc.weizmann.ac.il/report/2010/163