Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Mitsunori Ogiwara, Osamu Watanabe · SIAM Journal on Computing · 1991
It is proved that if ${\text{P}} e {\text{NP}}$, then there exists a set in ${\text{NP}}$ that is not polynomial-time bounded truth-table reducible (in short, $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible) to any sparse set. In other words, it is proved that no sparse $ \leqq _{{\text{btt}}}^{\text{P}} $-hard set exists for ${\text{NP}}$ unless ${\text{P}} = {\text{NP}}$. By using the technique proving this result, the intractability of several number-theoretic decision problems, i.e., decision problems defined naturally from number-theoretic problems is investigated. It is shown that for these number-theoretic decision problems, if it is not in ${\text{P}}$, then it is not $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible to any sparse set.