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
EXP, or even in EXP^{NP} that are not computed by
polynomial size circuits and hence are not reducible to a sparse
set.

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 [LT91] that EXP^{NP} does not have hard
sparse selfreducible sets. We define a natural version of
selfreduction: tree-selfreducibility, and show that NEXP does
not have hard sparse tree-selfreducible sets. It can be shown that this
result is optimal with respect to relativizing proofs, by exhibiting
an oracle where all of EXP is reducible to a sparse
tree-selfreducible set.

We also prove that log-sparse bounded-truth-table-selfreducible sets are in P.