Abstract
Abstract Branching (AB) is a novel search-based procedure for solving Quantified Boolean Formulas (QBF) that mitigates the exponential overhead of branching on universal variables. By prioritizing existential variables and employing Binary Decision Diagrams (BDDs) to manage "universal scenarios," AB offers a robust alternative to traditional DPLL-style solvers. Evaluation on QBFLIB benchmarks shows that AB is particularly effective for game-based problems, outperforming existing state-of-the-art solvers.
Introduction
Quantified Boolean Formulas (QBF) extend standard SAT problems with universal ($\forall$) and existential ($\exists$) quantifiers, making them suitable for modeling complex domains like formal verification and two-player games. However, QBF solving is PSPACE-complete. Traditional DPLL-style solvers often struggle with the "universal bottleneck": for every universal variable, the solver must explore both truth assignments, leading to an exponential explosion in the search tree. While inference-based solvers (using resolution or Skolemization) exist, they frequently encounter memory limitations. Abstract Branching seeks a middle ground by combining search with efficient scenario tracking.
Methodology: Abstract Branching
The core innovation of Abstract Branching (AB) is the reversal of the traditional search perspective. Instead of alternating branches between universal and existential variables, AB focuses on existential assignments.
- Existential-First Search: The solver initially guesses assignments for existential variables.
- Scenario Neutralization: For a given existential assignment, the solver identifies which "universal scenarios" (combinations of universal assignments) are satisfied. These are marked as "neutralized."
- Space Coverage: The search continues until the entire space of universal scenarios is covered (TRUE) or existential options are exhausted (FALSE).
- BDD Integration: To handle the potentially astronomical number of scenarios, AB uses Reduced Ordered Binary Decision Diagrams (ROBDDs). BDDs allow for compact representation and efficient set operations like union and projection.
- Abstract Unit Propagation: The method extends standard unit propagation to "Abstract Unit Clause Propagation" (AUCP), pruning the search space by identifying existential assignments forced by active universal scenarios.
Experimental Evaluation
The algorithm was evaluated using 192 instances from the QBFLIB benchmarks, focusing on $\forall\exists$ structures. The dataset included families such as mutex, shifter, robots, tree-exa, and game. AB was compared against established solvers including QuBE, sKizzo, semprop, yquaffle, and Quantor.
Results and Discussion
AB demonstrated superior performance, solving 91.7% of the test set within a 1000-second timeout, compared to 87.0% for QuBE. A standout result was observed in the "game" family; AB solved instances like game20 and game50 in fractions of a second (0.01s - 0.03s), whereas other solvers often timed out.
Key insights from the results include:
- Monotonicity: The set of neutralized scenarios grows monotonically, ensuring a systematic search.
- Complementarity: AB excels on instances that are difficult for standard DPLL solvers, suggesting it explores the search space in a fundamentally different way.
- Efficiency: By using BDDs, AB manages the memory intensity of inference methods while retaining the search-based advantage of polynomial-space guarantees (under controlled BDD sizes).
Conclusion
Abstract Branching offers a powerful new approach to QBF solving by abstracting away universal branching. While currently focused on $\forall\exists$ formulas and constrained by prefix ordering, its success on game-based benchmarks highlights its potential. Future work will focus on generalizing the method to deeper quantifier alternations and improving BDD scaling during deep searches.
Summary updated