×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI