Reliable reductions, high sets and low sets
V. Arvind, Johannes Köbler, Martin Mundhenk · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · 1992
Measuring the information content of a set by the space-bounded Kolmogorov complexity of its characteristic sequence, we investigate the (non-uniform) complexity of sets A in EXPSPACE/poly 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, 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.