基于分支回溯的NAE-3SAT问题求解算法

摘要：

NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.

关键词：NAESAT、NAE-3SAT、时间复杂性、NAE-3SAT问题上界、变量数目、分支回溯

所属期刊栏目：7

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

资助基金：国家自然科学基金资助项目61070084,60803102;中央高校基本科研业务费专项资金资助项目11QNJJ006;浙江师范大学计算机软件与理论省级重中之重学科开放基金资助项目ZSDZZZZXK37

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

页数：共6页

页码：506-511