Simplifying the propositional satisfiability problem by sub-model propagation

被引:0
作者
Kusper, Gabor [1 ]
Csoke, Lajos [1 ]
Kovasznai, Gergely [1 ]
机构
[1] Eszterhazy Karoly Coll, Inst Math & Informat, POB 43, H-3301 Eger, Hungary
来源
ANNALES MATHEMATICAE ET INFORMATICAE | 2008年 / 35卷
关键词
SAT; blocked clause; nondecisive clause;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We describes cases when we can simplify, a general SAT problem instance by sub-model propagation. Assume that we test our input clause set whether it is blocked or not, because we know that a blocked clause set can be solved in polynomial time. If the input clause set is not blocked, but some clauses are blocked, then what can we do? Can we use the blocked clauses to simplify the clause set? The Blocked Clear Clause Rule and the Independent Blocked Clause Rule describe cases when the answer is yes. The other two independent clause rules, the Independent Nondecisive-and Independent Strongly Nondecisive Clause Rules describe cases when we can use nondecisive and strongly nondecisive clauses to simplify a general SAT problem instance.
引用
收藏
页码:75 / 94
页数:20
相关论文
共 20 条
  • [1] LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS
    ASPVALL, B
    PLASS, MF
    TARJAN, RE
    [J]. INFORMATION PROCESSING LETTERS, 1979, 8 (03) : 121 - 123
  • [2] Aspvall B., 1980, J ALGORITHMS, V1, P97, DOI DOI 10.1016/0196-6774(80)90007-3
  • [3] RECOGNITION IN Q-HORN FORMULAS IN LINEAR-TIME
    BOROS, E
    HAMMER, PL
    SUN, XR
    [J]. DISCRETE APPLIED MATHEMATICS, 1994, 55 (01) : 1 - 13
  • [4] A COMPLEXITY INDEX FOR SATISFIABILITY PROBLEMS
    BOROS, E
    CRAMA, Y
    HAMMER, PL
    SAKS, M
    [J]. SIAM JOURNAL ON COMPUTING, 1994, 23 (01) : 45 - 49
  • [5] EXTENDED HORN SETS IN PROPOSITIONAL LOGIC
    CHANDRU, V
    HOOKER, JN
    [J]. JOURNAL OF THE ACM, 1991, 38 (01) : 205 - 221
  • [6] Cheeseman P., 1991, 12TH P INT JOINT C A, V91, P331, DOI DOI 10.1109/PHYCMP.1992.615495
  • [7] Cook S. A., 1971, Proceedings of the 3rd annual ACM symposium on theory of computing, P151
  • [8] A HIERARCHY OF TRACTABLE SATISFIABILITY PROBLEMS
    DALAL, M
    ETHERINGTON, DW
    [J]. INFORMATION PROCESSING LETTERS, 1992, 44 (04) : 173 - 180
  • [9] LINEAR-TIME ALGORITHMS FOR TESTING THE SATISFIABILITY OF PROPOSITIONAL HORN FORMULAE.
    Dowling, William F.
    Gallier, Jean H.
    [J]. Journal of Logic Programming, 1984, 1 (03): : 267 - 284
  • [10] Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048