| Complexity of Some Problems Concerning 2CNF Formulas |
| |
| 作者姓名： | Hans Kleine Büning |
| |
| 作者单位： | 帕德恩大学 教授 |
| |
| 摘 要： | In this paper we investigate the complexity of several problems concerning 2CNF formulas. At first, we show that the minimal unsatisfiability problem for 2CNF formulas can be solved in linear time. Then we prove that the problem determining if a 2CNF formula can be transformed to a minimal unsatisfiable formula is also solvable in linear time. Thirdly, we show the polynomial solvability of the satisfiability problem for symmetric monotone formulas in which all clauses has length 2 or ? n - k ( n is the number of variables and k is a fixed positive integer). Finally, we prove that the satisfiability of symmetric monotone formulas in which each literal occurs at most twice depends only on the 2-clauses they contains.
|
Complexity of Some Problems Concerning 2CNF Formulas |
| |
| Xishun Zhao Hans Kleine Buning Decheng Ding.Complexity of Some Problems Concerning 2CNF Formulas[J].Journal of Sun Yatsen University(Social Science Edition),2003(Z1). |
| |
| Authors: | Xishun Zhao Hans Kleine Buning Decheng Ding |
| |
| Abstract: | In this paper we investigate the complexity of several problems concerning 2CNF formulas. At first, we show that the minimal unsatisfiability problem for 2CNF formulas can be solved in linear time. Then we prove that the problem determining if a 2CNF formula can be transformed to a minimal unsatisfiable formula is also solvable in linear time. Thirdly, we show the polynomial solvability of the satisfiability problem for symmetric monotone formulas in which all clauses has length 2 or ? n - k ( n is the number of variables and k is a fixed positive integer). Finally, we prove that the satisfiability of symmetric monotone formulas in which each literal occurs at most twice depends only on the 2-clauses they contains. |
| |
| Keywords: | minimal unsatisfiable formulas symmetric monotone formulas satisfiability complexity |
| 本文献已被 CNKI 等数据库收录！ |
