We investigate the complexity of obtaining sparse descriptions for sets in various reduction classes to sparse sets. Let $A$ be a set in a certain reduction class $R_r(\Sparse)$. Then we are interested in finding upper bounds for the complexity (relative to $A$) of sparse sets $S$ such that $A\in R_r(S)$. By establishing such upper bounds we are able to derive the lowness of $A$. In particular, we show that if a set $A$ is in the class $R_{hd}^p(R_c^p(\Sparse))$ then $A$ is in $R_{hd}^p(R_c^p(S))$ for a sparse set $S\in\NP(A)$. As a consequence we can locate $R^p_{hd}(R^p_{c}(\Sparse))$ in the $EL^{\Theta}_3$ level of the extended low hierarchy. Since $R^p_{hd}(R^p_{c}(\Sparse))\supseteq R^p_{b}(R^p_{c}(\Sparse))$ this solves the open problem of locating the closure of sparse sets under bounded truth-table reductions optimally in the extended low hierarchy. Furthermore, we show that for every $A\in R^p_d(\Sparse)$ there exists a sparse set $S\in\NP(A\oplus\SAT)/\FThetap_2(A)$ such that $A\in R^p_d(S)$. Based on this we show that $R^p_{1-tt}(R^p_{d}(\Sparse))$ is in $EL^{\Theta}_3$. Finally, we construct for every set $A\in R^p_c(\tally)\cap R^p_d(\tally)$ (or equivalently, $A\in\IC$, as shown in~\cite{ten92}) a tally set $T\in\P(A\oplus\SAT)$ such that $A\in R^p_c(T)\cap R^p_d(T)$. This implies that the class $\IC$ of sets with low instance complexity is contained in $EL_1^{\Sigma}$.
Back to my homepage