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 ...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 ...展开更多
文摘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 ...
