Self-reducible sets have a rich internal structure. The information contained in these sets is encoded in some redundant way. Therefore a lot of the information of the set is easily accessible. In this paper it is investigated how this self-reducibility structure of a set can be used to access easily {\em all} information contained in the set, if its information content is small. It is shown that $\P$ can be characterized as class of self-reducible sets which are ``almost'' in $\P$ (i.e.~sets in $\APT'$). Self-reducible sets with low instance complexity (i.e.~sets in $\IC$) are shown to be in $\NP\cap\coNP$, and sets which disjunctively reduce to sparse sets or which belong to a certain superclass of the Boolean closure of sets which conjunctively reduce to sparse sets are shown to be in $\P^{\NP}$, if they are self-reducible in a little more restricted sense of self-reducibility.
Back to my homepage