Polynomial time bounded truth-table reducibilities to padded sets

Glasnák, Vladimír

Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) no. 4, pp. 773-792.

Résumé

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class $f\text{\it -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: $$ R_{\text{\rm m}}(f\text{\it -PAD})\subsetneq R_{1\text{\rm -tt}}(f\text{\it -PAD}) \subsetneq \dots \subsetneq R_{\text{\rm btt}}(f\text{\it -PAD}), \text{ or} \ R_{\text{\rm m}}(f\text{\it -PAD}) = R_{1\text{\rm -tt}}(f\text{\it -PAD})\subsetneq \dots \subsetneq R_{\text{\rm btt}}(f\text{\it -PAD}), \text{ or} \ R_{\text{\rm m}}(f\text{\it -PAD}) = R_{\text{\rm btt}}(f\text{\it -PAD}). $$

Détail

Classification : 03D15, 03D30, 68Q15, 68Q17
Keywords: computational complexity; sparse set; padded set; reducibility