𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On random reductions from sparse sets to tally sets

✍ Scribed by Uwe Schöning

Book ID
107766115
Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
248 KB
Volume
46
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On reductions of NP sets to sparse sets
On reductions of NP sets to sparse sets
✍ Steven Homer; Luc Longpré 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 678 KB

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-tabl

On Sets Cook-Reducible to Sparse Sets
On Sets Cook-Reducible to Sparse Sets
✍ Solovay, Robert M. 📂 Article 📅 1976 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 694 KB
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