We investigate the complexity of computing small descriptions for sets in various reduction classes to sparse sets. For example, we show that if a set $A$ and its complement conjunctively reduce to some sparse set, then they also are conjunctively reducible to a $\P(A\oplus\SAT)$-printable tally set. As a consequence, the class $\IC$ of sets with low instance complexity is contained in the $EL_1^{\Sigma}$-level of the extended low hierarchy. By refining our techniques, we also show that all word-decreasing self-reducible sets in $\IC$ are in $\NP\cap\coNP$ and therefore low for $\NP$. We derive similar results for sets in $R^p_d(\Sparse))$ and $R_{hd}^p(R_c^p(\Sparse))$, as well as in some nondeterministic reduction classes to sparse sets.
Back to my homepage