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

Vikraman Arvind, Johannes Köbler, and Martin Mundhenk

Abstract:

We investigate the complexity of computing small descriptions for sets in various reduction classes to sparse sets. For example, we show that if a set A and its complement conjunctively reduce to some sparse set, then they also are conjunctively reducible to a P(A join SAT)-printable tally set. As a consequence, the class IC[log,poly] of sets with low instance complexity is contained in the first level of the extended low hierarchy. By refining our techniques, we also show that all word-decreasing self-reducible sets in IC[log,poly] are low for NP. We derive similar results for other reduction classes to sparse sets.