隐蔽集的研究及发展

• 作者: 李淑霞 殷明浩 谷文祥
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: SAT问题 QBF问题 隐藏结构 隐蔽集
• 年，卷（期）: 2010,（3）
• 页码范围: 11-16
• 页数: 6页
• 分类号: TP18
• 字数: 8627字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2010.03.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谷文祥	东北师范大学计算机学院	71	538	11.0	20.0
2	殷明浩	东北师范大学计算机学院	35	304	10.0	16.0
3	李淑霞	东北师范大学计算机学院	3	16	3.0	3.0