Abstract
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Abstract:
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 belongs to R_r(S). By establishing such upper bounds we
are able to derive the lowness of A.
In particular, we show that the closure of sparse sets under bounded
truth-table reductions (as well as the closure under disjunctive
reductions) is located in the third theta level of the extended low
hierarchy. Finally, we construct for every set A in IC[log,poly] a
tally set T in P(A join SAT) such that A is in P_ctt(T) and in
P_dtt(T). This implies that the class IC[log,poly] of sets with low
instance complexity is contained in first level of the extended low
hierarchy.