Strong (D)QBF Dependency Schemes via Pure Paths with Applications to Proof Checking

Leroy Chew, Tomáš Peitl · 2026

Read Strong (D)QBF Dependency Schemes via Pure Paths with Applications to Proof Checking by Leroy Chew, Tomáš Peitl (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29763.txt.

Introduction

Leroy Chew and Tomáš Peitl advance certification for quantified Boolean formulas and their dependency variant. Most techniques here can be mimicked by the independent extension rule, yet modern proof checkers lean on a broader RAT rule that (D)QBF formats have not matched. The team introduces Dpure, a new dependency scheme that, added to Blinkhorn's DQRAT system, makes it provably as strong as Independent Extended QU-Res. They also build a prototype checker carrying the new rule and show Dpure fits cleanly into the dependency-learning solver Qute.

Catalog record

CREATORLeroy Chew, Tomáš Peitl
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107728
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29763

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strong (D)QBF Dependency Schemes via Pure Paths with Applications to Proof Checking Leroy Chew, Tomáš Peitl Abstract Certification for Quantified Boolean Formulas (QBF) and Dependency Quantified Boolean Formulas (DQBF) is an ongoing challenge. Recent proof complexity work has shown that the majority of QBF and DQBF techniques can be p-simulated by using the independent extension rule. In propositional logic, extension rules are supported by proof checkers using a more general RAT (Resolution Asymmetric Tautology) rule. The next step in (D)QBF certification would be to update these modern RAT formats to match the strength of this independent extension rule. In this paper we first introduce a new dependency scheme called 𝒟 ∀ pure \mathcal{D}^{\mbox{\scriptsize$\forall$pure}} . This rule is the missing ingredient that when added to Blinkhorn’s proof system DQRAT allows it to be provably p-equivalent to the Independent Extended QU-Res, the most powerful of the known QBF and DQBF proof systems. Up until now, DQRAT has only existed in theory, so we implement a prototype checker DQRAT-check which includes our extra rule. In addition to its inclusion in our proof checker we show 𝒟 ∀ pure \mathcal{D}^{\mbox{\scriptsize$\forall$pure}} has other properties that have been found for previous dependency schemes, and each of these observations has potential in solving/checking including the sound integration into the dependency learning solver Qute . Czech Technical University in Prague, Prague, Czech Republic and https://leroychew.wordpress.com/ [email protected]://orcid.org/0000-0003-0226-2832This project is supported by FWF ESPRIT grant number ESP-197, by the European Union under the project ROBOPROX (reg. no. CZ.02.01.01/00/22_008/0004590) and by the Czech Science Foundation project 24-12759S TU Wien, Vienna, Austria and https://ac.tuwien.ac.at/people/peitl [email protected]://orcid.org/0000-0001-7799-1568 Thanks to Martina Seidl for discussions on this topic, to Mirek Olsak and Zarathustra Goertzel for help debugging DQRAT-check and to the anonymous reviewers for improvements to the paper. ccs Theory of computation Proof Complexity keywords DQBF, QBF, Qute, Proof Systems, Dependency Schemes, Dependency Learning, Skolem functions † † runningauthor: Leroy Chew, Tomáš Peitl † † copyright: Leroy Nicholas Chew, Tomáš Peitl † † supplement: https://doi.org/10.5281/zenodo.20203771 † † runningtitle: Strong (D)QBF Dependency Schemes via Pure Paths † † editors: Alexey Ignatiev and Stefan Szeider † † event-title: 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026) † † event-shorttitle: SAT 2026 † † event-acronym: SAT † † year: 2026 † † event-date: July 20–23, 2026 † † event-location: Lisbon, Portugal † † series-volume: 377 † † articleno: 11 1 Introduction Our main motivation comes from the recent introduction of a new proof rule known as independent extension [ 19 ] , which has desirable certification properties. The central observation of this paper is that we can readily simulate independent extension, with only a quick “fix” of existing certification rules. The fix is a sound relaxation of the order of quantification and also works with solvers. In this paper we explore how, why and to what extent this works, before implementing it in a proof checker. 1.1 Background The canonical \mathsf{NP} -complete problem is propositional satisfiability (SAT), and if we extend it with a prefix of Boolean quantifiers we get the Quantified Boolean Formula (QBF) problem which is then considered the canonical \mathsf{PSPACE} -complete problem. We can extend QBF even further into Dependency QBF (DQBF), where Boolean quantification still occurs, but the quantification order is not dictated by a linear prefix. Instead, every existentially quantified variable is given an explicit set of variables that it comes ‘after’. DQBF is considered a more expressive language than QBF as it is \mathsf{NEXPTIME} -complete rather than in \mathsf{PSPACE} . While research into DQBF is studied for its own sake, we are very interested where DQBFs appear in QBF research, because making changes to the quantification order in a QBF can make a QBF easier to solve or prove. Occasionally such changes require us to shift to a non-linear quantifier prefix. One common example is when solvers and proof systems employ dependency schemes , which calculate whether a dependency of one quantified variable to another is necessary or spurious. We can think of this as a transformation from a QBF to a DQBF as the prefix is recalculated to remove spurious dependencies. An example of well-studied dependency is the reflexive resolution path dependency scheme denoted by the symbol \mathcal{D}^{\mbox{\scriptsize rrs}} . This detects that a dependency is spurious if there is no sufficient pair of resolution paths (see Section 2 for the definition of a resolution path) from \forall to \exists literals. The use of a whole range of transformations from QBF to DQBF, which is often done only implicitly, has made deciding a commonly agreed upon QBF proof format more challenging. Theoretical proof systems such as the sequent calculus \mathsf{G} [ 33 ] (named after Gentzen who pioneered sequent calculi) assume a neat symmetry between true and false as QBF is closed under negation and \mathsf{PSPACE} is self-complementary, but DQBF is not alike in this way and has an inherent asymmetry between \exists and \forall . In addition, theoretical proof systems make poor checking formats in a practical setting because they do not generalise existing practical formats and often proofs with polynomial size upper bounds are still too large in practice. One noteworthy QBF format that attempts to tackle this issue is QRAT (Quantified Resolution Asymmetric Tautology) [ 25 ] . In addition to generalising the rules of the propositional proof system DRAT (Deletion Resolution Asymmetric Tautology), which is the closest system propositional logic has to a standard format, QRAT can detect the same side conditions that a dependency scheme detects. Instead of modifying the quantifier prefix, QRAT modifies a clause. Such a combination of rules ends up being incredibly powerful and QRAT can p-simulate a majority of the solving and preprocessing techniques in QBF, despite the large disparity of these techniques. This is incredibly fortunate overall, but it is not directly possible in QRAT to treat a QBF with a dependency scheme as a DQBF, as we soundly ought to be able to do. In fact, QRAT has been proven on a theoretical level to be no stronger than \mathsf{G} [ 18 ] , so even its detection of dependency schemes is no more than a sufficient combination of fundamental QBF steps. In an attempt to build QRAT into a genuine DQBF proof system, Blinkhorn proposed [ 15 ] the DQBF proof system DQRAT (Dependency Quantified Resolution Asymmetric Tautology) and DQRAT can handle dependency schemes directly. However, DQRAT has not been developed since its initial introduction, nor is there a substantial body of proof complexity follow up work that discusses it. Nonetheless, work into strong DQBF proof systems may yet be fruitful. Recent developments in QBF proof complexity have shown that a new DQBF proof system \mathsf{IndExtQU\mathsf{Res}} (where the power comes from an Independent Extension rule) can p-simulate practically everything in QBF and DQBF including \mathsf{G} , QRAT , DQRAT and some dependency scheme rules such as \mathcal{D}^{\mbox{\scriptsize rrs}} [ 19 ] . \mathsf{IndExtQU\mathsf{Res}} is not yet a practical format, and the proposed next step in the paper by Chew and Peitl introducing \mathsf{IndExtQU\mathsf{Res}} was to find a RAT version which was p-equivalent or more powerful. In this paper we create a DQRAT proof checker and we add one additional rule to it. We demonstrate theoretically that

Read the complete text