##
**Two results on polynomial time truth-table reductions to sparse sets.**
*(English)*
Zbl 0532.68051

This work is inspired by the recent solution by S. Mahaney of the Berman- Hartmanis conjecture [J. Hartmanis and L. Berman, ibid. 6, 305-322 (1977; Zbl 0356.68059] that NP cannot have a sparse complete set for many-one polynomial-time reductions unless \(P=NP\). The paper analyzes the implications of NP and PSPACE having sparse sets that are hard or complete for reduction types more general than the many-one reductions. Three special cases of truth-table reductions are considered. It is shown that if NP (PSPACE) has a tally \(\leq^ P_{k-T}\)-hard set, then \(P=NP (P=PSPACE)\). Here \(\leq^ P_{k-T}\) denotes a subcase of polynomial-time Turing reducibility in which, for some constant k, the reducing Turing machine is allowed to make at most k queries to the oracle. It as also shown that if co-NP (PSPACE) has a sparse hard set for conjunctive polynomial time reductions, then \(P=NP (P=PSPACE)\). Closely related results have recently been obtained also by C. K. Yap and by Y. Yesha.

### MSC:

68Q25 | Analysis of algorithms and problem complexity |

03D30 | Other degrees and reducibilities in computability and recursion theory |