Message passing for quantified Boolean formulas
This work addresses the problem of efficient QBF solving for AI and verification applications, offering incremental improvements through novel heuristics.
The paper tackles solving quantified Boolean formulas (QBF) by introducing message passing algorithms, including heuristics for proving unsatisfiability and guiding branching in DPLL solvers, resulting in exponential efficiency gains on random QBFs and solving previously unsolved benchmarks.
We introduce two types of message passing algorithms for quantified Boolean formulas (QBF). The first type is a message passing based heuristics that can prove unsatisfiability of the QBF by assigning the universal variables in such a way that the remaining formula is unsatisfiable. In the second type, we use message passing to guide branching heuristics of a Davis-Putnam Logemann-Loveland (DPLL) complete solver. Numerical experiments show that on random QBFs our branching heuristics gives robust exponential efficiency gain with respect to the state-of-art solvers. We also manage to solve some previously unsolved benchmarks from the QBFLIB library. Apart from this our study sheds light on using message passing in small systems and as subroutines in complete solvers.