Abstract
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Abstract:
We investigate the complexity of sets that have a rich internal
structure and at the same time are reducible to sets of either
low or very high information content. In particular, we show
that every length-decreasing or word-decreasing self-reducible
set that reduces to some sparse set via a non-monotone variant
of the Hausdorff reducibility is low for P(NP).
Measuring the information content of a set by the space-bounded
Kolmogorov complexity of its characteristic sequence, we
further investigate the (non-uniform) complexity of sets A$ in
EXPSPACE that reduce to some set having very high information
content. Specifically, we show that if the reducibility used
has a certain property, called ``reliability,'' then A in
fact is reducible to a sparse set (under the same
reducibility). As a consequence of our results, the existence
of hard sets (under ``reliable'' reducibilities) of very high
information content is unlikely for various complexity classes
as for example NP, PP, and PSPACE.