betaFeedback

WorksComputer Science

The QBF Gallery 2026

Abstract

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.

Introduction

Quantified Boolean formulas (QBFs) arise in numerous practical applications including synthesis, bounded model checking and planning [63]. The corresponding decision problem is widely regarded as the canonical PSPACE-complete problem [66]. To assess the state-of-the-art in QBF solving, regular events such as the QBFEval and the QBF Gallery have been organized. This tradition began in 2003 and had its latest entry 2023, with numerous editions in between [5, 6, 34, 37, 44, 47, 50, 53, 54]. This paper reports on the organization and results of the QBF Gallery 2026.

The event itself was conducted virtually with the evaluations performed on a local compute cluster. The results were presented at the Federated Logic Conference (FLoC) 2026, as part of the FLoC Olympics, affiliated with the International Conference on Theory and Applications of Satisfiability Testing [1]. In addition to solvers and preprocessors, participants were invited to submit novel problem instances to different tracks covering different QBF formalisms and input formats. The results are analyzed not only to determine a winner for each track but also to identify the practical challenges currently faced by the field. By including instances and solvers from previous competitions, we aim to show the progress made over the last iterations. This paper is structured as follows: First, we describe the organizational aspects of the Gallery including the experimental setup and the individual tracks. We then present the benchmarks and solvers newly submitted and further the selected participants of this Gallery. Finally, we evaluate the results on their different performance metrics and provide a deeper analysis of the collected data.

Organization

The QBF Gallery 2026 featured five tracks, each based on different types of formulas. This section describes the experimental setup including resource limits and evaluation procedure as well as the input formats and semantic details of of each track.

Setup

All experiments were conducted on an Ubuntu 24.04.4 LTS compute cluster consisting of 20 nodes, each equipped with 64 dual-socket 16-core AMD EPYC [email protected] GHz CPUs. All tracks were evaluated on this setup with one allocated node per instance. A timeout of 900 s and a memory limit of 8 GB was set for each instance in every track. Additionally, some selected tracks were re-ran with an increased memory limit of 128 GB to evaluate the extent to which solver performance is constrained by memory limitation.

Tracks of the QBF Gallery 2026

In the following we present the Prenex Conjunctive Normal Form (PCNF), Prenex Non-Conjunctive Normal Form (PNCNF), Dependency Quantified Boolean Formula (DQBF), Crafted Instances and Preprocessor track. Submissions of both formulas and solvers were accepted for the first four tracks. In contrast, the Preprocessor track only accepted preprocessors while using the benchmarks submitted to the PCNF (resp. Non-PCNF) track. Solvers and formulas were allowed to be featured in multiple tracks, provided they satisfy the respective track requirements.

PCNF Track

A QBF in Prenex Conjunctive Normalform (PCNF) has the structure ϕ=Π:Ψ\phi= \Pi: \Psi, where Π=Q1x1…Qmxm\Pi= Q_1x_1 \ldots Q_mx_m is a quantifier prefix with Qi∈{∀,∃}Q_i \in\{\forall, \exists\} and Ψ\Psi is a propositional matrix in conjunctive normal form, i.e., a conjunction of clauses (disjunctions) of literals over pairwise

distinct propositional variables x1…xmx_1 \ldots x_m. The standardized input format for PCNFs—and consequently the required format of this track—is QDIMACS [56]. Figure 1 shows an example QDIMACS encoding of an exclusive-or formula eligible for the PCNF track.

QDIMACS representation of a quantified Boolean formula

Figure 1. Example of a QDIMACS representation of ∀a∃x:(a∨x)∧(¬a∨¬x)\forall a\exists x : (a \lor x) \land(\lnot a \lor\lnot x)

PNCNF Track

In contrast to the PCNF track, the prenex non-CNF (PNCNF) track permits arbitrary propositional formulas as the matrix Ψ\Psi. The requirements regarding the quantifier prefix are the same as in the PCNF track. Input formulas for this track are accepted in the QCIR (Quantified CIRcuit) [23] format. The left side of Figure 2 shows an example of an QCIR-encoded QBF. A QCIR formula consists of a prefix as well as a sequence of gate definitions bound to Tseitin-like variables [69] called gate variables forming a directed acyclic graph (DAG). Supported gates include and, or, xor (exclusive-or), ite (if-then-else) as well as local quantifiers forall and exists. Consequently, QCIR formulas can represent non-prenex QBFs. To ensure that submitted formulas are in PNCNF, the Gallery imposes the following restrictions:

Example of a QCIR and cleansed QCIR instance

Figure 2. Example of a QCIR (left) representing ∀a∀b∃x:ite⁡(b,z∧x,∃y:xor⁡(a,¬y))\forall a\forall b\exists x:\operatorname{ite}(b,z\land x,\exists y:\operatorname{xor}(a,\lnot y)) and cleansed QCIR (right) instance representing ∀a∀b∀c∃x∃y∃z:(¬a∨x)∧(¬b∨y)∧(¬c∨z)∧¬(x∧y∧z)\forall a\forall b\forall c\exists x\exists y\exists z:(\lnot a\lor x)\land(\lnot b\lor y)\land(\lnot c\lor z)\land\lnot(x\land y\land z)

  • No free variables (closed prefix)

  • Only and and or gates are permitted

  • Local quantifier gates are not permitted

  • Variables may use numeric names only

The resulting restricted format is commonly referred to as cleansed QCIR, of which an example is shown on the right side of Figure 2. The semantics of submitted formulas in this format were checked using dedicated tools during benchmark selection.

DQBF Track

Dependency QBF (DQBF) extends QBF by allowing a non-linear quantifier prefix Π\Pi. Instead of a variable being dependent on their predecessor in a linear list, variable dependencies are stated explicitly utilizing Henkin quantifiers [4]. This increased expressiveness also raises the complexity of the decision problem to solve them from PSPACE to NEXPTIME. The input format for this track is DQDIMACS [21], an extension of QDIMACS additionally supporting the definition of Henkin quantifiers and their associated dependencies. Figure 3 shows a DQDIMACS encoding of a false exclusive-or formula, which can be constructed by using explicit dependencies.

Example of a DQDIMACS representation

Figure 3. Example of a DQDIMACS representation of ∀a∀b∃x(a)∃y(b):(a∨y)∧(¬a∨¬y)\forall a\forall b\exists x(a)\exists y(b) : (a \lor y) \land(\lnot a \lor\lnot y)

Crafted Instances Track

Crafted instances are parameterized formula families originating from proof complexity, such as the Kleine Büning–Karpinski–Flögel (KBKF) formulas [12]. They are designed to assess the strength of the underlying proof systems of QBF solvers. Since the size of these instances can be adjusted, they enable the analysis of how solving effort increases with increasing instance parameter. This scalability analysis is the primary objective of the Crafted Instances track. As all submitted crafted instances are in PCNF format, this track features the corresponding solvers.

Preprocessor Tracks

The Preprocessor track is the only track that does not accept formulas or solvers for submission. Instead, it focuses on evaluating preprocessors. A preprocessor rewrites the input into an equivalent formula without the primary goal of solving it but rather making it (potentially) easier for a subsequent solver to handle. Although also widely employed in inprocessing, preprocessors are executed independently on the benchmarks of a track resulting in a set of novel instances to evaluate. This track features the formulas of the PCNF and PNCNF tracks. No preprocessor was submitted for the DQBF track.

Benchmarks

In the following section, we present the instances submitted to and selected for each track. In addition to describing their origins, we provide basic information about the problems they encode and their structural characteristics. The selection process for the instances was the same for all tracks. First, all newly submitted formulas were solved using the eligible solvers for the respective track. Each run in this smoke test was subject to a time limit of 300 s with four instances executed concurrently on a single node. Instances solved by every solver were removed from the selection pool. From the remaining formulas, we randomly chose a representative subset. To complete the benchmarks, we selected a subset of instances from the previous QBF Gallery 2023 [34]. For the DQBF track, we chose instances from the QBFEval 2020 [55], as the same set of formulas was used in 2023. Finally, we compared the results reported by the solvers to identify disagreements and thus potential unsoundness. The selected formulas of the tracks can be found in the artifact published on Zenodo [51].

PCNF Benchmarks (QDIMACS Format)

Table 1 provides an overview of the submitted and selected formulas for the PCNF track, while detailed statistical data of the selected formulas is summarized in Table 2. In total, we received 523 instances across five different submissions of which 218 were selected for the Gallery. Additionally, we took 88 instances from the QBF Gallery 2023 [34], resulting in a total of 306 instances for the PCNF dataset. In the following we describe the submitted formula families.

FamilyAuthorSub. (Sel.)satunsatunsolved
Bounded SynthesisSlivovsky F.115 (40)41 (16)39 (12)35 (12)
Connect4Mayer-Eichberger V. et al170 (64)42 (13)101 (45)27 (6)
Feature ModelsHeisinger S.20 (16)2 (2)9 (5)9 (9)
GDL-GamesHe Y. et al.152 (68)42 (21)73 (38)37 (9)
Pasp2QBFMauá et al.66 (30)44 (23)22 (7)0 (0)
Total523 (218)171 (75)244 (107)108 (36)

Table 1. Submitted (Selected) QDIMACS formulas of the PCNF track

DatasetQ. Alt.Avg. ClausesAvg. VarsAvg. ∀\forallAvg. ∃\exists#
Bounded Synthesis22191956203456202940
Connect4: partial7x66-189043204120202030
Connect4: fromEmpty10-249034201026198334
Feature Models1617841428237999541824216
GDL-Games: GB32-724632613115951302017
GDL-Games: GB (bloqqer)12-4892051549638102615
GDL-Games: GD24-725636119068991896919
GDL-Games: GD (bloqqer)10-34144161930137186217
Pasp2QBF160371644139150530
Gallery23: Matrix Multiplication23059024496224449381
Gallery23: Grid Games12-20484016715316186
Gallery23: QBFEval 20201-442677968383921236257262
Gallery23: Hex Games12757719993219684
Gallery23: Organic Synthesis21362813886014388464
Gallery23: Pattern Finding21469562328361498
Gallery23: Linear Domino11-12635911151409753

Table 2. Statistics of the selected formulas in the PCNF track

  • The Bounded Synthesis instances encode the question of whether a Mealy machine of at most kk states realizes or falsifies a given LTL specification. The original encoding was introduced by Faymonville et al. [20].

  • The Connect4 instances [46] encode the popular Connect Four game as QBFs. Depending on the initial state of the game, the formulas are divided into two subfamilies. Partial7x6 instances begin from an ongoing game whereas fromEmpty instances assume an empty board. The QDIMACS instances were exported using Bule [39].

  • The Feature Models instances [32] encode feature-model differences as introduced by Heisinger et al. [31]. They include configurations ranging from bicycles to the Linux kernel. Initially, the problems were encoded in Unified Variability Language (UVL) [67] and afterwards exported by Booleguru [30].

  • The GDL-Games [27] instances are derived from a general Game Description Language (GDL) encoding. They express whether a player can achieve 100 points within nn steps, regardless of the actions of the other players. Details of the encoding were published by He et al. [26]. The benchmark set is divided into four sub-families: GB instances use a baseline encoding while GD instances use a dependency-based encoding. Both sets were additionally preprocessed using bloqqer [9], resulting in the GD (bloq) and GB (bloa) subfamilies.

  • The Pasp2QBF instances [45] encode probabilistic answer set programming (PASP) inference problems as 2QBF formulas [70]. The collection contains 12 sub-families representing different problems ranging from Sudoku puzzles to graph coloring. To generate the instances, the PASP problems were first encoded in WCNF formulas and subsequently rewritten as QBFs.

FamilyAuthorSub. (Sel.)satunsatunsolved
Feature ModelsHeisinger S.20 (16)0 (0)6 (2)14 (14)
Functional SynthesisKhalimov A.334 (25)311 (20)0 (0)23 (5)
Total554 (41)311 (20)6 (2)37 (19)
FamilyAuthorSub. (Sel.)satunsatunsolved
Feature ModelsHeisinger S.20 (16)0 (0)6 (2)14 (14)
Functional SynthesisKhalimov A.334 (25)311 (20)0 (0)23 (5)
Total554 (41)311 (20)6 (2)37 (19)

Table 3. Submitted (Selected) formulas of the PNCNF track

To complete the PCNF track, we also included instances from the QBF Gallery 2023 [33]. Detailed descriptions of the formula families can be found in the report of the Gallery 2023 [34].

PNCNF Benchmarks (QCIR Format)

Table 3 provides an overview of the submitted and selected formulas for the PNCNF track, while detailed statistical data of the selected formulas is shown in Table 4. In total, we received 554 instances across two submissions of which 41 were selected for the Gallery. Additionally, we took 335 instances from the QBF Gallery 2023 [34] resulting in a total of 376 instances for the PNCNF dataset. In the following, we describe the submitted formula families.

DatasetQ. Alt.Avg. gatesAvg. varsAvg. ∀\forallAvg. ∃\exists#
Feature Models150144199909995999516
Functional Synthesis1243962193186725
Gallery23: Grid Games10-201293140479419
Gallery23: Transitive Closure36-1102031042902884140610
Gallery23: Nested Counterfactuals790418796916
Gallery23: Generalized TTT6-1484767214628
Gallery23: Hyper-Properties0-15071952146059286820
Gallery23: Matrix Multiplication215103186425183910
Gallery23: Hadwiger Conjecture1288491961187821
Gallery23: QBFEval 20201-74134421411185956191
Gallery23: Circuit Minimization1-21403640319321130

Table 4. Statistics of the selected formulas in the PNCNF track

  • The Feature Models instances are the same as described for the PCNF track, but exported from the original UVL into the QCIR format using the tool Booleguru [30].

  • The Functional Synthesis instances [40] encode the automatic synthesis of a system from a behavioral specification. The resulting instances are formulated as safety games.

  • To complete the PNCNF track, we also included instances from the QBF Gallery 2023 [33]. Detailed descriptions of the formula families can be found in the report of the QBF Gallery 2023 [34].

DQBF Benchmarks (DQDIMACS Format)

Table 5 provides an overview of the submitted and selected formulas for the DQBF track, while detailed statistical data of the selected formulas is shown in Table 6. In total, we received 980 instances across two submissions of which 139 were selected for the gallery. Additionally, we took 181 instances from the QBFEval 2020 [55] resulting in a total of 320 instances for the DQBF dataset. In the following we describe the submitted formula families.

  • The Bounded Synthesis instances follow the same encoding as its PCNF-track counterpart but additionally uses Henkin dependencies. Two subfamilies were submitted: the state-symbolic encoding has propositional inputs whereas the fully-symbolic encoding has universal inputs, making it the most concise of the variants.

FamilyAuthorSub. (Sel.)satunsatunsolved
Bounded SynthesisSlivovsky F.386 (73)128 (16)87 (26)171 (31)
RamseyCheng C.504 (44)241 (18)31 (6)232 (20)
Succinct GraphCheng C.90 (22)10 (5)42 (9)38 (8)
Total980 (139)379 (39)160 (41)441 (59)

Table 5. Submitted (Selected) formulas of the DQBF track

DatasetQ. Alt.Avg. clausesAvg. varsAvg. ∀\forallAvg. ∃\existsAvg. dd#
Bounded Synthesis: Full12649624100672231006361436
Bounded Synthesis: State1208675958163312575400622037
Ramsey138912624901244
Succinct Graph: Clique19512476173688
Succinct Graph: Hamiltonian129321081720741710
Succinct Graph: Coloring117261243254
QBF Eval 20200-241059218974785181

Table 6. Statistics of the selected formulas in the DQBF track

  • The Ramsey and Succinct Graph instances [16] were submitted together with their generator by the same author as one single submission of two formula families. The Ramsey formulas check if a Ramsey number [2] is greater than some threshold. The Succinct Graph formulas encode graph problems from the three subcategories: Clique, Coloring and Hamiltonian.

  • To complete the DQBF track, we also included instances from the QBFEval 2020 [55].

Crafted Instances

Table 7 provides an overview of the submitted and selected formulas for the Crafted Instances track. We received one submission (QBFFamExt [62]) containing six new families all of which were selected for the track. Each family is parameterized by nn and some families provide additional parameters for further tuning. Using these parameters, we selected 16 instances across the six families. The details of this selection are shown in Table 8. In the following, we describe the selected formula families.

FamilyAbbr.Authorresult
Gadget-FamilyGADGETA. Schleitzer, O. Beyersdorffunsat
All-Equal-SATAESATA. Schleitzer, O. Beyersdorffunsat
Succinct-K-RadiusSUCCKRADA. Schleitzer, O. Beyersdorffunsat
Clique ColoringCLIQUECOLA. Schleitzer, O. Beyersdorffunsat
Generalised Subset SumSUBSETSUMA. Schleitzer, O. Beyersdorffunsat
Instancerange#
AESAT(n)n=5…30n = 5 \ldots30, 40,50,60,7030
CLIQUECOL(n)n=1…4n = 1 \ldots44
GADGET(n, base=ec, gadget=eq)n=5…30n = 5 \ldots30, 40,50,60,7030
GADGET(n, base=ec, gadget=xor)n=5…30n = 5 \ldots30, 40,50,60,7030
GADGET(n, base=ic, gadget=eq)n=5…30n = 5 \ldots30, 40,50,60,7030
GADGET(n, base=ic, gadget=xor)n=5…30n = 5 \ldots30, 40,50,60,7030
GADGET(n, base=sc, gadget=eq)n=5…30n = 5 \ldots30, 40,50,60,7030
GADGET(n, base=sc, gadget=xor)n=5…30n = 5 \ldots30, 40,50,60,7030
SUBSETSUM(n)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=3)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=5)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=7)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=10)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=15)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=20)n=5…30n = 5 \ldots30, 40,50,60,7030
SUCCKRAD(n,k=30)n=5…30n = 5 \ldots30, 40,50,60,7030

Table 7. New Crafted Instance formulas

  • The All-Equal-SAT family [61] encodes the following problem: Given a 3-CNF formula φ(X,Y)\varphi(X,Y), where (X,Y)(X,Y) is a partition of vars⁡(φ)\operatorname{vars}(\varphi), All-Equal-∃∀\exists\forall-3SAT solves, whether there exists an assignment to the variables in XX such that for every assignment to the variables in YY, at least one clause contains either only true or only false literals. The parameter nn specifies the number of clauses in the generated formula.

  • The Clique Coloring family [61] encode the decision problem given a graph G=(V,E)G=(V,E) and k=3k=3, whether GG admits a kk-clique-coloring, i.e. a coloring of the vertices in VV such that no maximal clique in GG is monochromatic. The parameter nn specifies the family index of the Grötzsch graph induction.

  • The Gadget-Family [60] problems are obtained by connecting a propositional base formula with a gadget. Available base formulas are single clause (SC), implication chain (IC) and

equality chain (EC). The gadget can be chosen to be either equality (EQ) or exclusive-or (XOR) constraints. Both the base formula and the gadget are additional parameters of the construction. The parameter nn specifies either the number of variables for SC or the chain length for IC and EC.

  • The Generalized Subset Sum [61] family encodes the following problem: Given two integer vectors uu and vv with ∣u∣=k|u| = k, ∣v∣=l|v| = l and an integer tt, the formula encodes ∃x∀y:(ux+vy≠t)\exists x \forall y : (ux + vy \ne t), where xx and yy are binary vectors with ∣x∣=k|x| = k, ∣y∣=l|y| = l. The parameter nn scales the lengths of uu and vv and determines the number of selector variables in the encoding.

  • The Succinct-K-Radius family encodes whether a Galperin-Widgerson representation CC of a directed graph G=(VG,EG)G = (V_G, E_G) has a radius of at most kk. The value kk is an additional parameter of the construction. The parameter nn specifies the grid height.

Solvers and Preprocessors

In the following, we introduce the solvers and preprocessors participating in each track. The participants include not only newly submitted tools but also solvers and preprocessors introduced in previous QBF Galleries. Some solvers appear in multiple tracks because of their support for different input formats.

PCNF Solvers

Table 9 lists the solvers participating in the PCNF track. Three newly submitted solvers, each with up to 8 different configurations, were included. The remaining solvers were selected from the previous QBF Gallery.

solverconfig.AuthorSub./Sel.typeref.
caqe-<br>bloqqer<br>hqspreL. Tentrup, M. RabeselectedCEGAR (clausal abstraction)[57]
DepQBF-<br>no-nenofexF. LonsingselectedQCDCL[43]
DepQBFcadicalM. HeisingerselectedQCDCL[29]
DynQBFG. Charwatselecteddynamic programming[13]
HybridQBFcaqe-v1<br>caqe-v2-m1<br>caqe-v2-m2<br>caqe-v3<br>hb-v0<br>hb-v1<br>hb-v2<br>hqsprebloqqerL. ZhaohuisubmittedCombination of approaches[42]
MiniQUF. SlivovskyselectedQCDCL[65]
Quteofo<br>plain<br>upureF. SlivovskysubmittedQCDCL[49]
RAReQSM. JanotaselectedCEGAR (expansion)[38]

Table 9. Participating solvers of the PCNF track

  • HybridQBF is based on DepQBF and incorporates additional solving techniques including WalkSAT [71] and glue clauses [3]. No accompanying paper or system description is available. The submitted versions utilize different configurations involving the solver caqe [57] as well as Bloqqer [9] and HQSPre [72] for pre- and inprocessing.

  • DepQBF-cadical [29] replaces the internal SAT solvers of the original DepQBF implementation, Minisat [19], for CaDiCaL [8].

  • Qute [49] was submitted in three different configurations: one using out-of-order (ofo) decisions [11], one implementing the DvpureD_{\mathrm{vpure}} (vpure) dependency scheme [17] and the (plain) standard configuration [49].

In the following we list the different solving paradigms applied by the PCNF solvers:

  • CEGAR (Counter Example Guided Abstraction Refinement) iteratively solves propositional abstractions of a QBF formula [18]. Candidate results obtained from an abstraction are validated against the original formula and refined. This process is repeated until the QBF is determined to be true or false. CEGAR is commonly seen as a two player game between the universal and existential player, trying to find a winning strategy for either player. The participating PCNF solvers utilize two flavours of CEGAR:

    • CEGAR with clausal abstraction decomposes the formula into an abstraction of a sequence of propositional formulas associated with the quantifier blocks [57].

    • CEGAR with expansion recursively1 expands quantified variables into propositional instances. (Counter)-models discovered during solving are then used to refine the expansion until a result is obtained [38].

  • Dynamic programming first partitions the CNF matrix into sub-problems using a tree decomposition approach and then processes this decomposition by dynamic programming [14], combining intermediate results from the subproblems. To account for dependencies induced by the quantifier prefix, dependency schemes are integrated into the solving process. This approach can be viewed as an expansion-based method as it combines local expansions of the subproblems.

  • QCDCL (Quantified Conflict Driven Clause learning) extends CDCL-based SAT solving by learning conflict clauses and solution cubes. Once an empty constraint can be learnt, the result is determined [7].

The following commands have been used for calling the solvers:

caqe <FILE>
caqe --preprocessor=bloqqer --qdo <FILE>
caqe --preprocessor=hqspre --qdo <FILE>
depqbf <FILE>
depqbf --qdo --no-dynamic-nenofex <FILE>
depqbf-cadical <FILE>
dynqbf -f <FILE>
HybridQBF_CAQE_V1 <FILE>
HybridQBF_CAQE_V2_M1 <FILE>
HybridQBF_CAQE_V2_M2 <FILE>
HybridQBF_CAQE_V3 <FILE>
HybridQBF_HB_V0 <FILE>
HybridQBF_HB_V1 <FILE>
HybridQBF_HB_V2 <FILE>
HybridQBF_HQSPre_Bloqqer <FILE>
miniQU <FILE>
qute --out-of-order-decisions all <FILE>
qute <FILE>
qute --depscheme upure <FILE>
rareqs <FILE>

PNCNF Solvers

Table 10 lists the solvers participating in the PNCNF track. Only Qute as described in the previous section was newly submitted to this track. The remaining solvers were selected from the previous QBF Gallery.

solverconfig.AuthorSub./Sel.typeref.
cqesto-<br>cadicalM. Janotaselectedpropositional abstraction[35]
GhostQ-<br>cegarW. KlieberselectedQDPLL<br>QDPLL + CEGAR[41]
MiniQUF. SlivovskyselectedQCDCL[65]
qfun-<br>cadicalM. Janotaselectedexpansion + ML[36]
QuABSL. TentrupselectedCEGAR (literal abstraction)[28]
Quteofo<br>plain<br>upureF. SlivovskysubmittedQCDCL[49]

Table 10. Participating solvers of the PNCNF track

In the following we list the different solving paradigms applied by the PNCNF solvers:

  • Expansion + ML utilizes machine learning to derive candidate strategies during expansion solving [36]. Rather than expanding the formula with individual assignments, learned strategies are incorporated. As further samples are collected, strategies as well as the expansion are iteratively refined until a result is obtained.

  • Literal abstraction is a CEGAR-based approach constructing propositional abstractions for quantifier blocks using literals to summarize the interaction between inner and outer blocks [68]. SAT solving provides candidate assignments and counterexamples, which are used to refine the abstractions recursively.

  • Propositional abstraction is a circuit-based extension of clausal abstraction. Rather than operating on a CNF matrix, the circuit representation of the propositional part of the QBF is preserved during solving. As in clausal abstraction, a propositional abstraction is constructed for each quantifier level and repeatedly solved and refined using SAT solving [35].

  • QDPLL (Davis-Putnam-Logemann-Loveland for QBFs) [25] is the foundation of modern QCDCL. The search algorithm assigns variables in prefix order while simplifying the formula under the current assignment. The algorithm can be utilized for non-clausal

representation and extended with different modalities of learning and propagation — including CEGAR learning as optionally applied in GhostQ [41].

  • QCDCL is the same paradigm as described for the PCNF solvers. PNCNF solvers using QCDCL commonly translate the input internally into a CNF representation by applying a Tseitin-style clausification [69].

The following commands have been used for calling the solvers:

cqesto <FILE>
cqesto-cadical <FILE>
qcir-to-gq.sh <FILE> | ghostq /dev/stdin -s-cnf -q2 -cegar 0
qcir-to-gq.sh <FILE> | ghostq /dev/stdin -s-cnf -q2 -cegar 1
miniQU <FILE>
qfun <FILE>
qfun-cadical <FILE>
quabs <FILE>
qute --out-of-order-decisions all <FILE>
qute <FILE>
qute --depscheme upure <FILE>

DQBF

Table 11 lists the solvers participating in the DQBF track. Three newly submitted solvers were included. The remaining solvers were selected from the previous QBF Gallery 2023 [34].

  • Pedant was submitted as the latest version of the established DQBF solver [59].

  • P3 is a simplified version of Pedant with optimized internal data-structure for Skolem functions.

  • Pedant-rewrite is a rewritten version of Pedant submitted in two configurations.

In the following we list the different solving paradigms applied by the DQBF solvers:

  • Quantifier elimination is a DQBF solving approach that eliminates variables responsible for the non-linear dependencies introduced by the Henkin quantifiers of the formula [24]. This transforms the input into a QBF with linearly ordered dependencies, which is then delegated to a QBF solver. This technique can also be applied to Binary decision diagram (BDD) like datastructures [64].

  • CEGIS (Counter Example Guided Inductive Synthesis) iteratively constructs Skolem functions of a QBF. If a candidate function is invalid for some assignment of the universal variables, the resulting counterexample is used for refinement by using interpolation based definitions. The process continues until correct Skolem functions are obtained or the QBF is proven to be false [59].

The following commands have been used for calling the solvers:

solverconfig.AuthorSub./Sel.typeref.
DQBDDJ. SíselectedQuantifier Elimination[64]
HQS-2022R. Wimmer, C. SchollselectedQuantifier Elimination[24]
P3F. Reichl, F. SlivovskysubmittedCEGIS[58]
PedantF. Reichl, F. SlivovskysubmittedCEGIS[59]
Pedant-rewrite- no-resC. ChengsubmittedCEGIS[15]

Table 11. Participating solvers of the DQBF track

processorformatAuthorSub./Sel.typeref.
BloqqerPCNFA. Biere, F. Lonsing, M. SeidlselectedClausal simplification[9]
PreProQPNCNFC. Peyrer, M. SeidlsubmittedCircuit simplification[52]

Table 12. Preprocessors

dqbdd <FILE>
hqs2 <FILE>
p3 <FILE>
pedant <FILE>
pedant-rewrite <FILE>
pedant-rewrite <FILE> --max-resolutions 1

Preprocessors

Table 12 lists the preprocessors participating in the preprocessor track. Only one new preprocessor, PreProQ, was submitted. In addition, Bloqqer was selected for the PCNF track.

  • PreProQ (Pre-Processor for Q-circuits) is a PNCNF preprocessor that applies circuit-structure simplification techniques to exploit non-CNF properties [52].

The following parametrization has been used for the preprocessors.

bloqqer <FILE>
preproq <FILE>

Evaluation

This chapter presents the evaluation results of the QBF Gallery 2026. First we describe the methodology of the smoke test. Then we analyze the various metrics and results from our evaluation of each track.

Smoke Test

Before the evaluation, we tested all newly available formulas with a timeout of 300 s using the solvers participating in the complementing track. The smoke test served three purposes: ensuring that each formula can be parsed without errors, identifying potential solver issues early and gathering data necessary for the benchmark selection. A lack of consensus among the results of different solvers may indicates unsound behavior. In the following, we discuss the relevant incidents.

  • Failing instance: PCNF/connect4/partial7x6/6_12_442317624273_-13_SAT.qdimacs The following table provides an overview of the solver results on this instance:

SATUNSAT
caqecaqe-hqspre
caqe-bloqqerHybridQBF-caqe-v2-m2
DepQBFHybridQBF-caqe-v1
DepQBF-cadicalHybridQBF-hb-v0
DepQBF-no-nenofexHybridQBF-hb-v1
HybridQBF-hb-v2HybridQBF-hqsprebloqqer
Qute-plain
Qute-ofo
RAReQS
MiniQU
HybridQBF-caqe-v3
Qute-upure
HybridQBF-caqe-v2-m1

Table 8.

One submitted PCNF formula was reported to be unsatisfiable by six solvers, while the other 13 reported satisfiability. We used DepQBF with QRP certificate generation to verify the result and obtained a successful proof of satisfiability. Consequently, the six solvers that reported unsatisfiable were disqualified for producing an unsound result.2

  • Failing instance: DQBF/ramsey/general_R_3_3_04_sat.dqdimacs The following table provides an overview of the solver results on this instance:

SATUNSAT
PedantDQBDD
P3HQS-2022
Pedant-rewrite-no-res
Pedant-rewrite

Table 20.

In total, five formulas in the DQBF track showed discrepancies. The specified formula is one representative of them. In each case, the solvers DQBDD and HQS-2022 reporting different results. To resolve these cases, we used Pedant to extract models from for the respective formulas, which then could be verified using the provided toolchain (certifyModel.py). Consequently, the two solvers which disagreed with the verified results in multiple cases were disqualified.

After running the preprocessor track, an additional discrepancy was found for HybridQBF-hb-v2. The instance PCNF/bounded-synthesis/simple_arbiter_enc_6__system__b8.qdimacs was reported as unsatisfiable after preprocessing with Bloqqer. Consequently, this solver was also disqualified.2

PCNF Track

Table 13 presents the evaluation results for the PCNF track. For completeness, disqualified solvers are listed with an indicator whether their results are counted. In addition to the participating tools, also the Virtual Best Solver (VBS) is listed. VBS (all) shows the performance of the Virtual Best solver including the disqualified solvers. The solvers are sorted according to their PAR-2 score with a memory limit of 8 GB. The table additionally reports the number of solved formulas, the distribution of satisfiable and unsatisfiable formulas, uniquely solved instances and the number of error codes. Returning unknown (0) was not counted as an error but treated as a timeout receiving the usual PAR-2 penalty. For comparison, we also reported PAR-2 scores using a memory limit of 128 GB. The visualization of those results is shown in Figure 4.

Figure 4. Results of the PCNF track

SolverPAR-2 (8 GB)PAR-2 (128 GB)SolvedsatunsatUniqueErrors
VBS (all)701.75703.881978211580
VBS746.99747.0418879109100
hybridqbf-hb-v1873.23869166719500
hybridqbf-hqsprebloqqer885.39889.64163729110
hybridqbf-hb-v2890.29896.07163729111
hybridqbf-hb-v0909.45909.12160709000
caqe-bloqqer929.70929.80154718300
hybridqbf-caqe-v2-m1949.48949.45152638900
hybridqbf-caqe-v3960.35960.45151668530
hybridqbf-caqe-v1969.28972.134149678210
caqe-hqspre994.75988.924143657802
hybridqbf-caqe-v2-m21000.511000.51142647800
depqbf-no-nenofex1019.171016.41140578300
depqbf-cadical1022.401022.35139568304
depqbf1030.251030.40138568200
caqe1030.801030.89138578100
miniq1168.891168.76114486600
rareqs1392.471392.3572373500
qute-plain1399.051399.0272314100
qute-upure1402.541402.4772324000
qute-ofo1590.301590.2237201700
dynqbf1662.561660.162516920

Table 13. Evaluation data of the PCNF track. Red colored rows are disqualified.

The winner of the PCNF track is caqe with Bloqqer as its preprocessor. After accounting for disqualifications, HybridQBF achieved second place, while demonstrating considerable potential for improved results. Third place was taken by DepQBF. Although DynQBF is ranked last, it uniquely solved two formulas. Increasing the memory limit did not have a significant effect on the results.

PNCNF Track

Table 14 presents the evaluation results for the PNCNF track. As in the PCNF track, we report the usual statistics as well as the additional evaluation with a memory limit of 128 GB. The winner of this track is cqesto with an internal CaDiCaL SAT solver. Second place was achieved by QuABS, followed by qfun in third place. MiniQU is noteworthy for solving the largest number of formulas uniquely. Increasing the memory limit had a slightly positive effect on some solvers, with cqesto showing the biggest improvement.

Results of the PNCNF track

Figure 5. Results of the PNCNF track

SolverPAR-2 (8 GB)PAR-2 (128 GB)SolvedsatunsatUniqueErrors
VBS415.62415.58297168129220
cqesto-cadical778.58765.9822221338910
quabs796.86793.922191229760
cqesto815.30805.2172201239700
qfun-cadical957.02947.9651851028350
qfun972.42969.9041861018520
ghostq-cegar1019.111015.93175948101
miniq1037.801031.22167996880
ghostq1183.001180.29137835401
qute-plain1314.341314.35110605000
qute-ofo1463.491463.4778364200
qute-upure1495.571495.5770313900

Table 14. Evaluation data of the PNCNF track

Results of the DQBF track

Figure 6. Results of the DQBF track

SolverPAR-2 (8 GB)PAR-2 (128 GB)SolvedsatunsatUniqueErrors
VBS (all)719.97723.1820091109100
VBS821.77821.6418782105230
p3921.84921.931696710230
pedant956.63950.09161679400
hqs20221105.161105.62129616861
dqbdd1143.251143.19120447616
pedant-rewrite1247.711244.68110585200
pedant-rewrite-no-res1252.271252.27110595100

Table 15. Evaluation data of the DQBF track

DQBF Track

Table 15 presents the evaluation for the DQBF track. As in the previous tracks, the table reports the usual statistics. Disqualified solvers are listed for completeness and the VBS (all) solver visualizes the Virtual Best Solver over all participants.

The winner of the DQBF track is P3. Second place was achieved by Pedant, followed by Pedant-rewrite. Even though DQBDD was disqualified, it is noteworthy for solving the most formulas uniquely.

Preprocessor Track

In this track, we evaluated PCNF and PNCNF tracks by placing a preprocessor before each solver. The reported runtimes include both preprocessing and solving time. Table 16 presents statistics for preprocessors run without an attached solver.

Table 17 presents the results obtained by running Bloqqer before the solvers in the PCNF track. We compare the number of formulas solved by each resulting pipeline with the corresponding original results from the PCNF track without preprocessing. Note that the PAR-2 score is computed only over the formulas not trivially solved by the preprocessor, whereas the number of solved formulas includes these 34 instances. It is further noticeable that some HybridQBF configurations suddenly produced a lot of errors. These errors originated in the parser, which reported that no input stream was available. They occurred only sporadically, with no apparent pattern. We were unable to determine their cause and hope that the authors of the solver can address this issue in future versions. The results for HybridQBF-hb-v2 were not processed further because of the inconsistency detected directly in this track. DepQBF-no-nenofex won this track solving 26 additional formulas. Second place went to caqe, which solved 25 additional instances followed by HybridQBF in third place despite three erroneous instances. Qute benefited the most from Bloqqer, solving 37 additional formulas.

Table 18 presents the results of running PreProQ before the solvers in the PNCNF track. Due to the clausification capabilities of this preprocessor, we additionally included the PCNF track winner caqe. The instance PNCNF/Gallery23/hyperprop/2.2.qcir caused PreProQ to exceed its 8 GB memory limit. This subsequently resulted in an error for the attached solver, explaining the single error reported for every solver in this track

Proc.TracktotalsolvedoutAvg. time
BloqqerPCNF306341219.26 s
PreProQPNCNF37601211.62 ms

Table 16. Results of the preprocessors on their corresponding track

Solver (bloqqer+...)PAR-2solved (incl. 34)solved (PCNF)satunsatUniqueErrors
VBS (all)749.5520219755113140
VBS776.4619718855108140
depqbf-no-nenofex991.07166140468610
caqe994.66163138498000
caqe-bloqqer995.558163154498000
hybridqbf-caqe-v2-m1997.09163152498003
depqbf-cadical1002.79162139458300
depqbf1022.72159138438200
hybridqbf-caqe-v11048.32156149418130
hybridqbf-hb-v01049.271561604280140
hybridqbf-hqsprebloqqer1055.681531634277036
hybridqbf-hb-v11060.831521664276038
caqe-hqspre1088.49148143397500
hybridqbf-caqe-v31089.29148151387610
hybridqbf-caqe-v2-m21092.09147142387503
miniq1103.37146114427020
qute-plain1329.6610972324310
qute-upure1334.8010872324210
rareqs1387.5110072293720
qute-ofo1680.42533710900
dynqbf1729.9536257520

Table 17. Results of Bloqqer with solvers on the PCNF track

Solver (preproq+...)PAR-2solvedsolved (PNCNF)satunsatUniqueErrors
VBS415.22297297167130201
cqesto-cadical701.432392221409931
quabs791.872202191279371
cqesto841.082132201189501
miniq962.521811671057671
qfun-cadical969.991841851038121
qfun1015.23177186987911
ghostq-cegar1050.73167175927501
ghostq1184.33138137845401
qute-plain1253.48122110635901
qute-ofo1354.459878494901
caqe1383.0493-405301
qute-upure1407.878970365301

Table 18. Results of PreProQ with solvers on the PNCNF track

The winner of this track is cqesto-cadical. Notably, the base version of cqesto did not benefit to the same extent. Second place was achieved by QuABS, followed by MiniQU in third place. The biggest benefit was observed for Qute-ofo, which solved 20 additional instances.

Crafted Instances Track

Table 19 presents the results of the Crafted Instances track. Due to space limitations, we assigned aliases to the instances. The following list gives the corresponding mappings:

F0=AESAT(nn)F8=SUBSETSUM(nn)
F1=CLIQUECOL(mm)F9=SUCCKRAD(nn, kk=3)
F2=GADGET(nn, base=ec, gadget=eq)F10=SUCCKRAD(nn, kk=5)
F3=GADGET(nn, base=ec, gadget=xor)F11=SUCCKRAD(nn, kk=7)
F4=GADGET(nn, base=ic, gadget=eq)F12=SUCCKRAD(nn, kk=10)
F5=GADGET(nn, base=ic, gadget=xor)F13=SUCCKRAD(nn, kk=15)
F6=GADGET(nn, base=sc, gadget=eq)F14=SUCCKRAD(nn, kk=20)
F7=GADGET(nn, base=sc, gadget=xor)F15=SUCCKRAD(nn, kk=30)

with n={5…30}∪{40,50,60,70}n = \{5 \ldots30\} \cup\{40, 50, 60, 70\} and m={1…4}m = \{1 \ldots4\}.

In this track, the parameter nn is increased incrementally until either the time limit is reached or the final instance is solved. Each table entry denotes the largest nn solved successfully within the resource limitations. A ✓ indicates that all instances of the respective family were solved successfully.

SolverF0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15
caqe12114121413151310✓✓✓✓✓✓✓
caqe-bloqqer133✓✓✓✓✓✓16✓✓✓✓✓✓✓
caqe-hqspre12✓14131513151314✓✓✓✓14✓30
depqbf1915012✓✓✓✓10✓✓✓✓✓✓✓
depqbf-cadical1815012✓✓✓✓10✓✓✓✓✓✓✓
depqbf-no-nenofex21120122412241210✓✓✓✓✓✓✓
dynqbf✓1✓✓✓✓✓✓30✓✓✓✓✓✓✓
hybridqbf-caqe-v113✓14131513151314✓✓✓✓24✓0
hybridqbf-caqe-v2-m113314121413151310✓✓✓✓✓✓✓
hybridqbf-caqe-v2-m212✓14131513151314✓✓✓✓40✓0
hybridqbf-caqe-v314314131513151315✓✓✓✓✓✓✓
hybridqbf-hb-v014224132413231319✓✓✓✓✓✓✓
hybridqbf-hb-v114224132413231319✓✓✓✓✓✓✓
hybridqbf-hb-v214224132413231320✓✓✓✓✓✓✓
hybridqbf-hqsprebloqqer14224132413231319✓✓✓✓✓✓✓
miniq22124122312241211✓✓✓✓✓✓✓
qute-ofo✓1✓✓✓✓✓✓12✓✓59000
qute-plain✓1✓✓✓✓✓✓12✓✓✓✓✓✓23
qute-upure✓1✓✓✓✓✓✓12✓✓✓✓✓✓16
rareqs11114121411141110✓✓✓✓✓✓✓

Table 19. Crafted formulas

The CLIQUECOL instances were the most challenging in this track as they were the only family for which the range of nn had to be adjusted. Even on the range of n=1…4n = 1 \ldots4, the fastest runtime was still above 500 s. In contrast, the SUCKRAD instances were the easiest to solve. No solver solved all SUBSETSUM instances up to n=70n = 70. Overall, DynQBF performed the best in this track, successfully solving every family except CLIQUECOL and SUBSETSUM.

Beyond PAR-2 Scores

This section presents additional statistics for the three main tracks. In particular, we examine similarities between solvers and analyze the performance of each solver on the individual formula families. To this end we visualize solver similarities using heatmaps, following a concept introduced at the SAT Competition 2020 [22]. For each pair of solvers, we compute the Pearson correlation coefficient [48] of their runtimes over the individual instances. The resulting values are represented by a color gradient ranging from green (strong inverse correlation) to yellow (no correlation) to red (strong correlation). A solver compared with itself therefore appears in red on the diagonal of the heatmap. Furthermore, we provide histograms showing the results for each participating solver, segmented by the formula families.

PCNF Track

Figure 7 shows the similarities between the solvers in the PCNF track. The solvers least similar to the other participants were DynQBF and Qute with out-of-order decisions. HybridQBF and its hb variants were the most similar to one another. Overall, the track exhibited a moderate degree of variation between solver behaviors. Figure 8 shows the number of solved formulas for each solver, segmented by formula family. The Pasp2QBF family was solved the most frequently overall, whereas the solvers struggled the most with the Gallery 23: Pattern finding instances.

Solver similarities of the PCNF track visualized in a heatmap

Figure 7. Solver similarities of the PCNF track visualized in a heatmap

Formula families solved by the solvers of the PCNF track

Figure 8. Formula families solved by the solvers of the PCNF track

The Feature model family has by far the largest average number of clauses and variables, whereas Gallery23: Grid Games has the smallest averages for both measures. Both

Pasp2QBF and Feature model contain only one quantifier alternation, while GDL-Games: GB has the largest average number of quantifier alternations. The hard to solve Gallery23: Pattern finding family does not stand out in any of these metrics. Overall, no strong correlation between those statistics and the hardness of a formula was observed.

PNCNF Track

Figure 9 shows the similarities between the solvers in the PNCNF track. The variation among these solvers is substantially higher than in the PCNF track, indicating less similar solver behavior overall. The most similar solvers are primarily different configurations of the same solver. Figure 10 shows the number of solved formulas for each solver, segmented by formula family. The highest number of solved instances comes from the QBFEval2020, which unsurprising since this family accounts for approximately 50 % of the instances of the track. The most challenging families were the new Feature Models and the Gallery23: Transitive Closure.

Solver similarities of the PNCNF track visualized in a heatmap

Figure 9. Solver similarities of the PNCNF track visualized in a heatmap

Formula families solved by the solvers of the PNCNF track

Figure 10. Formula families solved by the solvers of the PNCNF track

The Gallery23: Hyper-Properties family has the largest average number of gates, while having a comparatively moderate average number of variables and the Feature Models family has the largest average number of variables. Generalized TTT has the smallest average numbers of both gates and variables. The difficult Gallery23: Transitive Closure family has the second-largest average number of variables. Overall, the results indicate a slight trend towards increased solving time for families with more variables.

DQBF Track

Figure 11 shows the similarities between the solvers of the DQBF track. Pedant-rewrite, DQBDD and HQS-2022 differ most from the remaining solvers in this track. Pedant and P3 are the most similar.

Solver similarities of the DQBF track visualized in a heatmap

Figure 11. Solver similarities of the DQBF track visualized in a heatmap

Figure 12 shows the number of solved formulas for each solver, segmented by formula family. Most solved instances originated from the QBFEval2020 family, which accounts for more than half of the formulas in the track. The Succinct Graph: Coloring family was the most challenging overall.

Formula families solved by the solvers of the DQBF track

Figure 12. Formula families solved by the solvers of the DQBF track

The Bounded Synthesis: Full family has by far the largest average numbers of clauses and variables, while also having the lowest proportion of variables quantified by Henkin quantifiers at only 0.014 %. The Succinct Graph: Coloring family has the smallest average numbers of both variables and clauses. In contrast, Succinct Graph: Clique has the highest average proportion of Henkin-quantified variables at 27.53 %. Overall, these metrics do not appear to correlate with formula hardness.

Conclusion

The QBF Gallery 2026 continued the traditional series of QBF evaluations. We evaluated a range of new formulas and solvers with a noticeable increase in interest in DQBF. All submitted instances and solvers were described, analyzed and tested before conducting the detailed evaluation.

In addition to the main tracks, we evaluated new crafted instances and investigated the effect of preprocessing. Beyond the usual PAR-2 scores, we also provided insights into solver similarities and performance on individual formula families. Finally, we released the new benchmarks in a dedicated artifact [51].

Results with disqualified solvers

Figure 13 and 14 show the results of the PCNF and DQBF track with the disqualified solvers.

Results of the PCNF track containing also the disqualified solvers

Figure 13. Results of the PCNF track containing also the disqualified solvers

Results of the DQBF track containing also the disqualified solvers

Figure 14. Results of the DQBF track containing also the disqualified solvers

References

  1. [1]SAT 2026. 29th International Conference on Theory and Applications of Satisfiability Testing, volume 377 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. URL: https://www.dagstuhl.de/dagpub/978-3-95977-431-4.
  2. [2]Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on ramsey numbers. Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980. doi:10.1016/0097-3165(80)90030-8.DOI
  3. [3]Gilles Audemard and Laurent Simon. Predicting learnt clauses quality in modern SAT solvers. In IJCAI 2009: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 399–404, 2009. URL: http://ijcai.org/Proceedings/09/Papers/074.pdf.
  4. [4]Valeriy Balabanov, Hui-Ju Katherine Chiang, and Jie-Hong R. Jiang. Henkin quantifiers and boolean formulae: A certification perspective of dqbf. Theoretical Computer Science, 523:86–100, 2014. doi:10.1016/j.tcs.2013.12.020.DOI
  5. [5]Daniel Le Berre, Massimo Narizzano, Laurent Simon, and Armando Tacchella. The second QBF solvers comparative evaluation. In SAT 2004: 7th International Conference on Theory and Applications of Satisfiability Testing, volume 3542 of Lecture Notes in Computer Science, pages 376–392. Springer, 2004. doi:10.1007/11527695\_28.DOI
  6. [6]Daniel Le Berre, Laurent Simon, and Armando Tacchella. Challenges in the QBF arena: the sat’03 evaluation of QBF solvers. In SAT 2003: 6th International Conference on Theory and Applications of Satisfiability Testing, volume 2919 of Lecture Notes in Computer Science, pages 468–485. Springer, 2003. doi:10.1007/978-3-540-24605-3\_35.DOI
  7. [7]Olaf Beyersdorff, Mikoláš Janota, Florian Lonsing, and Martina Seidl. Quantified boolean formulas. In Handbook of Satisfiability - Second Edition, volume 336 of Frontiers in Artificial Intelligence and Applications, pages 1177–1221. IOS Press, 2021. doi:10.3233/FAIA201015.
  8. [8]Armin Biere, Tobias Faller, Katalin Fazekas, Mathias Fleury, Nils Froleyks, and Florian Pollitt. CaDiCaL 2.0. In CAV 2024: 36th International Conference on Computer Aided Verification, volume 14681 of Lecture Notes in Computer Science, pages 133–152. Springer, 2024. doi:10.1007/978-3-031-65627-9\_7.DOI
  9. [9]Armin Biere, Florian Lonsing, and Martina Seidl. Blocked clause elimination for QBF. In CADE 23: 23rd International Conference on Automated Deduction, volume 6803 of Lecture Notes in Computer Science, pages 101–115. Springer, 2011. doi:10.1007/978-3-642-22438-6\_10.DOI
  10. [10]Roderick Bloem, Nicolas Braud-Santoni, Vedad Hadzic, Uwe Egly, Florian Lonsing, and Martina Seidl. Expansion-based QBF solving without recursion. CoRR, abs/1807.08964, 2018. doi:10.48550/ARXIV.1807.08964.DOI
  11. [11]Benjamin Böhm, Tomás Peitl, and Olaf Beyersdorff. Should decisions in QCDCL follow prefix order? J. Autom. Reason., 68(1):5, 2024. doi:10.1007/S10817-024-09694-6.
  12. [12]Hans Kleine Büning, Marek Karpinski, and Andreas Flögel. Resolution for quantified boolean formulas. Information and computation, 117(1):12–18, 1995. doi:10.1006/inco.1995.1025.DOI
  13. [13]Günther Charwat and Stefan Woltran. Bdd-based dynamic programming on tree decompositions. Database and Artificial Intelligence Group, TU Wien, Tech. Rep. DBAI-TR-2016, 95, 2016. URL: http://hdl.handle.net/20.500.12708/78589.
  14. [14]Günther Charwat and Stefan Woltran. Dynamic programming-based qbf solving. In QBF@SAT, pages 27–40, 2016. URL: https://ceur-ws.org/Vol-1719/paper2.pdf.
  15. [15]Che Cheng, Long-Hin Fung, Jie-Hong R. Jiang, and Tony Tan. pedant-rewrite. Zenodo, 2026. doi:10.5281/zenodo.20265576.DOI
  16. [16]Che Cheng, Long-Hin Fung, Chi-Kit Ng, Chen-Ching Nieh, Jie-Hong R. Jiang, Friedrich Slivovsky, and Tony Tan. DQBF instances: Ramsey and succinct graph. Zenodo, 2026. URL: https://zenodo.org/records/20263590.
  17. [17]Leroy Chew and Tomás Peitl. Strong (D)QBF dependency schemes via pure paths with applications to proof checking. In SAT 2026: 29th International Conference on Theory and Applications of Satisfiability Testing, volume 377 of LIPICs, pages 11:1–11:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.SAT.2026.11.
  18. [18]Edmund M. Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, and Helmut Veith. Counterexample-guided abstraction refinement for symbolic model checking. J. ACM, 50(5):752–794, 2003. doi:10.1145/876638.876643.
  19. [19]Niklas Eén and Niklas Sörensson. Minisat. Github, 2013. URL: https://github.com/niklasso/minisat.
  20. [20]Peter Faymonville, Bernd Finkbeiner, Markus N. Rabe, and Leander Tentrup. Encodings of bounded synthesis. In TACAS 2017: 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 10205 of Lecture Notes in Computer Science, pages 354–370, 2017. doi:10.1007/978-3-662-54577-5\_20.
  21. [21]Andreas Fröhlich, Gergely Kovásznai, Armin Biere, and Helmut Veith. idq: Instantiation-based dqbf solving. In POS-14: Fifth Pragmatics of SAT workshop, volume 27 of EPiC Series in Computing, pages 103–116. EasyChair, 2014. doi:10.29007/1s5k.
  22. [22]Nils Froleyks, Marijn Heule, Ashlin Isar, Matti Järvisalo, and Martin Suda. SAT competition 2020. Artificial Intelligence, 301:103572, 2021. doi:10.1016/J.ARTINT.2021.103572.
  23. [23]QBF Gallery, 2014. URL: https://qbf.pages.sai.jku.at/qcir.pdf.
  24. [24]Karina Gitina, Ralf Wimmer, Sven Reimer, Matthias Sauer, Christoph Scholl, and Bernd Becker. Solving DQBF through quantifier elimination. In DATE 2015: Proceedings of the 2015 Design, Automation and Test in Europe Conference, pages 1617–1622. ACM, 2015. URL: https://dl.acm.org/doi/10.5555/2755753.2757188.DOI
  25. [25]Alexandra Goultiaeva, Vicki Iverson, and Fahiem Bacchus. Beyond cnf: A circuit-based qbf solver. In International Conference on Theory and Applications of Satisfiability Testing, pages 412–426. Springer, 2009. doi:10.1007/978-3-642-02777-2_38.DOI
  26. [26]Yifan He, Abdallah Saïdine, and Michael Thielscher. Solving Two-player Games with QBF Solvers in General Game Playing. In AAMAS 2024: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 807–815. International Foundation for Autonomous Agents and Multiagent Systems, 2024. doi:10.5555/3635637.3662934.DOI
  27. [27]Yifan He, Abdallah Saïdine, and Michael Thielscher. PCNF instances: GDL-games. Github, 2026. URL: https://github.com/hharryf/gdl2qbf-general/tree/main/qbfgallery2026.
  28. [28]Jesko Hecking-Harbusch and Leander Tentrup. Solving QBF by abstraction. In GandALF 2018: Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification, volume 277 of EPTCS, pages 88–102, 2018. doi:10.4204/EPTCS.277.7.DOI
  29. [29]Maximilian Heisinger. dqbf-cadical. Gitlab, 2025. URL: https://gitlab.sai.jku.at/maximilian/deqbf-cadical.
  30. [30]Maximilian Heisinger, Simone Heisinger, and Martina Seidl. Booleguru, the propositional polyglot (short paper). In IJCAR 2024: 12th International Joint Conference on Automated Reasoning, volume 14739 of Lecture Notes in Computer Science, pages 315–324. Springer, 2024. doi:10.1007/978-3-031-63498-7\_19.DOI
  31. [31]Simone Heisinger, Maximilian Heisinger, and Martina Seidl. (semantic) feature model differences with (Q)SAT. In SLE 2025: 18th International Conference on Software Language Engineering, pages 189–198. ACM, 2025. doi:10.1145/3732771.3742723.DOI
  32. [32]Simone Heisinger, Maximilian Heisinger, and Martina Seidl. PCNF/PNCNF instances: Feature models. GitLab, 2026. URL: https://gitlab.sai.jku.at/monasan/fm-qbf.
  33. [33]Simone Heisinger, Luca Pulina, and Martina Seidl. Instances of the QBF gallery 2023. GitLab, 2023. URL: https://qbf23.pages.sai.jku.at/gallery/.
  34. [34]Simone Heisinger, Luca Pulina, and Martina Seidl. The qbf gallery 2023, 2026. URL: https://arxiv.org/abs/2604.16153, arXiv:2604.16153.
  35. [35]Mikolás Janota. Circuit-based search space pruning in QBF. In SAT 2018: 21st International Conference on Theory and Applications of Satisfiability Testing, volume 10929 of Lecture Notes in Computer Science, pages 187–198. Springer, 2018. doi:10.1007/978-3-319-94144-8\_12.DOI
  36. [36]Mikolás Janota. Towards generalization in QBF solving via machine learning. In AAAI 18: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, the 30th innovative Applications of Artificial Intelligence and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, pages 6607–6614. AAAI Press, 2018. doi:10.1609/AAAI.V32I1.12208.DOI
  37. [37]Mikolás Janota, Charles Jordan, Will Klieber, Florian Lonsing, Martina Seidl, and Allen Van Gelder. The QBFGallery 2014: The QBF competition at the floc olympic games. J. Satisf. Boolean Model. Comput., 9(1):187–206, 2014. doi:10.3233/SAT190108.
  38. [38]Mikolás Janota, William Klieber, Joao Marques-Silva, and Edmund Clarke. Solving QBF with counterexample guided refinement. Artificial Intelligence, 234:1–25, 2016. doi:10.1016/j.artint.2016.01.004.DOI
  39. [39]Jean Christoph Jung, Valentin Mayer-Eichberger, and Abdallah Saffidine. QBF programming with the modeling language bule. In SAT 2022: 25th International Conference on Theory and Applications of Satisfiability Testing, volume 236 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.31.DOI
  40. [40]Ayrat Khalimov. PCNF instances: Functional synthesis. Github, 2026. URL: https://github.com/5nizza/relation-determinization.
  41. [41]William Klieber. Ghsto qbf solver system description, 2012. URL: https://www.wklieber.com/ghstoq/ghstoq-sys-desc.pdf.
  42. [42]Zhaohui Liu. Hybridqbf. Github, 2026. URL: https://github.com/LiuZH0001/QBFGallery26_HybridQBF_HQSPre_Bloqqer.
  43. [43]Florian Lonsing and Uwe Egly. DepQBF 6.0: A search-based QBF solver beyond traditional QCDCL. In CADE 26: 26th International Conference on Automated Deduction, volume 10395 of Lecture Notes in Computer Science, pages 371–384. Springer, 2017. doi:10.1007/978-3-319-63046-5\_23.
  44. [44]Florian Lonsing, Martina Seidl, and Allen Van Gelder. The QBF gallery: Behind the scenes. CoRR, abs/1508.01045, 2015. arXiv:1508.01045, doi:10.48550/ARXIV.1508.01045.DOI
  45. [45]Denis D. Mauá, Rahul Kapur, YooJung Choi, and Guy Van den Broeck. PCNF instances: PASP2QBF. Github, 2026. URL: https://github.com/Rkus990/pasp2qbf-benchmarks.
  46. [46]Valentin Mayer-Eichberger and Abdallah Saffidine. PCNF instances: Connect4. Github, 2026. URL: https://github.com/vale1410/connect4qbf.
  47. [47]Massimo Narizzano, Luca Pulina, and Armando Tacchella. Report of the third QBF solvers evaluation. J. Satisf. Boolean Model. Comput., 2(1-4):145–164, 2006. doi:10.3233/SAT190019.
  48. [48]Karl Pearson. Note on regression and inheritance in the case of two parents. proceedings of the royal society of London, 58:240–242, 1895. URL: https://www.jstor.org/stable/115794.
  49. [49]Tomás Peitl, Friedrich Slivovsky, and Stefan Szeider. Dependency learning for QBF. J. Artif. Intell. Res., 65:180–208, 2019. URL: https://doi.org/10.1613/jair.1.11529, doi: 10.1613/JAIR.1.11529.
  50. [50]Claudia Peschiera, Luca Pulina, Armando Tacchella, Uwe Bubeck, Oliver Kullmann, and Inês Lynce. The seventh QBF solvers evaluation (qbfeval’10). In SAT 2010: 13th International Conference on Theory and Applications of Satisfiability Testing, volume 6175 of Lecture Notes in Computer Science, pages 237–250. Springer, 2010. doi:10.1007/978-3-642-14186-7\_20.
  51. [51]Cynthia Peyrer, Luca Pulina, and Martina Seidl. Qbf gallery 2026, 2026. doi:10.5281/zenodo.22639316.arxiv.org/abs/2611.18169
  52. [52]Mark Peyrer. Reprocessing of Non-QCNF prenex formulas. 2024. URL: https://resolver.obvsg.at/urn:nbn:at:at-ubl:1-7273.
  53. [53]Luca Pulina. The ninth QBF solvers evaluation - preliminary report. In QBF 2016: Proceedings of the 4th International Workshop on Quantified Boolean Formulas, volume 1719 of CEUR Workshop Proceedings, pages 1–13. CEUR-WS.org, 2016. URL: https://ceur-ws.org/Vol-1719/paper0.pdf.
  54. [54]Luca Pulina and Martina Seidl. The 2016 and 2017 QBF solvers evaluations (QBFEVAL’16 and QBFEVAL’17). Artificial Intelligence, 274:224–248, 2019. doi:10.1016/J.ARTINT.2019.04.002.
  55. [55]Luca Pulina, Martina Seidl, and Ankit Shukla. Qbf evaluation 2020, 2020. URL: https://www.qbflib.org/event_page.php?year=2020.
  56. [56]QBFLib, 2005. URL: https://www.qbflib.org/qbflib.html.
  57. [57]Markus N. Rabe and Alexander Tentrup. CAQE: A certifying QBF solver. In FMCAD 2015: 15th Conference on Formal Methods in Computer-Aided Design, pages 136–143. IEEE, 2015. doi:10.1109/FMCAD.2015.7542263.DOI
  58. [58]Franz Reichl and Friedrich Slivovsky. P3. Github, 2025. URL: https://github.com/fxreichl/p3.
  59. [59]Franz-Xaver Reichl and Friedrich Slivovsky. Pedant: A certifying DQBF solver. In SAT 2022: 25th International Conference on Theory and Applications of Satisfiability Testing, volume 236 of LIPIcs, pages 201–210. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.20.
  60. [60]Agnes Schleitzer and Olaf Beyersdorff. Classes of hard formulas for qbf resolution. Journal of Artificial Intelligence Research, 77:1455–1487, 2023. doi:10.1613/jair.1.14710.DOI
  61. [61]Agnes Schleitzer and Olaf Beyersdorff. Computationally hard problems are hard for qbf proof systems too. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 11336–11344, 2025. doi:10.1609/aaai.v39i11.33233.
  62. [62]Agnes Schleitzer and Olaf Beyersdorff. Crafted instance generator. Github, 2026. URL: https://github.com/AgnesSchubert/qbffamExt.
  63. [63]Ankit Shukla, Armin Biere, Luca Pulina, and Martina Seidl. A survey on applications of quantified boolean formulas. In ICTAI 2019: 31st IEEE International Conference on Tools with Artificial Intelligence, pages 78–84. IEEE, 2019. doi:10.1109/ICTAI.2019.00020.DOI
  64. [64]Juraj Šíć and Jan Strejcek. DQBDD: an efficient bdd-based DQBF solver. In SAT 2021: 24th International Conference on Theory and Applications of Satisfiability Testing, volume 12831 of Lecture Notes in Computer Science, pages 535–544. Springer, 2021. doi:10.1007/978-3-030-80223-3\_36.DOI
  65. [65]Friedrich Slivovsky. Miniqu. Github, 2024. URL: https://github.com/fslivovsky/miniQU.
  66. [66]Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pages 1–9. ACM, 1973. doi:10.1145/800125.804029.DOI
  67. [67]Chico Sundermann, Kevin Feichtinger, Dominik Engelhardt, Rick Rabiser, and Thomas Thüm. Yet another textual variability language? a community effort towards a unified language. In SPLC 2021: Proceedings of the 25th ACM International Systems and Software Product Line Conference – Volume A, page 136–147. Association for Computing Machinery, 2021. doi:10.1145/3461001.3471145.
  68. [68]Leander Tentrup. Non-prenex QBF solving using abstraction. In International Conference on Theory and Applications of Satisfiability Testing, pages 393–401. Springer, 2016. doi:10.1007/978-3-319-40970-2_24.DOI
  69. [69]Grigorii S Tseitin. On the complexity of derivation in propositional calculus. In Automation of reasoning: 2: Classical papers on computational logic 1967–1970, pages 466–483. Springer, 1983. doi:10.1007/978-3-642-81955-1_28.DOI
  70. [70]Benjie Wang, Denis Deratani Mauá, Guy Van den Broeck, and YooJung Choi. A compositional atlas for algebraic circuits. In Advances in Neural Information Processing Systems, volume 37, pages 141318–141355. Curran Associates, Inc., 2024. doi:10.52202/079017–4488.arxiv.org/abs/2412.05481
  71. [71]Wei Wei, Jordan Eenrich, and Bart Selman. Towards efficient sampling: Exploiting random walk strategies. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, pages 670–676. AAAI Press / The MIT Press, 2004. URL: http://www.aaai.org/Library/AAAI/2004/aaai04-106.php.
  72. [72]Ralf Wimmer, Sven Reimer, Paolo Marin, and Bernd Becker. HQSpre - an effective preprocessor for QBF and DQBF. In TACAS 2017: 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 10205 of Lecture Notes in Computer Science, pages 373–390, 2017. doi:10.1007/978-3-662-54577-5\_21.

Paper details

vlnc:W_pjg4hvek
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents