Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
1983; Society for Industrial and Applied Mathematics; Volume: 12; Issue: 3 Linguagem: Inglês
10.1137/0212038
ISSN1095-7111
Autores Tópico(s)Computability, Logic, AI Algorithms
ResumoInspired 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}})$.
Referência(s)