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

Zbl 0356.68059
Full Text: