Solving QBF by Clause Selection

Mikolás Janota, João Marques-SilvaIJCAI 2015

Abstract

This paper introduces QESTO (Qbf clausE SelecTion sOlver), a novel algorithm for solving Quantified Boolean Formulas (QBF). By treating SAT solvers as modular "black-box" oracles and framing the problem as one of clause selection, QESTO achieves high performance and architectural flexibility. The approach leverages the "duality hitting set principle" to bridge the gap between QBF solving and error diagnosis. Experimental results show that QESTO is highly competitive with state-of-the-art tools, particularly dominating in formulas with two levels of quantification (2QBF).

Introduction: The Challenge of QBF

In computational logic, while SAT (Satisfiability) is NP-complete, many real-world AI applications—such as formal verification, planning, and game theory—require the more expressive language of Quantified Boolean Formulas (QBF). QBF, which incorporates universal ($\forall$) and existential ($\exists$) quantifiers, is PSPACE-complete, making it significantly more complex to solve than standard SAT.

Existing QBF solvers often struggle with architectural rigidity, either attempting to directly extend SAT techniques like conflict-driven learning or expanding formulas into massive, unmanageable SAT problems. The authors address this by proposing QESTO, a solver designed to use any off-the-shelf SAT solver as a modular component, allowing it to immediately benefit from advancements in SAT technology.

Methodology: The QESTO Algorithm

QESTO's innovation lies in its treatment of QBF as a game of clause selection. The algorithm is built upon four key pillars:

  1. Clause Selection: Instead of assigning truth values to variables, the algorithm uses "selector variables" to determine which clauses are active at each quantification level. The Universal player ($\forall$) tries to select an unsatisfiable set of clauses, while the Existential player ($\exists$) tries to satisfy them.
  2. SAT Solvers as Oracles: QESTO instantiates separate SAT solvers for each quantification level. These solvers act as NP-oracles that inform the main algorithm whether a specific selection of clauses is feasible, without needing to understand the full QBF structure.
  3. Duality Hitting Set Principle: Borrowed from error diagnosis (finding Minimally Unsatisfiable Sets), this principle allows QESTO to generalize the search process across arbitrary quantification levels.
  4. Loss Analysis: When a player "loses" (the SAT solver returns unsatisfiable), the algorithm performs conflict analysis to learn new constraints, effectively pruning the search space and preventing future identical losses.

A key insight of this approach is monotonicity: once a clause is satisfied by a player's move, it remains satisfied for the duration of that round, simplifying progress tracking.

Experimental Results

The authors evaluated QESTO against state-of-the-art solvers (GhostQ, DepQBF, and RAReQS/AReQS) using two primary benchmark sets: the QBFLIB (2014 QBF Gallery) with 276 instances and the 2QBF Track with 65 instances.

Summary of solved instances across QBFLIB and 2QBF benchmarks.

Dominance in 2QBF

QESTO demonstrated superior performance on formulas with exactly two levels of quantification. It solved 53 out of 65 instances, outperforming its closest competitor, AReQS (52 instances).

Cactus plot comparing solver performance on 2QBF instances.

Competitive Performance on General QBF

On the broader QBFLIB suite, QESTO solved 133 instances, placing it second only to GhostQ (137). It outperformed established solvers such as DepQBF (128) and RAReQS (129), proving the robustness of the clause-selection approach across varied problem structures.

Discussion and Future Work

QESTO's modular design provides a significant engineering advantage, making it "future-proof" against changes in SAT solver technology. However, its reliance on Conjunctive Normal Form (CNF) can be a drawback, as the conversion process may destroy useful structural information—a factor that likely contributed to GhostQ's lead on certain benchmarks.

Future research will focus on adapting QESTO to work directly on non-CNF formulas (such as circuits) and incorporating more advanced variable dependency tracking to further enhance its efficiency.

Summary updated

BibTeX
@inproceedings{janota2015solving,
  author = {Mikolás Janota and João Marques-Silva},
  title = {{Solving QBF by Clause Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure