Sparse Selfreducible Sets and Nonuniform Lower Bounds

It 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 \({\mathrm{EXP^{NP}}}\), or even in \({\mathrm{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 (in: Mathematical systems theory, 1991) that \({\mathrm{EXP^{NP}}}\) does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that \({\mathrm{NEXP}}\) does not have sparse tree-selfreducible hard sets. We also construct an oracle relative to which all of \({\mathrm{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 super-polynomial circuit lower bounds for \({\mathrm{NEXP}}\).