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

Let Σ be a finite alphabet. A set S ⊂ Σ ^ * is called sparse if the number of members of S having length at most n is bounded above by a polynomial in n. Let ₘP denote polynomial-time many-one reducibility, and let bpttP denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) bpttP reducibility of a coNP-hard set to a sparse set implies NP = P, and (2) bpttP reducibility of an NP-hard set to a sparse set which is itself in NP implies NP = P. (1) generalizes Fortune’s result [F]. He proved it for the case of ₘP reducibility. (2), for the case of ₘ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 ₘP 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 ₘ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].