Advanced Search

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class $f\mathit{\text{-PAD}}$ of all $f$-padded sets, if it is a subset of $\{x{10}^{f\left(\right|x\left|\right)-\left|x\right|-1};x\in {\{0,1\}}^{*}\}$). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...