隐蔽集的研究及发展

Research and Development in Backdoor Set

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

There is a great relationship between hidden structure of Propositional Satisfiability problem and problem hardness,which becomes a focus of study in recent years. Backdoor is one of these hidden structures,which makes the remaining questions can be solved in polynomial time. Through the study of this backdoor questions, firstly this paper made more comprehensive introduction about the developing of backdoor problem, related concepts of backdoor problem, parametric complexity of backdoor problem and relationship between backbone and backdoor. Then introduced more specific solution of backdoor set from these aspects, such as Constraint Satisfaction Problem （CSP） , Propositional Satisfiability Problem and Quantified Boolcan Formulae （QBF）. At the same time, summarized some unresolved queslions and prospects of the backdoor sets.