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

• 作者: 傅琳璐 周俊萍 殷明浩
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 海明距离 可满足性(SAT) X3SAT DPLL 最坏情况 复杂性分析 上界
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 学术研究
• 页码范围: 664-671
• 分类号: TP301.5
• 字数: 7210字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2012.07.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周俊萍	东北师范大学计算机科学与信息技术学院	10	82	4.0	9.0
2	殷明浩	东北师范大学计算机科学与信息技术学院	35	304	10.0	16.0
3	傅琳璐	东北师范大学计算机科学与信息技术学院	2	0	0.0	0.0