Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki · 2026

Read Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach by Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki (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-12073.txt.

Introduction

Leif Eriksson and five colleagues study a new way to size hard logic problems. Their yardstick counts the clauses that must be cut to reach an easy class, called a clause covering backdoor. The test problems are quantified Boolean formulas, a class known to be PSPACE-complete. For the old easy classes Horn, 2-CNF, and linear equations, they prove Horn is W[1]-hard while the rest allow fast fixed-parameter methods. Their methods use propagation and Gaussian elimination, and just one key case is left open for a full split.

Catalog record

CREATORLeif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65063
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki Abstract Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to problems in NP, a lack of positive theoretical results, and in the parameterized complexity setting one often has to restrict the quantifier prefix (e.g., bounding alternations) to obtain fixed parameter tractability (FPT). We propose a new parameter: the number of variables in clauses that has to be removed before reaching a tractable class (a clause covering (CC) backdoor ). We are then interested in solving QBF in FPT time given a CC-backdoor of size k k . We consider the three classical, tractable cases of QBF as base classes: Horn , 2-CNF , and linear equations . We establish W ⁡ [ 1 ] \mathrm{W}[1] -hardness for Horn but prove FPT for the others, and prove that in a precise, algebraic sense, we are only missing one important case for a full dichotomy. Our algorithms are non-trivial and depend on propagation, and Gaussian elimination, respectively, and are comparably unexplored for QBF. 1 Introduction The Boolean satisfiability problem (SAT) is the canonical NP-complete problem. Many hard problems can today be solved efficiently by a suitable SAT encoding together with off-the-shelf solvers [ 3 ] . While this often works well for problems in NP, many fundamental problems in AI and machine learning are harder than NP, with PSPACE crystallizing as the most fundamental class. Examples include neural network training [ 1 ] , graph neural network satisfiability [ 17 ] , and quantized graph neural network verification [ 18 ] , all of which are PSPACE-complete or contained in PSPACE. In symbolic AI, planning problems like STRIPS and SAS + also fall inside PSPACE. Solving PSPACE problems is thus a pressing issue. The canonical hard problem is the quantified Boolean formula problem (QBF), deciding the validity of \Psi=Q_{1}x_{1}\ldots Q_{n}x_{n}.\phi(x_{1},\ldots,x_{n}) where Q_{i}\in\{\forall,\exists\} and \phi is in CNF. Unfortunately, we lack fast techniques for solving QBF instances. Theoretically, \Psi can be solved in 2^{n} time by branching: \exists requires one successful branch while \forall requires both. While SAT’s 2^{n} complexity can be improved to c_{k}^{n} for c_{k}<2 for any k -CNF, no such improvement is known even for k=3 for QBF, and it is conjectured impossible unless the strong exponential-time hypothesis (SETH) [ 5 ] fails [ 6 ] . Hence, we move to parameterized complexity to identify parameters k (corresponding to a “hidden structure”) leading to tractability. We seek fixed-parameter tractability ( \mathrm{FPT} ), i.e., f(k)\cdot||\Psi||^{\mathcal{O}(1)} time for a computable f . \mathrm{FPT} is also characterized by a kernel : a polynomial-time procedure reducing an instance (\Psi,k) to (\Psi^{\prime},k^{\prime}) where ||\Psi^{\prime}||+k^{\prime}\leq f(k) . A well-known parameter is treewidth , measuring how tree-like a formula is. For instance, while QBF remains PSPACE-complete even for constant treewidth [ 2 ] it is \mathrm{FPT} parameterized by treewidth plus quantifier alternations. However, even in this case, f is a power tower which, even for small values, requires more operations than there are atoms in the universe. The most successful parameter besides treewidth is arguably backdoor size , which measures how close an instance is to a tractable class. For SAT, a (strong) backdoor for \phi is a set B\subseteq V(\phi) such that \phi[\tau] belongs to a fixed, tractable class (e.g., 2 -CNF) for each partial assignment \tau\colon B\to\{0,1\} . Here, \phi[\tau] is the formula obtained by replacing variables in B with their values under \tau and simplifying, and V(\phi) is the set of variables in \phi . However, backdoors cannot readily be applied to QBF since branching on B may violate the quantifier prefix. This can be circumvented with restrictions on the quantifier prefix [ 19 ] (e.g., that backdoor variables are to the left), but this only provides a meaningful speed-up for a very narrow class of QBF formulas. In this paper we investigate an alternative QBF backdoor notion which avoids any such restrictions. We primarily consider 2-CNF , \textup{HORN}/\textup{DualHORN} (at most one positive/negative literal in each clause), and AFF (systems of linear equations over GF(2)). We assume that the formulas in each class are conjunctions of clauses/atoms, e.g., each formula in 2-CNF is a conjunction of clauses of arity 2. For a class of formulas \mathcal{C} we write \textsc{QBF}(\mathcal{C}) for the QBF problem restricted to instances in \mathcal{C} . A first idea could be to measure the distance to a tractable class \mathcal{C} with respect to the number of clauses that are outside \mathcal{C} . I.e., if we view \phi as a set of clauses, we let \phi_{\mathcal{C}}\subseteq\phi be the maximal subset of clauses in \phi such that \phi_{\mathcal{C}} belongs to \mathcal{C} , and parameterize by |\phi\setminus\phi_{\mathcal{C}}| . Unfortunately, allowing even one out-of-class clause to be added to a 2-SAT or a Horn formula makes the problem PSPACE-complete [ 15 ] . Thus, we propose parameterization by |V(\phi\setminus\phi_{\mathcal{C}})| , i.e., the number of variables that cover all out-of-class clauses, leading to the following definition. Definition 1.1 . Let \mathcal{C} be a class of formulas. Let \Phi=\mathcal{Q}.\phi be a QBF formula. A set B of variables is a clause covering backdoor (CC-backdoor) for \Phi if \phi\setminus C\in\mathcal{C} for a subset C\subseteq\phi of clauses such that V(C)=B . Note that the CC-backdoor detection problem is trivial for all classical base classes: if the tractable class (e.g., 2-CNF) is fixed then we simply collect all out-of-class clauses, compute the set of variables covering them, and see whether it has the required size. Hence, the computationally interesting problem is CC-backdoor evaluation : given a QBF formula \Psi and CC-backdoor of size k , can \Psi be evaluated in \mathrm{FPT} time with respect to k ? Given the lack of \mathrm{FPT} results for QBF with unbounded quantifier alternations, there is perhaps not much reason to be optimistic. Furthermore, the standard quantifier elimination does not seem directly compatible with CC-backdoor evaluation problem: by eliminating backdoor variables we get a complicated disjunctive formula which does not appear to be easier to solve than the original formula. The main complication, then, is that the backdoor variables may be involved in the in-the-class clauses, i.e., some of them may be in V(\phi_{\mathcal{C}}) , so it is not possible to solve the backdoor part independently. Moreover, they can occur anywhere in the quantifier prefix. Despite this grim outlook we manage to prove \mathrm{FPT} for 2-CNF and AFF. For 2-CNF we use an elaborate branching strategy with look-ahead. Essentially, by going from left to right in the quantifier prefix we prove that one either (1) can branch and always “hits” a variable in the backdoor and therefore decreases the parameter k , or (2) if branching would not affect the backdoor variables, then one can disregard one of the branches. Then, depending on the current quantifier ( \exists or \forall ) we either continue the process or correctly report unsatisfiability. Concurrently, we repeatedly propagate the input formula to ensure that we do not miss any immediate implications. Put together, this results in an \mathrm{FPT} algorithm where f(k)=2^{k} and with a polynomial factor dominated by n^{3} from propagation.

Read the complete text