✦ LIBER ✦

On Sets Cook-Reducible to Sparse Sets

✍ Scribed by Solovay, Robert M.

Book ID: 118169403
Publisher: Society for Industrial and Applied Mathematics
Year: 1976
Tongue: English
Weight: 694 KB
Volume: 5
Category: Article
ISSN: 0097-5397
DOI: 10.1137/0205043

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On sets turing reducible to p-selective

On sets turing reducible to p-selective sets

✍ H. J. Burtschick; W. Lindner 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 506 KB

On Sets Turing Reducible to p-Selective

On Sets Turing Reducible to p-Selective Sets

✍ H.-J. Burtschick 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 97 KB

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 random reductions from sparse sets to

On random reductions from sparse sets to tally sets

✍ Uwe Schöning 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 248 KB

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

With Quasilinear Queries EXP Is Not Poly

With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets

✍ Fu, Bin 📂 Article 📅 1995 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 1005 KB