𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On reductions of NP sets to sparse sets

✍ Scribed by Steven Homer; Luc Longpré

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
678 KB
Volume
48
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 (2°(1°g2")).

• 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)co(log n). This implies that, up to relativization, some of our results are optimal.

📜 SIMILAR VOLUMES

On Sparse Complete Sets
On Sparse Complete Sets
✍ Gerd Wechsung 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

SETS by GERD WECHSUNG in Jena (G.D.R.)') 0. Iritroduet,ion and Resnlt,s The consequences of the existence of Theorem 1 ([3]). P = KP o There exists a &-complete sparse set d 7 ~ coNP. Theorem 2 ( [ 7 ] ) . P = N P e There exists a SL-complete sparse set in NP. B precursor of Theorem 2 is contained i

Deterministic and Randomized Bounded Tru
Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets
✍ Dieter van Melkebeek 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 545 KB

We prove that there is no sparse hard set for P under logspace computable bounded truth-table reductions unless P=L. In case of reductions computable in NC 1 , the collapse goes down to P=NC 1 . We parameterize this result and obtain a generic theorem allowing us to vary the sparseness condition, th