Lowness and the complexity of sparse and tally descriptions
FakultätenFakultät für Ingenieurwissenschaften und Informatik
LizenzStandard (Fassung vom 01.10.2008)
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.
Erstellung / Fertigstellung
Normierte SchlagwörterComputational complexity [LCSH]
Sparse matrices [LCSH]