• 学术研究 •

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

1. 东北师范大学 计算机科学与信息技术学院，长春 130117
• 出版日期:2012-07-01 发布日期:2012-07-02

### Worst Case Upper Bound for the Maximum Hamming Distance X3SAT Problem

FU Linlu, ZHOU Junping, YIN Minghao

1. School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
• Online:2012-07-01 Published:2012-07-02

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.