Polynomial time bounded truth-table reducibilities to padded sets. (English) Zbl 1051.03029

Glasnák, Vladimír

Commentat. Math. Univ. Carol. 41, No. 4, 773-792 (2000).

Summary: 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. 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{m}}(f\text{-PAD})\subsetneq R_{\text{1-tt}} (f\text{-PAD}) \subsetneq \cdots \subsetneq R_{\text{btt}}(f\text{-PAD}), \text{ or } R_{\text{m}}(f\text{-PAD}) = R_{\text{1-tt}} (f\text{-PAD})\subsetneq \cdots \subsetneq R_{\text{btt}}(f\text{-PAD}), \text{ or } R_{\text{m}}(f\text{-PAD}) = R_{\text{btt}} (f\text{-PAD})\).

MSC:

03D15	Complexity of computation (including implicit computational complexity)
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30	Other degrees and reducibilities in computability and recursion theory
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

computational complexity; sparse set; padded set; reducibility