Better Extension Variables in DQBF via Independence
Leroy Chew, Tomáš Peitl · 2025
Read Better Extension Variables in DQBF via Independence by Leroy Chew, Tomáš Peitl (2025) 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-2505-20069.txt.
Introduction
Leroy Chew and Tomáš Peitl strengthen a proof method for quantified Boolean formulas, the logic of true-false claims with for-all and there-exists layers. Solvers add helper variables to shorten proofs, but old rules limit how small their dependency sets can be. The authors let helpers depend on universal choices, which shrinks those sets.
The tweak lets one proof system mimic six hard rival systems step by step. Those rivals cover most known solving and preprocessing tricks for this logic family. The result is notable because the new rule is simple, yet it matches methods built from far more complex rules.
Catalog record
| CREATOR | Leroy Chew, Tomáš Peitl |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20069
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Better Extension Variables in DQBF via Independence Leroy Chew, Tomáš Peitl Abstract We show that extension variables in (D)QBF can be generalised by conditioning on universal assignments. The benefit of this is that the dependency sets of such conditioned extension variables can be made smaller to allow easier refutations. This simple modification instantly solves many challenges in p-simulating the QBF expansion rule, which cannot be p-simulated in proof systems that have strategy extraction [ 7 ] . Simulating expansion is even more crucial in DQBF, where other methods are incomplete. In this paper we provide an overview of the strength of this new independent extension rule. We find that a new version of Extended Frege called 𝖨𝗇𝖽𝖤𝗑𝗍𝖥𝗋𝖾𝗀𝖾 \mathsf{IndExt\mathsf{Frege}} + ∀ 𝗋𝖾𝖽 \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} can p-simulate a multitude of difficult QBF and DQBF techniques, even techniques that are difficult to approach with 𝖾𝖥𝗋𝖾𝗀𝖾 \mathsf{e\mathsf{Frege}} + ∀ 𝗋𝖾𝖽 \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} . We show six p-simulations, that 𝖨𝗇𝖽𝖤𝗑𝗍𝖥𝗋𝖾𝗀𝖾 \mathsf{IndExt\mathsf{Frege}} + ∀ 𝗋𝖾𝖽 \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} p-simulates QRAT, DQBF-IR-calc , IR( 𝒟 rrs \mathcal{D}^{\mbox{\scriptsize rrs}} )-calc , Fork-Resolution, DQRAT and 𝖦 \mathsf{G} which together underpin most DQBF solving and preprocessing techniques. The p-simulations work despite these systems using complicated rules and our new extension rule being relatively simple. Moreover, unlike recent p-simulations by 𝖾𝖥𝗋𝖾𝗀𝖾 \mathsf{e\mathsf{Frege}} + ∀ 𝗋𝖾𝖽 \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} we can simulate the proof rules line by line, which allows us to mix QBF rules more easily with other inference steps. 1 Introduction Proof systems that allow extension variables are very powerful [ 10 ] . We know that in propositional logic, extended resolution can p-simulate a multitude of disparate techniques, and lower bounds to extended resolution remain an open problem. This is remarkable because resolution itself is a weak proof system with various lower bounds, but simply adding the extension rule upgrades it to be amongst the most powerful propositional proof systems and is equivalent to the checking format DRAT [ 22 ] . An extension rule for variable v takes the form: v\leftrightarrow b(X):b\text{ is a Boolean function, }X\text{ is a set of existing variables} Quantified Boolean Formulas (QBF) also use extension variables [ 12 ] and these too can be very powerful. QBFs list all variables in a quantifier prefix. This defines whether a variable is existential ( \exists ) or universal ( \forall) . The order defines dependencies so variables only depend on other variables to their left. When used in refutations, extension variables must be existential, otherwise it is too easy to violate extension clauses. The dependency set of the new variables (which is the same as the quantification order in QBF) must be careful not to introduce falsity into the formula. In fact one of the earliest approaches was to say that every new variable is quantified rightmost to conservatively give it the entire dependency set. The drawback with this approach is that it limits the power of inferences from using extension variables [ 4 ] . In the current alternative, sometimes known as “strong extension”, we place \exists v immediately after all the variables X used in b . \mathsf{e\mathsf{Frege}} \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} uses this strong notion, and it is so powerful no unconditional lower bound can be found, unless either a long standing proof complexity or circuit complexity open problem is solved [ 3 ] . Some problems do emerge when looking at conditional lower bounds, though. The \select family of formulas can be shown by the QBF proof system QRAT to be equivalent to the law of non-contradiction on QBFs, but do not have short proofs in QBF Extended Frege unless \mathsf{PSPACE}\subseteq\mathsf{P/poly} [ 7 ] . QRAT manages this through a combination of extension variables and an explicit rule that calculates so-called spurious dependencies in quantified variables, when nominal dependencies can be ignored when making inferences. Note how different this is to propositional logic, in most cases where we would take a basic proof system and add even a complicated rule we would still be simulated by extended resolution. Based on our observations in this paper we find that we can do better with extension variables. Instead of extensions being pure definitions, they are now under conditions. \alpha\rightarrow(v\leftrightarrow b(X)):\alpha\text{ is a partial assignment of the universal variables} The utility of this is not immediately obvious because v is weaker than it could be, however precisely because this is weaker now the dependency of v on the variables of \alpha is no longer necessary for soundness. Because we can remove arbitrary dependencies the natural class for this proof system is for Dependency QBF (DQBF). But we can still use this rule for QBF, in fact it adds substantial clarity to existing QBF proof systems. Our main contribution is that we propose a line based proof system, that each new line addition preserves satisfiability, so when arriving at the falsum symbol 0 we know we started with an unsatisfiable DQBF. Unlike many QBF systems we are not able to construct countermodels from following the proof steps (unless \mathsf{P}=\mathsf{PSPACE} ). We then show how it can p-simulate existing QBF and DQBF proof system rules. Figure 1 shows the known p-simulations in QBF proof systems after considering the work in this paper. \mathsf{IndExt\mathsf{Frege}} \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} \mathsf{G} G 1 G {}^{*}_{1} QRAT \mathsf{e\mathsf{Frege}} \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} Frege + \forall Exp IR( \mathcal{D}^{\mbox{\scriptsize rrs}} )-calc \mathsf{Frege} \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} \mathsf{AC}_{0} \mathsf{Frege} \,\raisebox{0.86108pt}{$\scriptstyle+$}\,\boldsymbol{\forall}\kern 0.17218pt\mathsf{red} LD-Q-Res \setminus\{\boldsymbol{\forall}\kern 0.17218pt\mathsf{red}\} M-Res QU-Res Q-Res LD-Q-Res LQU- Res LQU + - Res Q( \mathcal{D}^{\mbox{\scriptsize std}} )-Res Q( \mathcal{D}^{\mbox{\scriptsize rrs}} )-Res LD-Q( \mathcal{D}^{\mbox{\scriptsize rrs}} )-Res QCDCL \forall Exp+Res IR-calc IRM-calc Known Strategy Extraction Figure 1: The p-simulation structure of refutational QBF proof systems 1.1 Related Work The original Extended Q-Resolution was defined by Jussila et al. [ 12 ] and discussed the weak and strong extension variables. QRAT by Biere, Heule and Seidl generalises extension variables in its clause additions. In the original paper [ 11 ] and later in Kiesl and Seidl’s paper [ 15 ] , they use similar clause additions to our independent extension definitions. Unlike our definitions, the new variables have a larger dependency set, but get round this by detecting spurious dependencies with an Extended Universal Reduction rule (EUR). These QRAT extension variables can capture the annotated variables used in the QBF proof system \forall\textsf{Exp+Res} , but there has not been success making the same method work for the more general QBF proof system IR-calc [ 6 ] . Our approach works backwards, instead of using the presence of resolution path schemes to derive expansions, we use expansions to show the validity of resolution path schemes. Blinkhorn proposed a DQBF proof system based on generalising the QBF proof system QRAT to DQBF [ 5 ] . This system too allows the addition of new variables v , but when using the RAT addition rules to make definition clauses the RAT addition rule only allows the variables in the dependency set of v to be used unlike in our case. Therefore we suspect their proof system is weaker. Rabe proposed DQBF proof system called Fork-Resolution that proposed extension variables but only in the case of clause-splitting [ 18 ] . Chew and Clymo showed the QRAT’s strongest rule