求解SAT问题的算法的研究进展

• 作者: 张斌 张长胜 郭莹
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: SAT问题 完备算法 不完备算法 组合算法
• 年，卷（期）: 2016,（3）
• 页码范围: 8-17
• 页数: 10页
• 分类号: TP301
• 字数: 11144字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2016.3.002

摘要

SAT问题是研究最广泛的NPC问题之一.由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法.因此设计出高效快速的SAT求解算法至今仍是研究热点.首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张斌	东北大学信息科学与工程学院	203	1801	20.0	33.0
2	郭莹	东北大学信息科学与工程学院	8	60	4.0	7.0
6	张长胜	东北大学信息科学与工程学院	23	161	6.0	12.0