✦ LIBER ✦

Comparing reductions to NP-complete sets

✍ Scribed by John M. Hitchcock; A. Pavan

Book ID: 113641664
Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 210 KB
Volume: 205
Category: Article
ISSN: 0890-5401
DOI: 10.1016/j.ic.2006.10.005

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Splitting NP-Complete Sets

✍ Glaßer, Christian; Pavan, A.; Selman, Alan L.; Zhang, Liyu 📂 Article 📅 2008 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 234 KB

Properties of NP‐Complete Sets

✍ Glaßer, Christian; Pavan, A.; Selman, Alan L.; Sengupta, Samik 📂 Article 📅 2006 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 291 KB

Computing the dimension ofN-free ordered

Computing the dimension ofN-free ordered sets is NP-complete

✍ H. A. Kierstead; S. G. Penrice 📂 Article 📅 1989 🏛 Springer Netherlands 🌐 English ⚖ 151 KB

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

Even initial feedback vertex set problem

Even initial feedback vertex set problem is NP-complete

✍ Dan A. Simovici; Gh. Grigoras 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 451 KB