O(m2)时间求解SAT问题的随机算法

• 作者: 徐云 许胤龙 陈国良 顾钧
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: SAT问题 随机算法 数学期望 不满足解数
• 年，卷（期）: 2001,（11）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1136-1141
• 页数: 6页
• 分类号: TP301
• 字数: 4546字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2001.11.002

摘要

传统的求解SAT问题的随机算法主要是对满足解进行搜索,在找不到满足解的情况下,则无法正确判断问题的可满足性.该文提出了两个时间复杂度为O(m2)求解SAT问题的随机算法SatTest1和SatTest2,这里m为CNF公式中的子句数.这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性,不同于传统的随机算法.其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计,是对传统随机算法的重要改进.试验结果表明,文中提出的算法对相变区域的难SAT实例有较好的求解能力.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与技术系	123	2142	20.0	43.0
2	徐云	中国科学技术大学计算机科学与技术系	79	411	13.0	16.0
3	许胤龙	中国科学技术大学计算机科学与技术系	37	259	8.0	14.0
4	顾钧	中国科学技术大学计算机科学与技术系	19	289	7.0	17.0