Falk Unger (CWI Amsterdam): Neuigkeiten über "Dünne selbstreduzierbare Mengen"

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 EXPNP 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 EXPNP 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.