Title of article
Computational complexity of some restricted instances of 3-SAT
Author/Authors
Piotr Berman، نويسنده , , Marek Karpinski، نويسنده , , Alexander D. Scott، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2007
Pages
5
From page
649
To page
653
Abstract
Tovey [A simplified satisfiability problem, Discrete Appl. Math. 8 (1984) 85–89] showed that it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times, while every instance of 3-SAT in which each variable occurs three times is satisfiable. We explore the border between these two problems. Answering a question of
Journal title
Discrete Applied Mathematics
Serial Year
2007
Journal title
Discrete Applied Mathematics
Record number
886450
Link To Document