✦ LIBER ✦

Sumsets of dense sets and sparse sets

✍ Scribed by John T. Griesmer

Book ID: 118819148
Publisher: The Hebrew University Magnes Press
Year: 2012
Tongue: English
Weight: 374 KB
Volume: 190
Category: Article
ISSN: 0021-2172
DOI: 10.1007/s11856-012-0008-1

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sumsets of sparse sets

✍ Artūras Dubickas, Paulius Šarka 📂 Article 📅 2012 🏛 Springer Netherlands 🌐 English ⚖ 125 KB

Diameter of sets and measure of sumsets

✍ Imre Z. Ruzsa 📂 Article 📅 1991 🏛 Springer Vienna 🌐 English ⚖ 196 KB

Sumsets contained in infinite sets of in

Sumsets contained in infinite sets of integers

✍ Melvyn B Nathanson 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 293 KB

On Sets Cook-Reducible to Sparse Sets

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