On Sets Reducible to Sparse Sets∗
- 1 June 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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)-tt S but there is no sparse set S′ such that L≤ P k-tt S′. 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 ≤ P tt S′, but there is no integer k such that for some sparse set S′, L≤ P k-tt S′. 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.Keywords
This publication has 0 references indexed in Scilit: