𝔖 Bobbio Scriptorium
✦   LIBER   ✦

(2+f(n))-SAT and its properties

✍ Scribed by Yunlei Zhao; Xiaotie Deng; C.H Lee; Hong Zhu

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
223 KB
Volume
136
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Consider a formula that contains n variables with the form = 2 ∧ 3, where 2 is an instance of 2-SAT containing m2 2-clauses and 3 is an instance of 3-SAT containing m3 3-clauses. is an instance of ( 2

Most interestingly, we give a candidate, (2 + (log n) k =n 2 )-SAT (k ¿ 2), for natural problems in NP -NPC -P (denoted as NPI) with respect to this (2 + f(n))-SAT model. We prove that the restricted version of it is not in NPC under P = NP. Actually, it is indeed in NPI under some stronger but plausible assumption, speciÿcally, the exponential-time hypothesis.

📜 SIMILAR VOLUMES

cover
El embrujo de Satán (2ª ed.)
✍ Burton Hare 📂 Fiction 📅 1977 🏛 Bolsilibros Bruguera 🌐 Spanish ⚖ 128 KB

Se quedó muda de espanto ante la aparición. Instintivamente se envolvió con la toalla y musitó sin voz:—¿Quién…?Entonces, Gina gritó y retrocedió presa de espanto.Una mano apartó violentamente la negra envoltura. En la mano brillaba el acero de un herrumbroso cuchillo. El movimiento fue tan violento

cover
El embrujo de Satán (2ª ed.)
✍ Burton Hare 📂 Fiction 📅 1973 🏛 ePubLibre 🌐 Spanish ⚖ 128 KB

Se quedó muda de espanto ante la aparición. Instintivamente se envolvió con la toalla y musitó sin voz: —¿Quién…? Entonces, Gina gritó y retrocedió presa de espanto. Una mano apartó violentamente la negra envoltura. En la mano brillaba el acero de un herrumbroso cuchillo. El movimiento fue tan viole

cover
Caricias de satén
✍ Chase, Loretta Lynda 📂 Fiction 📅 2013 🏛 Cisne : Penguin Random House Grupo Editorial 🌐 Spanish ⚖ 179 KB

El segundo libro de la serie Las modistasSophy Noirot podría vender arena a los beduinos, pero vender los diseños de su tienda es harina de otro costal, sobre todo desde que la boda de su hermana Marcelline provocara la ira de una de las damas más preeminentes de Londres. Convertir el escándalo en a

cover
Noches de satén
✍ Anne Mather 📂 Fiction 📅 2016 🌐 Spanish ⚖ 73 KB

De noches frías y solitarias… a noches ardientes de pasiónRachel era una madre divorciada con una hija difícil y un ex esposo irresponsable.Después de conocer a Joe Méndez, su vida dio un vuelco. El irresistible carisma de Joe, su atractivo y su descarnada sexualidad la hicieron salir de su caparazó