最坏情况下Min-2SAT问题的上界

摘要：

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.

关键词：MaxSAT、MinSAT、Min-2SAT、MaxSAT问题的上界、Min-2SAT问题的上界、子句数目、分支树

所属期刊栏目：7

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61070084;国家自然科学青年基金资助项目60803102;中央高校基本科研业务费专项资金资助项目11QNJJ006

在线出版日期：2012-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：241-245