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.