On reductions of NP sets to sparse sets

摘要

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following:•Applications of the main theorem to log-truth-table and log-Turing reductions of NP sets to sparse sets. One typical example is that if SAT is log-truth-table reducible to a sparse set then NP is contained in DTIME (2O(log2n)).•Generalizations of the main theorem which yields results similar to the main result at arbitrary levels of the polynomial hierarchy and which extend as well to strong nondeterministic reductions.•The construction of an oracle relative to which P ≠ NP but there are NP-complete sets which are f(n)-tt-reducible to a tally set, for any f(n) ε ω(log n). This implies that, up to relativization, some of our results are optimal.