Abstract:We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class $f\text {-PAD}$ of all $f$-padded sets, if it is a subset of $\{x10^{f(|x|)-|x|-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 function $f$ measuring ``holes'' in its image, one of the following three possibilities happen: $$ \gather R_{\text {m}}(f\text {-PAD})\subsetneq R_{1\text {-tt}}(f\text {-PAD}) \subsetneq...\subsetneq R_{\text {btt}}(f\text {-PAD}), \text { or} R_{\text {m}}(f\text {-PAD}) = R_{1\text {-tt}}(f\text {-PAD})\subsetneq...\subsetneq R_{\text {btt}}(f\text {-PAD}), \text { or} R_{\text {m}}(f\text {-PAD}) = R_{\text {btt}}(f\text {-PAD}). \endgather $$
Keywords: computational complexity, sparse set, padded set, reducibility
AMS Subject Classification: 68Q15