Hausdorff Reductions to Sparse Sets and to Sets of High Information Content

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.

Ps-File: Hausdorff Reductions to Sparse Sets and to Sets of High Information Content