Research and Development in Backdoor Set
Minghao Yin · 2010
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 Boolean Formulae (QBF).At the same time,summarized some unresolved questions and prospects of the backdoor sets.