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.


68Q25 Analysis of algorithms and problem complexity
03D30 Other degrees and reducibilities in computability and recursion theory


Zbl 0356.68059
Full Text: DOI