d-QBF with Few Existential Variables Revisited

Andreas Grigorjew, Michael Lampis · 2026

Read d-QBF with Few Existential Variables Revisited by Andreas Grigorjew, Michael Lampis (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-2603-08826.txt.

Introduction

Andreas Grigorjew and Michael Lampis close a gap for quantified Boolean formulas with few existential variables. Eriksson's team had shown fixed-parameter tractability when clause arity is bounded, but left a double-exponential method against a weaker lower bound. Assuming ETH, the authors prove the double-exponential cost cannot be beaten even at arity four, while the two-block case admits a near-optimal method.

Catalog record

CREATORAndreas Grigorjew, Michael Lampis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47425
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

d-QBF with Few Existential Variables Revisited Andreas Grigorjew, Michael Lampis Abstract Quantified Boolean Formula (QBF) is a notoriously hard generalization of SAT , especially from the point of view of parameterized complexity, where the problem remains intractable for most standard parameters. A recent work by Eriksson et al. [IJCAI 24] addressed this by considering the case where the propositional part of the formula is in CNF and we parameterize by the number k k of existentially quantified variables. One of their main results was that this natural (but so far overlooked) parameter does lead to fixed-parameter tractability, if we also bound the maximum arity d d of the clauses of the given CNF. Unfortunately, their algorithm has a double-exponential dependence on k k ( 2 2 k 2^{2^{k}} ), even when d d is an absolute constant. Since the work of Eriksson et al. only complemented this with a SETH-based lower bound implying that a 2 O ⁡ ( k ) 2^{O(k)} dependence is impossible, this left a large gap as an open question. Our main result in this paper is to close this gap by showing that the double-exponential dependence is optimal, assuming the ETH: even for CNFs of arity 4 4 , QBF with k k existential variables cannot be solved in time 2 2 o ⁡ ( k ) ​ | φ | O ⁡ ( 1 ) 2^{2^{o(k)}}|\varphi|^{O(1)} . Complementing this, we also consider the further restricted case of QBF with only two quantifier blocks ( ∀ ∃ \forall\exists -QBF). We show that in this case the situation improves dramatically: for each d ≥ 3 d\geq 3 we show an algorithm with running time k O d ​ ( k d − 1 ) ​ | φ | O ⁡ ( 1 ) k^{O_{d}(k^{d-1})}|\varphi|^{O(1)} and a lower bound under the ETH showing our algorithm is almost optimal. LAMSADE, CNRS UMR7243, Université Paris Dauphine-PSL, 75775 Paris, France [email protected] https://orcid.org/0000-0003-0989-2415 LAMSADE, CNRS UMR7243, Université Paris Dauphine-PSL, 75775 Paris, France [email protected] https://orcid.org/0000-0002-5791-0887 ccs Replace ccsdesc macro with valid one keywords QBF, FPT algorithms, ETH † † runningauthor: A. Grigorjew and M. Lampis † † copyright: Andreas Grigorjew and Michael Lampis † † funding: This work was supported by ANR project ANR-21-CE48-0022 (S-EX-AP-PE-AL). † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The Quantified Boolean Formula problem (QBF) is the following: we are given a formula of the form Qx_{1}Qx_{2}\ldots Qx_{n}\varphi(x_{1},x_{2},\ldots,x_{n}) , where x_{1},\ldots,x_{n} are boolean variables, each Q is a quantifier ( \exists or \forall ) and \varphi is propositional, and we want to decide if the formula evaluates to True. QBF is the prototypical PSPACE-complete problem and clearly generalizes SAT, which is the special case when all quantifiers are existential. Because of its great generality, QBF captures a large class of important problems [ 2 , 3 , 10 , 18 , 19 ] , but at the same time it is considerably more difficult to solve than SAT, both in theory and in practice [ 15 ] . In this paper we focus on the complexity of solving QBF through the lens of parameterized algorithms 1 1 1 We assume the reader to be familiar with the basics of parameterized complexity, as given in standard textbooks [ 5 ] . . QBF is notoriously hard from this point of view as well and most standard parameters which allow tractable algorithms for SAT, such as treewidth, do not work for QBF (we review some of the relevant literature below). Nevertheless, a notable recent work of Eriksson, Lagerkvist, Ordyniak, Osipov, Panolan, and Rychlicki [ 7 ] succeeded in discovering a rare island of tractability for this problem by considering a natural but so far overlooked parameter: the number of existentially quantified variables. Their main results can be summarized as follows: if a QBF instance has \varphi given in CNF and only contains at most k existential variables, then the instance can be decided in time roughly m^{2^{k}} , where m is the number of clauses; while if all clauses of \varphi also have arity at most d=O(1) , this running time can be improved to roughly 2^{2^{k}}|\varphi|^{O(1)} . The former result is therefore an XP algorithm for parameter k (the number of existential variables), while the latter is a (rare!) FPT algorithm for QBF with a natural parameter. Even though the results of [ 7 ] are refreshing in the sense that they uncover a rare natural parameter for which non-trivial algorithmic results can be obtained for QBF, their double-exponential running time is a major drawback. This is, however, inevitable for formulas of unbounded arity, as [ 7 ] supplies a reduction establishing that, under the Exponential Time Hypothesis (ETH), the m^{2^{k}} algorithm is optimal. Nevertheless, in the bounded-arity case the same work only establishes a much weaker lower bound: no algorithm can solve QBF of arity 3 in time c^{k}|\varphi|^{O(1)} , for any constant c , unless the Strong Exponential Time Hypothesis is false. This lower bound is quite unsatisfying, as it both leaves a huge gap in complexity with respect to the upper bound and also relies on a much stronger (and less widely believed [ 20 ] ) complexity hypothesis than the lower bound for CNFs of unbounded arity. Our results The question of whether QBF with k existential variables on CNFs of constant arity can be solved faster than with a double-exponential dependence is stated explicitly in [ 7 ] , where the authors state that it is not clear which direction one should try to improve. Our main contribution here is to settle this question by proving the following: assuming the ETH is true, there is no algorithm that can solve QBF in time 2^{2^{o(k)}}|\varphi|^{O(1)} , even if the propositional part is given in CNF where all clauses have arity at most 4 . This settles the main question of [ 7 ] by showing that their algorithm is essentially optimal and significantly improves their lower bound while relying on a weaker hypothesis. Complementing these results we also consider an interesting special case of QBF where the input formula only has two quantifier blocks, which we denote \forall\exists -QBF. Our motivation for considering this restriction is that both of the lower bounds given in [ 7 ] already apply to this special case, so it is interesting to ask if our lower bound also applies. What we discover is that \forall\exists -QBF has a quite different complexity from general QBF when d is bounded: we show that for all d\geq 3 we can solve \forall\exists -QBF in time k^{O_{d}\left(k^{d-1}\right)} , where O_{d} hides factors depending on d , significantly improving upon the double-exponential dependence of the general case. Furthermore, we show that our algorithm is essentially optimal, up to a logarithmic factor in the exponent: for all d\geq 3 , if \forall\exists -QBF could be solved in time 2^{o(k^{d-1})}|\varphi|^{O(1)} , then the ETH would be false.

Read the complete text