CS Paper Radar

Solving QBF by Clause Selection

Mikoláš Janota, Joao Marques-Silva

cs.LO ·submitted 2026-08-14 12:56 UTC · v1
top venuehighly cited

Abstract

Algorithms based on the enumeration of implicit hitting sets find a growing number of applications, which include maximum satisfiability and model based diagnosis, among others. This paper exploits enumeration of implicit hitting sets in the context of Quantified Boolean Formulas (QBF). The paper starts by developing a simple algorithm for QBF with two levels of quantification, which is shown to relate with existing work on enumeration of implicit hitting sets, but also with recent work on QBF based on abstraction refinement. The paper then extends these ideas and develops a novel QBF algorithm, which generalizes the concept of enumeration of implicit hitting sets. Experimental results, obtained on representative problem instances, show that the novel algorithm is competitive with, and often outperforms, the state of the art in QBF solving.

Closest papers

Nearest neighbours by meaning across the whole index.

Solving QBF with Counterexample Guided Refinement

cs.LO ·2026-08-14 ·Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke
top venuehighly cited similarity 0.69
Abstract

We propose two novel approaches for using Counterexample-Guided Abstraction Refinement (CEGAR) in Quantified Boolean Formula (QBF) solvers. The first approach develops a recursive algorithm whose search is driven by CEGAR (rather than by DPLL). The second approach employs CEGAR as an additional learning technique in an existing DPLL-based QBF solver. Experimental evaluation of the implemented prototypes shows that the CEGAR-driven solver outperforms existing solvers on a number of families in the QBF-LIB and that the DPLL solver benefits from the additional type of learning. Thus this article opens two promising avenues in QBF: CEGAR-driven solvers as an alternative to existing approaches and a novel type of learning in DPLL.

0.69

The QBF Gallery 2026

cs.LO ·2026-11-13 ·Cynthia Peyrer, Luca Pulina, Martina Seidl
benchmark similarity 0.66
Abstract · Open access version

The QBF Gallery 2026 is the latest evaluation event of (dependency) quantified Boolean formula (QBF) solving technology. Its goal is to assess the current state-of-the-art, enable the evaluation of novel solvers on newly curated benchmark instances and present the progress made since the previous competition. This report discusses the solvers, instances and tools submitted by the community and introduces new benchmark collections for evaluation. We evaluate solvers in three tracks, reflecting most common input formats in (dependency) QBF solving. In addition to those main evaluations, we investigate effects of preprocessing and include a track of new crafted benchmark families. The results are analyzed using various metrics and complementary statistics on solver similarities, different memory limitations and performance across formula families. Finally, the dedicated benchmarks for each track are made available as an artifact to support future research and reproducible evaluation.

0.46

On Knowledge Compilation Languages for QBFs

cs.CC ·2026-10-14 ·Sravanthi Chede, Vaibhav Krishan, Anil Shukla
published similarity 0.65
Abstract · To be published in FSTTCS-2026

In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increasing order of their power of representation, starting from a simple tree-based structure, and extending it to DAGs for a more efficient representation. We study the power and limitations of each language. We also show that QBF queries such as model counting and MaxQBF are easy to handle in all these languages. These languages naturally lead to various static proof systems for the #QBF problem, the model-counting version of the QBF problem. We compare these systems with one another and with a recently introduced line-based #QBF-system called Q-MICE (Chede, Chew, Krishan and Shukla, SAT `26). We show that a minor extension of the Q-MICE system efficiently simulates all these static proof systems, and is in fact exponentially stronger than each of them. We also initiate the implementation of a solver based on these languages. The solver compiles a representation of an input QBF in the proposed tree-like language, which is subsequently used for model counting. This is the first knowledge compilation based solver for #QBF which can handle QBFs with doubly exponential model counts as well. Experimentally, we compare its performance with the state-of-the-art #QBF-solver d4-QBF which works well for QBFs with small model counts.

0.26

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.63
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

On Structure-Aware SAT Solving

cs.LO ·2026-11-13 ·Eugene Goldberg
hot direction similarity 0.63
Abstract

Although modern SAT solvers have made remarkable progress, they still exploit formula structure only to a limited extent. We present two techniques that make SAT solving more structure-aware and provide experimental results showing their promise. The first technique ``$\mathit{melts}$'' the formula by reducing interaction between its parts. This is achieved by adding new variables, using existential quantifiers, and applying a procedure called partial quantifier elimination. The second technique exploits the notion of a $\mathit{local}$ $\mathit{proof}$. The latter establishes that a formula is unsatisfiable by proving that certain literals of its clauses are redundant. We show that using local proofs makes SAT solving more formula-specific.

0.44

Towards Understanding the Complexity of CAQE: A Proof-Theoretic Analysis of its Core Procedure

cs.LO cs.CC ·2026-11-14 ·Benjamin Böhm, Olaf Beyersdorff
top venuetheory similarity 0.60
Abstract

CAQE (Clausal Abstraction for Quantifier Elimination) is currently the most successful algorithmic paradigm for solving Quantified Boolean Formulas (QBF) in practice, clearly dominating recent QBF competitions. While apparently being a very strong solver, not much is known about CAQE in theory. We propose a framework for formalising runs of the basic CAQE algorithm (where failed assumptions are not considered) as proofs in a proof system CAQE$^{\mathsf{Core}}$, which we use to analyse the algorithm proof-theoretically and which provides methods for future work to separate it from optimised versions of CAQE that are used in practice. We show that one can perform strategy extraction on the CAQE$^{\mathsf{Core}}$ proof system in such a way that strategy size serves as a lower bound for basic CAQE runs. Furthermore, we introduce a measure, which we call CAQE width, which not only acts as a lower bound on CAQE$^{\mathsf{Core}}$ proofs, but -- with the number of $\exists\forall$ alternations as exponent -- as an upper bound as well. Using this analysis, we prove that Q-resolution with an NP oracle simulates CAQE$^{\mathsf{Core}}$ on QCNFs of bounded quantifier alternation. The same holds for QCDCL (Quantified Conflict-Driven Clause Learning, formalised as a proof system) on $Σ_3^b$ QCNFs when purely propositional CDCL steps are not counted, after a simple preprocessing step. In this setting, both systems are indeed strictly stronger than CAQE$^{\mathsf{Core}}$, where the separation of QCDCL from CAQE$^{\mathsf{Core}}$ uses cube learning.

0.64

A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression

cs.DM cs.DSmath.CO ·2026-11-10 ·Oscar Defrain, Corentin Jazeron, Kazuhisa Makino
hot direction similarity 0.57
Abstract · 6 pages

We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.

0.34

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving

cs.LO ·2026-09-28 ·Gábor Kusper
publishedtheory similarity 0.56
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

A resolvable network is a directed-graph representation of SAT: every SAT instance can be translated into an RN, and every RN has an associated CNF formula. Each reach represents one clause. In a mixed reach, the head and tail are disjoint sets of variables containing the variables occurring negatively and positively in the clause, respectively; the distinguished symbols Source and Sink represent a missing negative- or positive-literal side. RN-Solver is a proof-of-concept SAT solver based on this representation. Its all-positive clauses are represented by white reaches, and its token distributions are the inclusion-minimal hitting sets of the current white tails, generated by monotone CNF-DNF dualization. RN-Solver learns new white reaches by private-pivot resolution, a structured resolution sequence that uses old white reaches as pivot witnesses. In the original algorithm, every candidate white reach generated by such a chain was followed by a global subsumption test against the current network. Profiling showed that this subsumption test can dominate the runtime on random 3-SAT instances. We show that this check is unnecessary when the mixed reach used for learning is falsified by the current token distribution, meaning that the distribution makes all variables in the head true and all variables in the tail false. The key invariant is simple: the resulting white tail is disjoint from the triggering token distribution, while the same distribution intersects every old white tail. Hence no old white reach can subsume the generated reach. This structural observation allows us to construct a simpler, snapshot-based, subsumption-free variant of RN-Solver, where each main-loop iteration uses a fixed set of old reaches and installs newly generated white reaches only at the end of the iteration. We prove soundness of the revised algorithm. Empirical evaluation confirms the elimination of the targeted checks: within an 8 second budget, snapshot/full-DNF solves 963 of 1,000 uf20-91 instances, compared with 724 for the original control flow. A separate 100-instance comparison identifies exact incremental DNF as the most effective of the three tested configurations.

0.36