Lowness and the Complexity of Sparse and Tally Descriptions
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.
Ps-File: Lowness and the Complexity of Sparse and Tally Descriptions