Abstract
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.