💻 computer science

Solving QBF by Clause Selection

This paper introduces a novel QBF solving algorithm based on the generalization of implicit hitting set enumeration, demonstrating through experiments that it is competitive with and often outperforms state-of-the-art solvers.

Original authors: Mikoláš Janota, Joao Marques-Silva

Published 2026-08-17

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Mikoláš Janota, Joao Marques-Silva

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, cosmic game of "Yes or No" played with a deck of cards where some cards are controlled by a mischievous opponent and others by a clever hero. This is the world of Quantified Boolean Formulas (QBF), a branch of computer science that sits just beyond the famous "SAT" puzzles. While a standard SAT puzzle asks, "Can we flip these switches to make the whole machine light up?", a QBF adds a layer of drama: "Can the hero always win, no matter how the opponent tries to sabotage the switches?" This isn't just a brain teaser; it's the mathematical engine behind checking if self-driving cars will crash, if robots can plan complex missions, or if two-player games have a guaranteed winning strategy. Because these problems are so hard, solving them is like trying to find a needle in a haystack that keeps changing shape.

Enter a new team of researchers who decided to tackle this chaos not by building a bigger, more complex machine, but by playing a clever game of "clause selection." Think of the puzzle as a massive list of rules (clauses). The researchers realized that instead of trying to solve the whole thing at once, they could use a standard, off-the-shelf "Yes/No" solver (a SAT solver) as a referee to help them pick and choose which rules to keep or discard at each step of the game. Their new method, called QESTO, treats the problem like a strategic battle where the goal is to find a set of rules that the hero can satisfy no matter what the opponent does.

The paper introduces QESTO, a novel algorithm designed to solve these complex logic puzzles. The authors first broke the problem down into a simple two-player version (one opponent, one hero) and showed that their method is mathematically linked to a concept called "implicit hitting sets"—a fancy way of saying they are finding the smallest group of rules that, if broken, would cause the whole system to fail. They then expanded this idea to handle puzzles with any number of players and layers of "what if" scenarios.

In their experiments, the team built a prototype of QESTO and tested it against the best existing solvers on a set of standard benchmarks. The results suggest that QESTO is highly competitive. On a specific set of two-player puzzles, their prototype actually solved the most instances, outperforming other top-tier tools. On a broader, more complex set of benchmarks, it came in second place, just behind a solver that doesn't use the standard "rule list" format. The authors suggest that this approach is particularly strong because it relies on a "black box" SAT solver, meaning if someone invents a better SAT solver tomorrow, QESTO automatically gets better without needing to be rewritten. While the paper doesn't claim to have solved every QBF problem in existence, the simulations indicate that this new way of selecting and deselecting rules is a robust and promising direction for the future of automated reasoning.

Technical Summary: Solving QBF by Clause Selection

Problem Statement
The paper addresses the problem of solving Quantified Boolean Formulas (QBFs), specifically those in Prenex Conjunctive Normal Form (PQCNF). Deciding the validity of QBFs is a PSPACE-complete problem, covering applications such as model checking, planning, and two-player games. While SAT solving has seen significant success, QBF solving remains challenging. Existing approaches generally fall into two categories: conflict/solution-driven learning (extending SAT clause learning) and expansion-based methods (converting QBFs into SAT problems). The authors propose a novel approach that leverages the duality of hitting sets and implicit hitting set enumeration to solve QBFs.

Methodology
The core methodology, named QESTO (Qbf clausE SelecTion sOlver), treats QBF solving as a game between a universal player and an existential player. The algorithm operates by iteratively selecting and deselecting clauses at different quantification levels using a SAT solver as an oracle.

Two-Level QBF ( $\forall \exists$ ):
The authors first develop an algorithm for formulas with two quantification levels. They establish a link between solving $\forall X \exists Y. \phi$ and the enumeration of implicit hitting sets.
- Mechanism: The algorithm maintains a set of selection variables $s_C$ for each clause $C$ . A SAT solver is used to find a set of clauses $S$ that can be "selected" (i.e., their universal literals can be set to false).
- Verification: If the existential part of the selected clauses is unsatisfiable, the universal player wins (the formula is false). If satisfiable, the algorithm learns from the satisfying assignment to block future selections of subsets of clauses that were satisfied, effectively searching for a Minimal Unsatisfiable Set (MUS) of the existential part constrained by universal rules.
- Relation to Theory: This process is shown to be an application of the duality hitting set principle, where the algorithm traverses Maximally Satisfiable Sets (MSSes) to find MUSes.
General QBF (Arbitrary Prefixes):
The approach is generalized to arbitrary quantifier prefixes ( $Q_1 X_1 \dots Q_n X_n. \phi$ ).
- Game-Theoretic View: The algorithm simulates a game with $n$ $n$ rounds. At each level $i$ $i$ , the player $Q_i$ $Q_{i}$ selects or deselects clauses based on specific rules:
  - A clause can be selected at level $k$ only if it was selected in all previous levels and all its literals at level $k$ are set to false.
  - A clause can be deselected if it was deselected previously or if a literal at level $k$ is set to true.
- Clause Selection Logic: The algorithm maintains conditions $C_i$ for each level that block choices leading to a loss for the current player.
- Conflict Analysis: When a condition becomes unsatisfiable (indicating a player has lost), the algorithm performs a "loss analysis" using the final conflict clause from the SAT solver.
  - Existential Loss: If the existential player loses, the algorithm identifies a set of selected clauses causing unsatisfiability and backtracks to the highest quantification level of an existential literal within those clauses to force a deselection.
  - Universal Loss: If the universal player loses (all clauses deselected), the algorithm backtracks to the highest level where a universal player could have prevented the deselection.
- Learning: The algorithm learns new constraints (clauses) to prevent the same losing configuration from recurring, similar to conflict-driven learning in SAT but anchored in the selection variables.

Key Contributions

Novel Algorithm (QESTO): The paper introduces QESTO, a QBF solver that uses a SAT solver as a black-box oracle to select or deselect clauses at each quantification level.
Theoretical Link to Hitting Sets: It establishes a formal connection between QBF solving and the enumeration of implicit hitting sets, generalizing the duality hitting set principle (typically used for MUS computation and MaxSAT) to the PSPACE domain.
Connection to CEGAR: The two-level variant is linked to Counter-Example Guided Abstraction Refinement (CEGAR) approaches, specifically AReQS, though the generalization (QESTO) differs significantly from recursive generalizations like RAReQS by avoiding the introduction of fresh variables and maintaining a fixed number of solvers.
Engineering Advantage: The approach relies entirely on existing SAT solvers. If a better SAT solver is developed, it can be directly substituted into the implementation without modifying the QBF logic.

Experimental Results
The authors implemented a prototype in C++ using MiniSat 2.2 and evaluated it on the QBFLIB benchmark suite (2014) and the 2QBF track (2010).

2QBF Benchmarks: QESTO solved the highest number of instances (53 out of 65), outperforming DepQBF (30) and GhostQ (43). It was very close to AReQS (52), which is expected given their theoretical relationship.
QBFLIB Benchmarks: GhostQ (a non-CNF solver) dominated the results (137 instances), followed by QESTO (133). DepQBF and RAReQS solved 128 and 129 instances respectively.
Observation: The results suggest that while QESTO is competitive and robust, representing QBF problems strictly in CNF may be a limitation compared to non-CNF approaches like GhostQ.

Significance and Claims
The paper claims that QESTO represents a novel approach to QBF solving that is both theoretically significant and practically competitive.

Theoretical: It extends the duality hitting set principle from NP (MUS/MSS) to PSPACE (QBF), providing a new perspective on the problem structure.
Practical: The algorithm is "competitive with, and often outperforms, the state of the art" in specific domains (particularly 2QBF).
Modesty: The authors acknowledge that their CNF-based approach was outperformed by the non-CNF solver GhostQ on the general QBFLIB suite. They explicitly state that future work should investigate applying QESTO to non-CNF formulas and incorporating optimizations like pure literals or variable dependencies. They do not claim QESTO is the absolute state-of-the-art for all QBF instances but rather a robust and novel alternative that bridges different solving paradigms.

Technical Summary: Solving QBF by Clause Selection

More like this