最坏情况下X3SAT最大海明距离问题最小上界

摘要：

X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离.提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支.给出了多种化简规则,这些规则很好地提高了算法的时间效率.证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.710 7n)缩小到O(1.676 0n),其中n为公式中变量的数目.

关键词：海明距离、可满足性(SAT)、X3SAT、DPLL、最坏情况、复杂性分析、上界

所属期刊栏目：6

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

资助基金：The National Natural Science Foundation of China under Grant Nos.61070084,60803102;the Fundamental Research Funds for the Central Universities of China under Grant No.11QNJJ006;the Opening Fund of Top Key Discipline of Computer Software and Theory in Zhejiang Provincial Colleges at Zhejiang Normal University under Grant No.ZSDZZZZXK37

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

页数：共8页

页码：664-671