Egly, U., Lonsing, F., & Widl, M. (2013). Long-Distance Resolution: Proof Generation and Strategy Extraction in Search-Based QBF Solving. In K. McMillan, A. Middeldorp, & A. Voronkov (Eds.), Logic for Programming, Artificial Intelligence, and Reasoning (pp. 291–308). Springer. https://doi.org/10.1007/978-3-642-45221-5_21
International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR)
14-Mar-2005 - 18-Mar-2005
Montevideo, Uruguay, Austria
Number of Pages:
Springer, LNCS / 7180 / Heidelberg
QBF; QBF solving; strategy extraction
Strategies (and certificates) for quantified Boolean formulas (QBFs) are of high practical relevance as they facilitate the verification of results returned by QBF
solvers and the generation of solutions to problems formulated as QBFs. State of the art approaches to obtain strategies require traversing a Q-resolution proof of a QBF, which for many real-life instances is too large to handle. In this work, we consider the long-distance Q-resolution (LDQ) calculus, which allows particular tautological resolvents. We show that for a family of QBFs using LDQ allows for
exponentially shorter proofs compared to Q-resolution. We further show that an approach to strategy extraction originally presented for Q-resolution proofs can also be applied to LDQ-resolution proofs. As a practical application, we consider search-based QBF solvers which are able to learn tautological clauses based on resolution and the conflict-driven clause learning method. We prove that the resolution proofs produced by these solvers correspond to proofs in the LDQ calculus and can therefore be used as input for strategy extraction algorithms.
Experimental results illustrate the potential of the LDQ calculus in
search-based QBF solving.
FAME: Formalizing and Managing Evolution in Model-Driven Engineering (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds) Quantified Boolean Formulas: S 11409-N23 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))