Solving #QBF Using Extension Rule
Jun Ping Zhou, Chun Guang Zhou, Yan Dong Zhai, Yong Yang · Applied Mechanics and Materials · 2010
Extension rule is a new method for computing the number of models for SAT formulae. In this paper, we investigate the use of the extension rule in solving #QBF, i.e., computing the number of Q1x1…Qn xn which makes the Quantified Boolean Formulas (QBF) Q1x1…Qn xnF evaluate to true. We present a #QBF algorithm based on the extension rule, namely QBFMC, which also integrates the unit propagation and the component analysis together. These excellent technologies improve the efficiency of solving #QBF problems efficiently.