On Sets Reducible to Sparse Sets∗
Ronald V. Book, Ker‐I Ko · 1987
The main results of this paper may be summarized as follows: (1) For every k > 0, there exist a sparse set S and a set L such that L≤P(k+1)-ttS but there is no sparse set S′ such that L≤Pk-ttS′. Thus, the class of sets that are bounded truth-table reducible to sparse sets can be decomposed into a properly infinite hierarchy based on bounding the number of (nonadaptive) queries that are allowed. (2) There exist a sparse set S and a set L such that L ≤PttS′, but there is no integer k such that for some sparse set S′, L≤Pk-ttS′. Thus the class of sets that are bounded truth-table reducible to sparse sets is properly included in the class of sets that are truth-table reducible to sparse sets. (3) The class of sets that are bounded truth-table reducible to tally sets is equal to the class of sets that axe 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.