第7卷第3期 智能系统学报 Vol.7 No.3 2012年6月 CAAI Transactions on Intelligent Systems Jun.2012 D0I:10.3969/j.i8sn.1673-4785.201109003 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120510.1619.001.html 最坏情况下Min-2SAT问题的上界 谷文祥12，姜蕴晖，周俊萍，般明浩 (1.东北师范大学计算机科学与信息技术学院，吉林长春130117；2.长春建筑学院基础教学部，吉林长春130607) 摘要：最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题， 在求解某些组合优化问题时，将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度，因此对MinSAT问题 进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简，然后通过分 支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Mi2SAT问题可在 0(1.1343")时间内求解，对于每个变量至多出现在3个2-子句中的情况，得到最坏情况下的上界为0(1.1225)， 其中n为变量的数目. 关键词：MaxSAT:MinSAT;Min-2SAT;MaxSAT问题的上界：Min-2SAT问题的上界；子句数目；分支树 中图分类号：TP301文献标志码：A文章编号：16734785(2012)030241-05 New worst-case upper bounds for Min-2SAT problems GU Wenxiang2,JIANG Yunhui',ZHOU Junping',YIN Minghao' (1.School of Computer Science and Information Technology,Northeast Normal University,Changchun 130117,China;2.Department of Basic Subjects Teaching,Changchun Architecture Civil Engineering College,Changchun 130607,China) Abstract:The rigorous theoretical analyses of algorithms for solving the upper bounds of maximum satisfiability MaxSAT)problems have been proposed in research literature.The opposite problem of MaxSAT is the minimum satisfiability (MinSAT)problem.Solving some combinatorial optimization problems by reducing them to MinSAT form may be substantially faster than reducing them to MaxSAT form,so the MinSAT problem was researched in this paper.An algorithm(MinSATAlg)was presented for the minimum two-satisfiability (Min-2SAT)problem.In this paper,first,the simplification algorithm Simplify was used for simplification of formulas.Secondly,the branching tree method was used for branching on different kinds of clauses.It was proven that this algorithm can solve the Min-2SAT problem in 0(1.134 3),regarding the number of clauses as parameters.The upper bound in the worst case was derived as 0(1.122 5"),where n is the number of variables in an input formula for a particu- lar case of Min-2SAT in which each variable appears in three 2-clauses at most. Keywords:maximum satisfiability;minimum satisfiability;minimum two-satisfiability;upper bounds for maximum satisfiability;upper bounds for minimum two-satisfiability;number of clauses;branching tree 人工智能研究领域存在着很多计算困难的问 时间的求解算法.这时从理论上分析这些问题在最 题，如SAT(satisfiability)问题、QBF(quantified boole- 坏情况下的时间复杂性上界尤为重要，因为此时对 an formula)问题、智能规划问题、模型诊断问题等. 该上界的一个微小的改进，例如从O(c)改进为 若P≠NP成立，人们将无法为这些问题找到多项式 O((c-ε))，就会使得问题求解的算法在效率上获 得指数级别的提高.以SAT问题为例，作为第一个 收稿日期：20110906.网络出版日期：201205-10. 基金项目：国家自然科学基金资助项目(61070084)；国家自然科学青 被证明是NP完全的问题，改进其在最坏情况下的 年基金资助项目(60803102)；中央高校基本科研业务费专 时间上界受到了研究人员的广泛关注.MaxSAT 项资金资助项目(11QNJJ006) 通信作者：姜蕴晖.E-mail:jiangyh2l5@nenu.ed血.cn (maximum satisfiability)问题是SAT问题的扩展，它