Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
Esko Ukkonen · SIAM Journal on Computing · 1983
Inspired by the recent solution of the Berman-Hartmanis conjecture [SIAM J. Comp., 6 (1977), pp. 305–322] that NP cannot have a sparse complete set for many-one reductions unless ${\text{P}} = {\text{NP}}$, we analyze the implications of NP and PSPACE having sparse, hard or complete sets for reduction types more general than the many-one reductions. Three special cases of truth-table reductions are considered. First we show that if NP (PSPACE) has a tally $ \leqq _{k - T}^P $-hard set, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$. Here $ \leqq _{k - T}^P $ 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. We also show that if co-NP (PSPACE) has a sparse hard set for conjunctive polynomial time reductions, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$.