计算机科学 ›› 2010, Vol. 37 ›› Issue (3): 11-16.

• 综述 • 上一篇    下一篇

隐蔽集的研究及发展

谷文祥,李淑霞,殷明浩   

  1. (东北师范大学计算机学院 长春130117)
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金(60473042,60573067和60803102)资助

Research and Development in Backdoor Set

GU Wen-xiang,LI Shu-xia,YIN Ming-hao   

  • Online:2018-12-01 Published:2018-12-01

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

关键词: SAT问题,QBF问题,隐藏结构,隐蔽集

Abstract: 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.

Key words: Propositional satisfiability problem, Quantified boolcan formulae, Hidden structure, Backdoor set

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!