Title :
On reductions of NP sets to sparse sets
Author :
Homer, Steven ; Longpré, Luc
Author_Institution :
Dept. of Comput. Sci., Boston Univ., MA, USA
fDate :
30 Jun-3 Jul 1991
Abstract :
M. Ogiwara and O. Watanabe (1990) showed that if SAT is bounded truth-table reducible to a sparse set, then P=NP. In the present work, the authors 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; generalizations of the main theorem which yield results similar to the main result at arbitrary levels of the polynomial hierarchy; and 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)
Keywords :
Turing machines; computational complexity; set theory; NP-complete sets; P≠NP; P=NP; SAT; bounded truth-table reducible; log-Turing reductions; log-truth-table; oracle; polynomial hierarchy; sparse sets; tally set; Complexity theory; Computer science; Educational institutions; Encoding; History; Internet; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-2255-5
DOI :
10.1109/SCT.1991.160246
