Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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