On Sets Truth-Table Reducible to Sparse Sets
Ronald V. Book, Ker‐I Ko · SIAM Journal on Computing · 1988
We study sets that are truth-table reducible to sparse sets in polynomial time. The principal results are as follows: (1) For every integer $k > 0$, there is a set L and a sparse set S such that $L \leqq _{(k + 1) - tt}^P S$, but there is no sparse set $S'$ such that $L \leqq _{k - tt}^P S'$. (2) There exist a sparse set S and a set L such that $L \leqq _{tt}^P S$ but there is no integer k such that for some sparse $S'$, $L \leqq _{k - tt}^P S'$. (3) The class of sets that are bounded truth-table reducible to tally sets is equal to the class of sets that are many–one reducible to tally sets. (4) The class of sets having polynomial-size circuits is equal to the class of sets that are truth-table reducible to tally sets. Similar results are developed for truth-table reducibilities that are computed nondeterministically in polynomial time or in polynomial space.