ON REDUCTIONS OF NP SETS TO SPARSE SETS

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducib le 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. Amon g 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 a t arbitrary levels of the polynomial hierarchy and which extend as wel l to strong nondeterministic reductions. The construction of an oracle relative to which P not-equal NP but there are NP-complete sets which are f(n)-tt-reducible to a tally set, for any f(n) is-an-element-of o mega (log n). This implies that, up to relativization, some of our res ults are optimal. (C) 1994 Academic Press Inc.