| Computational Complexity of Some Restricted Instances of 3SAT (2008) | |||||||||||||
Abstract | |||||||||||||
| Tovey [10] 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 Iwama and Takaki, we show that, for every fixed k ≥ 0, there is a polynomial time algorithm to determine the satisfiability of 3-SAT instances in which k variables occur four times and the remaining variables occur three times. On the other hand, it is NP-hard to decide the satisfiability of 3-SAT instances in which all but one variable occurs three times, and the remaining variable is allowed to occur an arbitrary number of times. 1 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||