betaFeedback

WorksComputer Science

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

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 CAQECore^{\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 CAQECore^{\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 CAQECore^{\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 CAQECore^{\mathsf{Core}} on QCNFs of bounded quantifier alternation. The same holds for QCDCL (Quantified Conflict-Driven Clause Learning, formalised as a proof system) on Σ3bΣ_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 CAQECore^{\mathsf{Core}}, where the separation of QCDCL from CAQECore^{\mathsf{Core}} uses cube learning.

2012 ACM Subject Classification Theory of computation → Proof complexity

Keywords and phrases QBF, CAQE, CDCL, resolution, proof complexity, simulations, lower bounds

Related Version Conference Version: https://doi.org/10.4230/LIPIcs.SAT.2026.7 [17]

Funding Olaf Beyersdorff: Carl-Zeiss Foundation and DFG grant BE 4209/3-2

Acknowledgements We thank Leroy Chew for asking a question at SAT’25 on the proof-theoretic strength of CAQE, which led to this work. We used a large language model (Claude) as a writing assistant for this article; all results and proofs were checked by the authors.

Introduction

Quantified Boolean Formulas (QBF) extend the satisfiability problem (SAT) by quantification over Boolean variables. This increases the complexity of the problem (from NP to PSPACE), the versatility of expressions (many problems are more succinctly and more naturally encoded into QBF), and the range of applications [37].

Different from SAT, where conflict-driven clause learning (CDCL) is the ruling algorithmic paradigm, there are a number of competing approaches to QBF solving. Quantified conflict-driven clause learning (QCDCL) lifts the CDCL paradigm [29] to QBF [41, 14]. QCDCL can be further enhanced by dependency schemes [31] and dependency learning [30] and is implemented in a number of QBF solvers (Qute [32], DepQBF [28]). A second approach comes through expansion of universal variables in the counter-example guided abstraction refinement (CEGAR) framework, implemented in RAREQS [25, 26]. CAQE (Clausal Abstraction for Quantifier Elimination) is a third algorithmic paradigm, introduced in 2015 [35, 39] and implemented in the eponymous solver. CAQE also utilises CEGAR, but in a fundamentally different way compared to expansion.

With these various and seemingly orthogonal approaches, it is stunning that since 2017 versions of CAQE have won each QBF evaluation in the prenex CNF track, sometimes by quite a big margin [33, 34]. Experimental evaluations of different solvers as in QBF evaluations are an impactful driver for algorithmic progress. A systematic and theoretically concise comparison of different algorithmic solving techniques – in SAT, QBF and further fields – comes through proof complexity [20, 14, 13]. Proof complexity of QBF has been hugely advanced over the past decade (cf. [3] for a survey) and many theoretically clean and appealing QBF proof systems have been introduced together with proof methods to analyse them (e.g. [9, 6, 5, 11, 10, 2]).

When aiming to compare different solvers, we need proof systems tightly modelling solvers and such proof systems are typically quite different from rule-based calculi such as resolution [27, 40, 23], Frege or strong systems for proof logging [9, 24, 21]. A rigorous study of this kind has been performed on different versions of QCDCL and their relations to QBF resolution systems, unearthing surprising incomparability results – e.g. between standard QCDCL and Q-resolution [7] – as well as identifying potential improvements for solving (e.g. out-of-order decisions [16, 19] or cube learning and pure literal elimination [18]).

Such a tight theoretical model and comparison to other QBF solvers and proof systems is largely missing for the award-winning solver CAQE. An investigation into the proof-theoretic strength of CAQE was started in the paper [38], focusing on the comparison between CAQE and other CEGAR approaches such as RAREQ§, and establishing their incomparability. However, the relation to QCDCL – arguably the other main QBF solving approach – has been open for the past decade.

Our results. We provide a theoretical proof-complexity analysis of the core procedure of CAQE and compare it to QCDCL and Q-Resolution, resulting in the situation depicted in Figure 1. We do not consider potential optimisations of CAQE such as failed assumptions – we plan to address those in future work.

(a) As a first step, we tightly model the basic algorithmic paradigm of CAQE (without failed assumptions) as introduced in [35] as a proof system CAQECore^{\mathrm{Core}} such that runs of the basic CAQE algorithm can be translated into CAQECore^{\mathrm{Core}} proofs and conversely, each tree-like proof gives rise to a run of the basic algorithm (Theorem 11). We note that a proof system ∀Red+Res\forall\mathrm{Red}+\mathrm{Res} was introduced in [38] that likewise allows one to translate runs of the basic algorithm of CAQE into ∀Red+Res\forall\mathrm{Red}+\mathrm{Res}, but the converse direction fails (Theorem 16 and Theorem 34).

(b) In our main result we compare the core procedure of CAQE to QCDCL and show the possibly surprising result that QCDCL simulates this basic version of CAQE on Σ3b\Sigma^{b}_{3} QCNFs (Corollary 51). This holds after a simple preprocessing step, which makes the formulas fulfil the XTXT-property, and in a model where purely propositional CDCL steps are not counted (see below). Furthermore, we show that QCDCL with cube learning is exponentially stronger on selected formulas (Theorem 40). Our theoretical comparison utilises our new CAQECore\mathrm{CAQE}^{\mathrm{Core}} proof system and the QCDCL proof systems developed in [18, 7].

As CAQE uses a massive number of SAT calls, we believe that conceptually the fairest comparison is by discounting SAT computations. This approach aligns with large parts of the QBF literature where propositional hardness is filtered out by allowing NP oracles in proofs [12] (whereby lower bounds measure “genuine” QBF hardness and become more challenging). For CAQECore\mathrm{CAQE}^{\mathrm{Core}} this is fairly simple: we just count a SAT call as one step, whereas for QCDCL this is somewhat more intricate as QCDCL does not use SAT calls, but has all CDCL functionality “built in”. We therefore define a QCDCL model where purely propositional parts of the traces are not counted (imagine, e.g. that QCDCL stumbles upon a hard propositional formula not containing any universal variables).

Further, we show that our proof system CAQECore\mathrm{CAQE}^{\mathrm{Core}} is simulated by Q-Resolution (Corollary 39), again in the oracle model and on bounded quantifier alternation. While ∀Red+Res\forall\mathrm{Red}+\mathrm{Res} is known to be simulated by Q-Resolution [38], this result does not discount SAT calls, which means that it does not imply our stronger simulation. Q-Resolution is a weak system and in particular known to be incomparable to QCDCL [18, 7, 15].

Conceptually, the simulation order in Figure 1 means that, from a proof-complexity perspective and in the oracle setting described above, the core procedure of CAQE without failed assumptions is weaker than Q-Resolution on QCNFs of bounded quantifier alternation and weaker than QCDCL on Σ3b\Sigma^{b}_{3} QCNFs. Hence its practical outperformance appears to result from its clever and heavy SAT usage (cf. also the discussion in Section 9) as well as from optimisations such as failed assumptions and the reuse of refinement clauses across different calls (cf. the discussion after Theorem 11) – which we did not consider in this work.

!Hasse diagram showing QCDCL, Q-Res and CAQECore^{\mathrm{Core}}; QCDCL and Q-Res are incomparable [18, 7, 15]; both simulate CAQECore^{\mathrm{Core}} with exponential separation bbox=0.25,0.10,0.78,0.25

Figure 1. Hasse diagram of the simulation order of QCDCL, Q-Res and CAQECore^{\mathrm{Core}} (stronger systems on top). Solid lines denote a simulation together with an exponential separation. Both simulations hold in the oracle model of this paper: for Q-Res with an NP oracle (QNP^{\mathrm{NP}}-Res) on QCNFs of bounded quantifier alternation, and for QCDCL on Σ3b\Sigma^{b}_{3} QCNFs when purely propositional CDCL steps are not counted (and after a preprocessing step that establishes the XT-property); the separation of QCDCL from CAQECore^{\mathrm{Core}} uses cube learning. The dashed line indicates the known mutual exponential separations of QCDCL and Q-Res in the standard (non-oracle) setting.

Technically, we achieve our results by a characterisation of CAQECore\mathrm{CAQE}^{\mathrm{Core}} proof size by a measure we call CAQECAQE width, which yields lower as well as upper bounds on CAQECore\mathrm{CAQE}^{\mathrm{Core}} proof size (Theorem 29, Proposition 32). This characterisation gives rise to exponential lower bounds and the separations as well as to the extraction of short decision lists (Theorem 37) and consequently the simulations.

Relation to the conference version. A preliminary version of this article appeared in the proceedings of SAT 2026 [17]. The present article contains complete proofs of all results, most of which were only sketched or omitted in the conference version. In the course of this, we have also corrected some errors and inaccuracies of the conference version.

Organisation. After setting up notation in Section 2 we explain the basic CAQE algorithm in Section 3 and formalise it as a proof system CAQECore\mathrm{CAQE}^{\mathrm{Core}} in Section 4. In Section 5 we show that CAQECore\mathrm{CAQE}^{\mathrm{Core}} is sound and allows extraction of winning strategies. Section 6 introduces our main technical tool: CAQE width that we use to obtain lower and upper bounds and to prove the completeness of CAQECore\mathrm{CAQE}^{\mathrm{Core}}. In Section 7 we show that decision lists for winning strategies can be extracted from CAQECore\mathrm{CAQE}^{\mathrm{Core}} proofs, yielding the simulation of CAQECore\mathrm{CAQE}^{\mathrm{Core}} by QNP-Res\mathrm{Q}^{\mathrm{NP}}\text{-Res}. § 8 compares CAQECore\mathrm{CAQE}^{\mathrm{Core}} and QCDCL. We conclude with a discussion in § 9.

Preliminaries

Variables xx and negated variables xˉ\bar{x} are called literals. We denote the corresponding variable as var⁡(x):=var⁡(xˉ):=x\operatorname{var}(x) := \operatorname{var}(\bar{x}) := x. A clause is a disjunction of literals. A unit clause (ℓ)(\ell) is a clause consisting of only one literal. The empty clause (⊥)(\bot) has zero literals. A cube is a conjunction of literals, sometimes viewed as a set of literals. We define a unit cube of a literal ℓ\ell, denoted by [ℓ][\ell], and the empty cube [⊤][\top] with “empty literal” ⊤\top. If CC is a clause or a cube, we define var⁡(C):={var⁡(ℓ):ℓ∈C}\operatorname{var}(C) := \{\operatorname{var}(\ell) : \ell\in C\}.

An assignment σ\sigma of a set of variables VV is a function σ:V→{0,1}\sigma: V \to\{0,1\}, which can also be interpreted as the set {ℓ:var⁡(ℓ)∈V∧σ(ℓ)=1}\{\ell: \operatorname{var}(\ell) \in V \land\sigma(\ell) = 1\}. We denote the set of all assignments of VV as ⟨V⟩\langle V\rangle. For a cube DD we write ¬D\neg D for the clause that consists of the negations of the literals of DD. A clause CC is satisfied by σ\sigma if C∩σ≠∅C \cap\sigma\ne\varnothing. A cube DD is satisfied by σ\sigma if D⊆σD \subseteq\sigma, and it is falsified by σ\sigma if ¬D∩σ≠∅\neg D \cap\sigma\ne\varnothing. A clause CC that is not satisfied by σ\sigma can be restricted by σ\sigma, defined as C∣σ:=⋁ℓ∈C,ℓˉ∉σℓC|_{\sigma} := \bigvee_{\ell\in C,\bar{\ell} \notin\sigma} \ell. Similarly we can restrict a non-falsified cube DD as D∣σ:=⋀ℓ∈D∖σℓD|_{\sigma} := \bigwedge_{\ell\in D \setminus\sigma} \ell. We can restrict a clause CC to a set of variables VV by C∣V:=⋁ℓ∈C,var⁡(ℓ)∈VℓC|_{V} := \bigvee_{\ell\in C,\operatorname{var}(\ell) \in V} \ell. We can restrict a cube DD to a set of variables VV by D∣V:=⋀ℓ∈D,var⁡(ℓ)∈VℓD|_{V} := \bigwedge_{\ell\in D,\operatorname{var}(\ell) \in V} \ell. Note the difference between the restriction C∣σC|_{\sigma} by an assignment and the restriction C∣VC|_{V} to a set of variables – it will always be clear from the context which one is meant.

A CNF\mathrm{CNF} (conjunctive normal form) is a conjunction of clauses and a DNF\mathrm{DNF} (disjunctive normal form) is a disjunction of cubes. A CNF\mathrm{CNF} (DNF\mathrm{DNF}) is satisfied (falsified) by σ\sigma if all its clauses (cubes) are satisfied (falsified) by σ\sigma.

We use the notation σ⊨ψ\sigma\models\psi for a propositional formula ψ\psi and assignment σ\sigma if σ\sigma satisfies ψ\psi. We write φ⊨ψ\varphi\models\psi for propositional formulas φ\varphi and ψ\psi if each satisfying assignment of φ\varphi satisfies ψ\psi.

A QBF\mathrm{QBF} (quantified Boolean formula) Φ=Q⋅φ\Phi= Q \cdot\varphi consists of a propositional formula φ\varphi, called the matrix, and a prefix QQ. A prefix Q=Q1V1…QdVdQ = Q_1V_1 \dots Q_dV_d consists of non-empty and pairwise disjoint sets of variables V1,…,VdV_1,\ldots,V_d (the quantifier blocks) and quantifiers Q1,…,Qd∈{∃,∀}Q_1,\ldots,Q_d \in\{\exists,\forall\} with Qi≠Qi+1Q_i \ne Q_{i+1} for i<di < d. A QBF is propositional if its prefix is empty or consists of a single existential block. In this case, the QBF is true if and only if its matrix is satisfiable, and we identify the QBF with its matrix.

A QCNF\mathrm{QCNF} is a QBF Φ=Q⋅φ\Phi= Q \cdot\varphi with CNF\mathrm{CNF} φ\varphi. We define var⁡(Φ):=⋃C∈Φvar⁡(C)\operatorname{var}(\Phi) := \bigcup_{C \in\Phi} \operatorname{var}(C). We often identify a CNF\mathrm{CNF} with the set of its clauses and write φ⊆ψ\varphi\subseteq\psi if every clause of φ\varphi is a clause of ψ\psi. Analogously, for QCNFs\mathrm{QCNFs} Φ=Q⋅φ\Phi= Q \cdot\varphi and Ψ=Q′⋅ψ\Psi= Q' \cdot\psi with the same prefix we write Φ⊆Ψ\Phi\subseteq\Psi if φ⊆ψ\varphi\subseteq\psi. We restrict a CNF\mathrm{CNF} φ\varphi by an assignment σ\sigma as φ∣σ:=⋀C∈φ non-satisfiedC∣σ\varphi|_{\sigma} := \bigwedge_{C \in\varphi\text{ non-satisfied}} C|_{\sigma} and a QCNF\mathrm{QCNF} Φ=Q⋅φ\Phi= Q \cdot\varphi as Φ∣σ:=Q∣σ⋅φ∣σ\Phi|_{\sigma} := Q|_{\sigma} \cdot\varphi|_{\sigma}, where Q∣σQ|_{\sigma} is obtained by deleting all variables from QQ that appear in σ\sigma. Note that variables that no longer occur in φ∣σ\varphi|_{\sigma} remain in the prefix – such variables are simply irrelevant for the truth value. Hence, restricting a QCNF\mathrm{QCNF} by an assignment of a proper subset of its first block never deletes a quantifier block.

Throughout the paper we assume that the prefix of a QCNF\mathrm{QCNF} ends with an existential block. This is no restriction, because the literals of a universal block at the end of the prefix can be removed from all clauses without changing the truth value (this is the universal reduction rule recalled below), after which the block can be dropped. Hence, we usually write the prefix of a QCNF\mathrm{QCNF} as ∀U0∃X1∀U1…∃Xm∀Um∃Xm+1\forall U_0\exists X_1\forall U_1 \ldots\exists X_m\forall U_m\exists X_{m+1}, where only the block U0U_0 is allowed to be empty. In this notation, mm is the number of universal blocks that are preceded by an existential block, that is, the number of alternations from ∃\exists to ∀\forall.

References

  1. [1]Valeriy Balabanov and Jie-Hong R. Jiang. Unified QBF certification and its applications. Form. Methods Syst. Des., 41(1):45–65, 2012.DOI
  2. [2]Valeriy Balabanov, Magdalena Widl, and Jie-Hong R. Jiang. QBF resolution systems and their proof complexities. In Proc. Theory and Applications of Satisfiability Testing (SAT), pages 154–169, 2014.DOI
  3. [3]Olaf Beyersdorff. Proof of complexity of quantified Boolean logic – a survey. In Marco Benini, Olaf Beyersdorff, Michael Rathjen, and Peter Schuster, editors, Mathematics for Computation (M4C), pages 353–391. World Scientific, Singapore, 2022.DOI
  4. [4]Olaf Beyersdorff, Joshua Blinkhorn, and Luke Hinde. Size, cost, and capacity: A semantic technique for hard random QBFs. Logical Methods in Computer Science, 15(1), 2019.
  5. [5]Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, and Tomáš Peitl. Hardness characterisations and size-width lower bounds for QBF resolution. ACM Trans. Comput. Log., 24(2):10:1–10:30, 2023.
  6. [6]Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, and Gaurav Sood. Hard QBFs for merge resolution. ACM Trans. Comput. Theory, 16(2):6:1–6:24, 2024.
  7. [7]Olaf Beyersdorff and Benjamin Böhm. Understanding the relative strength of QBF CDCL solvers and QBF resolution. Log. Methods Comput. Sci., 19(2), 2023.DOI
  8. [8]Olaf Beyersdorff, Benjamin Böhm, and Meena Mahajan. Runtime vs. extracted proof size: An exponential gap for CDCL on QBFs. J. Autom. Reason., 69(4):30, 2025.
  9. [9]Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, and Jan Pich. Frege systems for quantified Boolean logic. J. ACM, 67(2):9:1–9:36, 2020.DOI
  10. [10]Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, and Luc Nicolas Spachmann. Semi-algebraic proof systems for QBF. In Jeremias Berg and Jakob Nordström, editors, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT), volume 341 of LIPIcs, pages 5:1–5:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.
  11. [11]Olaf Beyersdorff, Leroy Chew, and Mikoláš Janota. New resolution-based QBF calculi and their proof complexity. ACM Transactions on Computation Theory, 11(4):26:1–26:42, 2019.DOI
  12. [12]Olaf Beyersdorff, Luke Hinde, and Ján Pich. Reasons for hardness in QBF proof systems. ACM Transactions on Computation Theory, 12(2):10:1–10:27, 2020.DOI
  13. [13]Olaf Beyersdorff, Tim Hoffmann, and Luc Nicolas Spachmann. Proof complexity of propositional model counting. J. Satisf. Boolean Model. Comput., 15(1):27–59, 2024.DOI
  14. [14]Olaf Beyersdorff, Mikoláš Janota, Florian Lonsing, and Martina Seidl. Quantified Boolean formulas. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, pages 1177–1221. IOS Press, 2021.
  15. [15]Benjamin Böhm and Olaf Beyersdorff. Lower bounds for QCDCL via formula gauge. J. Autom. Reason., 67(4):35, 2023.
  16. [16]Benjamin Böhm and Olaf Beyersdorff. QCDCL vs QBF resolution: Further insights. J. Artif. Intell. Res., 81:741–769, 2024.DOI
  17. [17]Benjamin Böhm and Olaf Beyersdorff. Towards understanding the complexity of CAQE: A proof-theoretic analysis of its core procedure. In Alexey Ignatiev and Stefan Szeider, editors, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT), volume 377 of LIPIcs, pages 7:1–7:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.SAT.2026.7.DOI
  18. [18]Benjamin Böhm, Tomáš Peitl, and Olaf Beyersdorff. QCDCL with cube learning or pure literal elimination - what is best? Artif. Intell., 336:104194, 2024.DOI
  19. [19]Benjamin Böhm, Tomáš Peitl, and Olaf Beyersdorff. Should decisions in QCDCL follow prefix order? J. Autom. Reason., 68(1):5, 2024.
  20. [20]Sam Buss and Jakob Nordström. Proof complexity and SAT solving. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, pages 233–350. IOS Press, 2021.
  21. [21]Leroy Chew and Marijn J. H. Heule. Relating existing powerful proof systems for QBF. In Kuldeep S. Meel and Ofer Strichman, editors, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT), volume 236 of LIPIcs, pages 10:1–10:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  22. [22]Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems. The Journal of Symbolic Logic, 44(1):36–50, 1979.DOI
  23. [23]Uwe Egly, Florian Lonsing, and Magdalena Widl. Long-distance resolution: Proof generation and strategy extraction in search-based QBF solving. In Proc. Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), pages 291–308, 2013.DOI
  24. [24]Marijn J. H. Heule, Martina Seidl, and Armin Biere. Solution validation and extraction for QBF preprocessing. J. Autom. Reason., 58(1):97–125, 2017.DOI
  25. [25]Mikoláš Janota, William Klieber, João Marques-Silva, and Edmund M. Clarke. Solving QBF with counterexample guided refinement. Artif. Intell., 234:1–25, 2016.
  26. [26]Mikoláš Janota and João Marques-Silva. Expansion-based QBF solving versus Q-resolution. Theor. Comput. Sci., 577:25–42, 2015.DOI
  27. [27]Hans Kleine Büning, Marek Karpinski, and Andreas Flögel. Resolution for quantified Boolean formulas. Inf. Comput., 117(1):12–18, 1995.DOI
  28. [28]Florian Lonsing and Uwe Egly. DepQBF 6.0: A search-based QBF solver beyond traditional QCDCL. In Proc. International Conference on Automated Deduction (CADE), pages 371–384, 2017.DOI
  29. [29]João P. Marques Silva, Inês Lynce, and Sharad Malik. Conflict-driven clause learning SAT solvers. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, volume 336 of Frontiers in Artificial Intelligence and Applications, pages 133–182. IOS Press, second edition, 2021.
  30. [30]Tomáš Peitl, Friedrich Slivovsky, and Stefan Szeider. Dependency learning for QBF. J. Artif. Intell. Res., 65:180–208, 2019.
  31. [31]Tomáš Peitl, Friedrich Slivovsky, and Stefan Szeider. Long-distance Q-resolution with dependency schemes. J. Autom. Reasoning, 63(1):127–155, 2019.
  32. [32]Tomáš Peitl, Friedrich Slivovsky, and Stefan Szeider. Qute in the QBF evaluation 2018. J. Satisf. Boolean Model. Comput., 11(1):261–272, 2019. doi:10.3233/SAT190124.DOI
  33. [33]Luca Paulina and Martina Seidl. The 2016 and 2017 QBF solvers evaluations (QBFEVAL’16 and QBFEVAL’17). Artif. Intell., 274:224–248, 2019.
  34. [34]QBF solver evaluation portal. https://www.qbflib.org/index_eval.php. Accessed November 2026.
  35. [35]Markus N. Rabe and Leander Tentrup. CAQE: A certifying QBF solver. In Roope Kaivola and Thomas Wahl, editors, Formal Methods in Computer-Aided Design (FMCAD), pages 136–143. IEEE, 2015.DOI
  36. [36]Ronald L. Rivest. Learning decision lists. Machine Learning, 2(3):229–246, 1987.DOI
  37. [37]Ankit Shukla, Armin Biere, Luca Pulina, and Martina Seidl. A survey on applications of quantified Boolean formulas. In Proc. IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pages 78–84, 2019.DOI
  38. [38]Leander Tentrup. On expansion and resolution in CEGAR based QBF solving. In Rupak Majumdar and Viktor Kuncak, editors, Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part II, volume 10427 of Lecture Notes in Computer Science, pages 475–494. Springer, 2017.arxiv.org/abs/1803.09559
  39. [39]Leander Tentrup. CAQE and QuAbS: Abstraction based QBF solvers. J. Satisf. Boolean Model. Comput., 11(1):155–210, 2019.DOI
  40. [40]Allen Van Gelder. Contributions to the theory of practical quantified Boolean formula solving. In Proc. Principles and Practice of Constraint Programming (CP), pages 647–663, 2012.DOI
  41. [41]Lintao Zhang and Sharad Malik. Conflict driven learning in a quantified Boolean satisfiability solver. In Proc. IEEE/ACM International Conference on Computer-aided Design (ICCAD), pages 442–449, 2002.

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

Claude

View statement
Looking for related papers…
Contents