隐蔽集的研究及发展

摘要：

SAT问题的隐藏结构与问题难度有很大的关系,近年来成为人工智能的一个研究热点.隐蔽集(Backdoor)作为典型的隐藏结构之一,能使剩下的问题在多项式时间内求解.在深入研究隐蔽集的基础上,首先对隐蔽集的发展、相关概念、参数复杂性及隐蔽集与骨架(Backbone)之间的关系作了全面的论述;接着分别从CSP问题、SAT问题和QBF问题3个方面具体介绍了目前比较流行的隐蔽集求解方法;最后给出了3个未解决的问题,并对隐蔽集的发展趋势进行了展望.

关键词：SAT问题、QBF问题、隐藏结构、隐蔽集

所属期刊栏目：37

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60473042,60573067和60803102

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

页数：共6页

页码：11-16