On certain polynomial-time truth-table reducibilities of complete sets to sparse sets. (English) Zbl 0545.03023

(From author’s abstract.) Let \(\Sigma\) be a finite alphabet. A set \(S\subseteq \Sigma^*\) is called sparse if the number of members of S having length at most n is bounded by a polynomial in n. Let \(\leq^ P_ m\) denote polynomial-time many-one reducibility, and let \(\leq^ P_{bptt}\) denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) \(\leq^ P_{bptt}\) reducibility of a coNP-hard set to a sparse set implies \(NP=P\), and (2) \(\leq^ P_{bptt}\) reducibility of an NP-hard set to a sparse set which is itself in NP implies \(NP=P\). (1) generalizes Fortune’s result. He proved it for the case of \(\leq^ P_ m\) reducibility. (2), for the case of \(\leq^ P_ m\) reducibility, was proved by Mahaney, even without assuming that the sparse set itself is in NP. Our results imply that if a coNP-hard set is a finite union of sets which are \(\leq^ P_ m\) reducible to sparse sets, then \(NP=P\). We then investigate a certain nonpositive polynomial-time truth-table reducibility of NP-hard sets to sparse sets, and obtain new results regarding the structure of sets hard for NP or for ETIME. Finally, we investigate the possibility of existence of sets in NP-coNP which are \(\leq^ P_ m\) reducible to sparse sets. Some of our techniques involve generalizations of and variations on the techniques of Berman, Fortune and Mahaney.
Reviewer: P.Clote


03D10 Turing machines and related notions
03D15 Complexity of computation (including implicit computational complexity)
03D30 Other degrees and reducibilities in computability and recursion theory
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI