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 O(1.676 0n), which improves the previous result O(1.710 7n), where n is the number of the variables in the formula.

Key words: Hamming distance, satisfiability(SAT), X3SAT, DPLL, worst case, complexity analysis, upper bound

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

关键词: 海明距离, 可满足性（SAT）, X3SAT, DPLL, 最坏情况, 复杂性分析, 上界