Lowness and the complexity of sparse and tally descriptions
FakultätFakultät für Ingenieurwissenschaften und Informatik
Ressourcen- / MedientypArbeitspapier, Text
Datum der Freischaltung2009-08-09
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(SPARSE) to the class of sparse sets. Then we are interested in finding upper bounds for the complexity (relative to A) of sparse sets S such that A is in 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+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.
LizenzStandard (Fassung vom 01.10.2008)