基于分支回溯的NAE-3SAT问题求解算法
2012-11-26谷文祥傅琳璐周俊萍姜蕴晖
谷文祥,傅琳璐,周俊萍,姜蕴晖
(1.东北师范大学计算机科学与信息技术学院,吉林长春130117;2.长春建筑学院基础教学部,吉林长春130607)
可满足性问题(satisfiability,SAT)作为计算机理论与应用的核心问题,在智能规划、机器视觉、逻辑推理机以及电子设计自动化等领域中有着重要的理论研究与实际应用价值[1-4].SAT问题的计算复杂性是NP完全的[5],这意味着如果P≠NP成立,则无法在多项式时间内解决SAT问题.这时从理论上分析该问题在最坏情况下的时间复杂性上界尤为重要,因为此时对该问题上界的一个微小的改进,例如从O(ck)改进为O((c-ε)k)就会使得问题求解的算法在效率上获得指数级别的提高.多年来,研究人员不断改进SAT问题及其约束子问题的求解算法在最坏情况下的时间复杂度上界[6-11].以3SAT问题为例,最初Monien和Speckenmeyer在文献[6]中给出了求解3SAT问题的上界为O(2m/3),其中m是命题公式中的子句数目,目前获得的最好上界为O(1.234m)[8].SAT 问题理论上的不断发展使得其系统的求解能力有了很大的提高.目前Zchaff、Survey Propagation等SAT求解系统已可以求解包含100 000个以上变量的SAT问题实例[12-14].
NAESAT(not-all-equal satisfiability)问题作为SAT问题的一个重要扩展,判断是否存在一组真值赋值使得给定的命题公式为可满足,并且使公式的每个子句中所有文字的取值不全为真.NAESAT和NAE-k-SAT(即公式中所有子句的长度都小于等于k,k≥3)都是 NP 完全问题[15-17],其在集合分裂、最大割集等问题中都有着重要的应用[16].近来,从理论上研究NAESAT问题及其约束子问题在最坏情况下的时间复杂度上界受到了广……
