Computational complexity of some restricted instances of 3-SAT |
| |
Authors: | Piotr Berman Marek Karpinski Alexander D Scott |
| |
Institution: | a Department of Computer Science and Engineering, Pennsylvania State University, USA b Department of Computer Science, University of Bonn, Germany c Department of Mathematics, University College London, Gower Street, London WC1E 6BT, UK |
| |
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 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|