Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

• URL: http://arxiv.org/abs/2605.12073v1
• Date: Tue, 12 May 2026 13:00:55 GMT
• Title: Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
• Abstract summary: We consider the validity of a quantified Boolean formula (QBF)<n>We propose a new parameter: the number of variables in clauses that has to be removed before reaching a tractable class.<n>We are then interested in solving QBF in FPT time given a CC-backdoor of size $k$.
• Score: 19.400202883397537
• License: http://creativecommons.org/licenses/by/4.0/
• 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$. We consider the three classical, tractable cases of QBF as base classes: Horn, 2-CNF, and linear equations. We establish 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.

Related papers

• Decoded Quantum Interferometry for Weighted Optimization Problems [6.4675604105664]
  Decoded Quantum Interferometry (DQI) is a recently introduced quantum optimization to decoding.<n>In its original formulation, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest.<n>We develop a theory of DQI for weighted optimization problems, focusing on the weighted Max-LINSAT problem.
  arXiv  Detail & Related papers  (2026-05-11T14:45:46Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete [0.0]
  We prove that deciding whether a classical-quantum (C-Q) channel can exactly preserve a single classical bit is QCMA-complete.<n>This "bit-preservation" problem is a special case of orthogonality-constrained optimization tasks over C-Q channels.
  arXiv  Detail & Related papers  (2025-08-14T14:03:38Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Compilation and Fast Model Counting beyond CNF [31.620928650659586]
  This paper strengthens our theoretical knowledge of what classes of functions can be efficiently transformed, or compiled, into d-DNNF.<n>The constraints in question are all functions representable by constant-width ordered binary decision diagrams (OBDDs) for all variable orderings.<n>We give a more efficient FPT algorithm for model counting that applies to a sub-family of the constraints and does not require compilation.
  arXiv  Detail & Related papers  (2025-02-01T14:00:04Z)
• Solving Quantified Boolean Formulas with Few Existential Variables [19.221715574358207]
  The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. In this paper we consider a simple but overlooked parameter: the number of existentially quantified variables. We then develop a novel FPT algorithm applicable to QBF instances in conjunctive normal form (CNF) of bounded clause length.
  arXiv  Detail & Related papers  (2024-05-10T14:07:29Z)
• General Boolean Formula Minimization with QBF Solvers [4.264192013842096]
  We are interested in the problem of obtaining an equivalent formula in any format. We are motivated in applying minimization algorithms to generate natural language translations of the original formula. We analyze three possible (practical) approaches to solving the problem.
  arXiv  Detail & Related papers  (2023-03-12T12:08:58Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.