Title of article
Satisfiable Formulas Closed Under Replacement
Author/Authors
Hans Kleine Büning، نويسنده , , Hans and Xishun، نويسنده , , Zhao، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
11
From page
48
To page
58
Abstract
Let Var-SAT be the set of prepositional formulas which are satisfiable for any replacement of any set of literals by their complements. We discuss the complexity of Var-SAT. For 2-CNF -formulas we present a linear-time algorithm, and for DNF⩕ CNF -formulas we show the coNP—hardness of the problem Var-SAT. Further, we show that any satisfiable hitting formula and any proper subformula of a minimal unsatisfiable Horn-formula is in Var-SAT.
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2001
Journal title
Electronic Notes in Discrete Mathematics
Record number
1453222
Link To Document