第3期 谷文祥，等：最坏情况下Min2SAT问题的上界 ·245· 0(1.1225m) [7]BINKELE-RAIBLE D,FERNAU H.A new upper bound for 综上所述，给定一个2-CNF范式，算法Min Max-2-SAT:a graph-theoretic approach[].Joumal of Dis- SATAlg在O(1.1343m)时间内返回公式中同时可 crete Algorithms,2010,8(4):388-401. [8]GASPERS S,SORKIN G B.A universally fastest algorithm 以满足的最少的子句数，即定理2得证 for Max 2-Sat,Max 2-CSP,and everything in between[J]. 4结束语 Joural of Computer and System Sciences,2012,78(1): 305-335. MaxSAT问题是求解人工智能和组合优化问题 [9 AVIDOR A,ZWICK U.Approximating MIN 2-SAT and 的基础，而在求解某些组合优化问题时，将其转化为 MIN 3-SAT[J].Theory of Computing Systems,2005,38 MinSAT问题比MaxSAT问题有着更快的速度，因此 (3):329-345. 求解MinSAT问题并分析其复杂度有着很高的实际 [10]MARATHE M V,RAVI S S.On approximation algorithms for the minimum satisfiability problem J].Information 价值.本文研究了MinSAT问题中每个子句长度不 Processing Letters,1996,58(1):23-29. 大于2的情况，即Min-2SAT问题，提出了一个求解 [11]LI Chumin,MANYA F,QUAN Zhe,et al.Exact MinSAT Mn-2SAT问题的算法并证明了算法的时间复杂度 solving[C]//Proceedings of the 13th Interational Confer- 为0(1.1343)，其中m为公式中子句的数目.笔者 ence on Theory and Applications of Satisfiability Testing. 运用了一种新的复杂性测度来测量算法的运行时 Berlin/Heidelberg,Germany:Springer-Verlag,2010: 间.另外还证明了对于每个变量至多出现在3个2 363-368. 子句中的情况，其最坏情况下的时间复杂度为 [12]ZHOU Junping,YIN Minghao,ZHOU Chunguang.New 0(1.1225"),其中n为变量的数目. worst-case upper bound for #2-SAT and #3-SAT with the number of clauses as the parameter[C]//Proceedings of 在今后的工作中，可以进一步修正复杂性测度 the Twenty-Fourth AAAI Conference on Artificial Intelli- 或通过加入冲突子句等方法，来改善算法并减少算 gence.Atlanta,USA,2010. 法的时间复杂度 [13]KOJEVNIKOV A,KULIKOV A S.A new approach to pro- ving upper bounds for MAX-2-SAT[C]//Proceedings of 参考文献： the Seventeenth Annual ACM-SIAM Symposium on Dis- [1]HANSEN P,JAUMARD B.Algorithms for the maximum crete Algorithms.New York,USA:ACM,2006:11-17. satisfiability problem[J].Computing,1990,44(4):279- 作者简介： 303. 谷文祥，男，1947年生，教授，博士 [2]WALLACE R J.Enhancing maximum satisfiability algo- 生导师，主要研究方向为智能规划与规 rithms with pure literal strategies[C]//Proceedings of the 划识别.主持或参与国家自然科学基金 11th Biennial Conference of the Canadian Society for Com- 项目5项、教育部重点项目2项、省科 putational Studies of Intelligence on Advances in Artificial 委项目1项.发表学术论文130余篇， Intelligence.London,UK:Springer-Verlag,1996:388- 出版专著《智能规划与规划识别》，2011 401. 年获得吉林省专著类一等奖， [3]NIEDERMEIER R,ROSSMANITH P.New upper bounds for MaxSat[C]//Proceedings of the 26th Interational Col- 姜蕴晖，女，1987年生，硕士研究生， loquium on Automata,Languages and Programming.Lon- 主要研究方向为智能规划与自动推理。 don,UK:Springer-Verlag,1999:575-584. [4]GRAMM J,HIRSCH E A,NIEDERMEIER R,et al. Worst-case upper bounds for MAX-2-SAT with an applica- tion to MAX-CUT [J].Discrete Applied Mathematics, 2003,130(2):139-155. [5]KNEIS J,ROSSMANITH P.A new satisfiability algorithm 周俊萍，女，1981年生，讲师，主要 with applications to Max-Cut:Technical Report AIB2005-08 研究方向为智能规划与自动推理，发表 [R].Aachen,Germany:Department of Computer Science, 学术论文5篇. RWTH Aachen University,2005. [6]KULIKOV A S,KUTZKOV K.New bounds for MAX-SAT by clause learning C]//2nd International Symposium on Computer Science in Russia.Ekaterinburg,Russia,2007: 194-204