计算机科学与探索2012，Vol.6Issue(7)：664-671,8.DOI:10.3778/j.issn.1673-9418.2012.07.010
最坏情况下X3SAT最大海明距离问题最小上界
Worst Case Upper Bound for the Maximum Hamming Distance X3SAT Problem
摘要
Abstract
The maximum Hamming distance X-3-satisfiability (X3SAT) problem looks for the maximum Hamming distance between any two x-models of the formula F in 3-conjunctive normal form (3-CNF). This paper presents an exact algorithm HMX based on Davis-Putnam-Logemann-Loveland (DPLL) for the maximum Hamming distance X3SAT problem. The algorithm branches on some variable according to its different values in two truth assignments of the formula. Before the branching some reduction rules are used to simplify the formula. The reduction rules increase the efficiency of the algorithm. The worst case upper bound for the problem is 0(1.676 0n), which improves the previous result 0(1.710 7n), where n is the number of the variables in the formula.关键词
海明距离/可满足性(SAT)/X3SAT/DPLL/最坏情况/复杂性分析/上界Key words
Hamming distance/ satisfiability(SAT)/ X3SAT/ DPLL/ worst case/ complexity analysis/ upper bound分类
信息技术与安全科学引用本文复制引用
傅琳璐,周俊萍,殷明浩..最坏情况下X3SAT最大海明距离问题最小上界[J].计算机科学与探索,2012,6(7):664-671,8.基金项目
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(浙江师范大学计算机软件与理论省级重中之重学科开放基金). （浙江师范大学计算机软件与理论省级重中之重学科开放基金）
