On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

Abstract

Let $\Sigma $ be a finite alphabet. A set $S \subset \Sigma ^ * $ is called sparse if the number of members of S having length at most n is bounded above by a polynomial in n. Let $ \leqq _m^P $ denote polynomial-time many-one reducibility, and let $ \leqq _{bptt}^P $ denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) $ \leqq _{bptt}^P $ reducibility of a coNP-hard set to a sparse set implies ${\text{NP}} = {\text{P}}$, and (2) $ \leqq _{bptt}^P $ reducibility of an NP-hard set to a sparse set which is itself in NP implies ${\text{NP}} = {\text{P}}$. (1) generalizes Fortune’s result [F]. He proved it for the case of $ \leqq _m^P $ reducibility. (2), for the case of $ \leqq _m^P $ reducibility, was proved by Mahaney [M], 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 $ \leqq _m^P $ reducible to sparse sets, then ${\text{NP}} = {\text{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 $ \leqq _m^P $ reducible to sparse sets. Some of our techniques involve generalizations of and variations on the techniques of Berman [B], Fortune [F] and Mahaney [M].