Cover Image

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Eriksson, Leif, Lagerkvist, Victor, Ordyniak, Sebastian, Osipov, George, Panolan, Fahad, Rychlicki, Mateusz
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Solving Quantified Boolean Formulas with Few Existential Variables
by: Eriksson, Leif, et al.
Published: (2024)

Backdoors for Quantified Boolean Formulas
by: Eriksson, Leif, et al.
Published: (2026)

Explaining Decisions in ML Models: a Parameterized Complexity Analysis
by: Ordyniak, Sebastian, et al.
Published: (2024)

CSPs with Few Alien Constraints
by: Jonsson, Peter, et al.
Published: (2024)

Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)
by: Ordyniak, Sebastian, et al.
Published: (2025)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

Complexity of Faceted Explanations in Propositional Abduction
by: Schmidt, Johannes, et al.
Published: (2025)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Parameterized Complexity Of Representing Models Of MSO Formulas
by: Kučera, Petr, et al.
Published: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
by: Beyersdorff, Olaf, et al.
Published: (2021)

The Parameterized Complexity of Computing the VC-Dimension
by: Foucaud, Florent, et al.
Published: (2025)

d-QBF with Few Existential Variables Revisited
by: Grigorjew, Andreas, et al.
Published: (2026)

Towards Uniform Certification in QBF
by: Chew, Leroy, et al.
Published: (2022)

Complexity Results of Persuasion
by: Grastien, Alban
Published: (2025)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
by: Goertzel, Ben, et al.
Published: (2026)

QBF Merge Resolution is powerful but unnatural
by: Mahajan, Meena, et al.
Published: (2022)

Complexity of Scheduling Charging in the Smart Grid
by: de Weerdt, Mathijs, et al.
Published: (2017)

Over the Edge of Chaos? Excess Complexity as a Roadblock to Artificial General Intelligence
by: Susnjak, Teo, et al.
Published: (2024)

The Complexity of Symmetry Breaking Beyond Lex-Leader
by: Anders, Markus, et al.
Published: (2024)

On the Complexity of Identification in Linear Structural Causal Models
by: Dörfler, Julian, et al.
Published: (2024)

A Structural Complexity Analysis of Hierarchical Task Network Planning
by: Brand, Cornelius, et al.
Published: (2024)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
by: Dörfler, Julian, et al.
Published: (2024)

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
by: Guerzhoy, Michael
Published: (2024)

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
by: Asadi, Ali, et al.
Published: (2026)

Bounded degree QBF and positional games
by: Oijid, Nacim
Published: (2024)

New Perspectives on Semiring Applications to Dynamic Programming
by: Baril, Ambroise, et al.
Published: (2025)

Learning Tree Pattern Transformations
by: Neider, Daniel, et al.
Published: (2024)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
by: Chambon, Pierre, et al.
Published: (2025)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
by: Ganian, Robert, et al.
Published: (2026)

The Computational Complexity of Circuit Discovery for Inner Interpretability
by: Adolfi, Federico, et al.
Published: (2024)

Linear Equations with Min and Max Operators: Computational Complexity
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

Data Complexity in Expressive Description Logics With Path Expressions
by: Bednarczyk, Bartosz
Published: (2024)