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