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

摘要：

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

关键词：SAT问题、完备算法、不完备算法、组合算法

所属期刊栏目：43

分类号：TP301(计算技术、计算机技术)

资助基金：宁夏回族自治区自然科学基金资助项目NZ13265

在线出版日期：2016-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：8-17