Reliable reductions, high sets and low sets
FakultätenFakultät für Ingenieurwissenschaften und Informatik
LizenzStandard (Fassung vom 01.10.2008)
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.
Erstellung / Fertigstellung