《最坏情况下X2SAT问题的上界》由会员分享，可在线阅读，更多相关《最坏情况下X2SAT问题的上界（1页珍藏版）》请在金锄头文库上搜索。
1、计算机研究与发展Journal of Computer Research and Development1X)1： 10. 7544/issnlOOO-1239. 2014. 2012058751(3)： 598-605 2014最坏情况下x2sat问题的上界周俊萍W殷明浩(东北师范大学计算机科学与信息技术学院长春130117)(planningnenu edu cn)New Worst-Case Upper Bounds for X2SATZhou Junpingt Jiang Yunhuit and Yin MinghaoSchool of Computer Science and Inf
2、ormation Technology. Northeast Normal University 9 Changchun 130117)Abstract The problem of X?SAT is a generalized problem of XSAT. Given a conjunctive normal function, this problem asks whether there exists a satisfying assignment for the input formula such that exactly two literals in each clause
3、are true. The rigorous theoretical analysis of the algorithms for solving X2SAT problem is proposed in the literature. An algorithm X2SAT-N based on Davis-Putnam- Logemann-Loveland (DPLL) is first presented to solve the X2SAT problem. In the algorithm X2SAT- N a simplification process is first calle
4、d to simplify the input formula. After that t several strategies are used to cut the branches on different kinds of clauses. It can be proved that the worstcase upper bound of algorithm X2SAT-N for solving X2SAT should be 0( 1. 4203), which improves the previous fastest X2SAT algorithm of 0( 1. 451
5、ln) up to now. Here n denotes the number of variables in a formula. Additionally9 an algorithm called as X2SAT-L for solving X2SAT problem is also presented.I his algorithm is also based on DPLL and using similar simplification process. We prove that the worst-case upper bound of this algorithm is 0
6、(1. 364 3), where I is the length of the formula. Within our knowledge, this algorithm is the best algorithm for X2SAT with the parameter of the length of the formula.Key words worst case； upper bounds； X2SAT; complexity analysis； branching tree摘 要 最坏情况下XSAT问题上界的研究已成为一个热门的研究领域针对XSAT的泛化问題XzSAT 提出了算法X
7、2SAT-N,该算法首先利用简化算法Simplify对公式进行化简然后通过分支树的方法对 不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的0(1.451 D 提高到0(1.4203)其中n为X.SAT公式中变童的数目.XgSAT问题实例的大小不仅依赖于变量的 数目还依赖于公式的长度，时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算 法X2SAT-L,并从公式长度的角度证明了 X2SAT问题在O (1. 364 3)时间上界内可解.关键词 最坏情况；上界；X2SAT；复杂性分析；分支树中图法分类号TP3O1.5收稿日期：2012-07- 16$修回日期：2012-09-27基金项目：国家门然科学感金项目(60803102.61070084.11226275吉林省自然科学墙金项目(201215006卄中央岛校基本科研业务费专项 资金项目(11QNJJ006.11CXPY010)価等学校博士学科点专项科研基金项目(20120043120017)通信作者：股明浩(ymhnc?nu edu. cn)
