Abstract
This paper introduces d4-QBF, the first model counter capable of handling Quantified Boolean Formulas (QBF) with arbitrary quantifier prefixes. By treating solutions as "tree models" and employing sophisticated caching and decomposition techniques, the authors significantly outperform existing methods and solve complex problems that were previously out of reach.
The Challenge of #QBF
In Boolean logic, Satisfiability (SAT) asks if an assignment exists, while model counting (#SAT) asks how many exist. Quantified Boolean Formulas (QBF) introduce universal ($\forall$) and existential ($\exists$) quantifiers, making the problem significantly harder. A solution to a QBF is not a single assignment but a tree model—a strategy that ensures the formula remains true regardless of the universal player's moves.
While #SAT is well-studied, #QBF (counting these tree models) has remained largely theoretical or limited to simple formulas with only two layers of quantifiers. The challenge lies in the massive search space and the structural dependencies created by the quantifier order.
The d4-QBF Approach
The authors present d4-QBF, a top-down compiler based on the successful D4 #SAT solver architecture. Its key innovations include:
- Quantifier-Aware Branching: Respecting the quantifier prefix order by branching on outermost variables first to maintain tree model integrity.
- Component Decomposition: Identifying independent parts of the formula. If a formula can be split, the total count is the product (for universal) or sum (for existential) of the counts of its parts.
- Canonical Prefix Caching: Using a
Shrinkfunction to normalize quantifier prefixes, allowing the solver to recognize and reuse results for sub-problems even if they appear in different contexts. - Hybrid Aggregation: Combining results using multiplication for $\forall$ variables and addition for $\exists$ variables.
Key Results
The evaluation on 2QBF and deeply nested "Crafted" benchmarks demonstrates d4-QBF's efficiency. It solved nearly all 2QBF instances and handled formulas with up to 25 quantifier blocks—tasks that existing counters simply could not perform.
As shown in the runtime comparison, d4-QBF consistently outperforms both the enumerative qcounter and baseline solvers, often by orders of magnitude. On 2QBF benchmarks, it solved all but 10 of 2,586 instances, demonstrating superior speed and robust handling of increasing complexity.
Conclusion
d4-QBF represents a major step forward in QBF reasoning. By extending top-down compilation techniques with quantifier-aware optimizations, it enables the counting of complex tree models in domains like formal verification and synthesis. Future work will explore improved propagation logic and more compact model representations to handle even larger problem instances.
Summary updated