Imagen de Portada

Solving Quantified Boolean Formulas with Few Existential Variables

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Eriksson, Leif, Lagerkvist, Victor, Osipov, George, Ordyniak, Sebastian, Panolan, Fahad, Rychlicki, Mateusz
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Artificial Intelligence
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
por: Eriksson, Leif, et al.
Publicado: (2026)

Backdoors for Quantified Boolean Formulas
por: Eriksson, Leif, et al.
Publicado: (2026)

CSPs with Few Alien Constraints
por: Jonsson, Peter, et al.
Publicado: (2024)

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

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

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

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

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

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

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
por: Jonsson, Peter, et al.
Publicado: (2025)

Model Counting for Dependency Quantified Boolean Formulas
por: Fung, Long-Hin, et al.
Publicado: (2025)

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

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

Solving Multiagent Path Finding on Highly Centralized Networks
por: Fioravantes, Foivos, et al.
Publicado: (2024)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
por: Beniamini, Gal, et al.
Publicado: (2025)

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

Quantifying over Optimum Answer Sets
por: Mazzotta, Giuseppe, et al.
Publicado: (2024)

Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
por: Pratt-Hartmann, Ian
Publicado: (2008)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
por: Chen, Bo, et al.
Publicado: (2025)

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

Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
por: Aavani, Amir
Publicado: (2026)

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

Learning Tree Pattern Transformations
por: Neider, Daniel, et al.
Publicado: (2024)

Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
por: Li, Jinzhao, et al.
Publicado: (2023)

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

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
por: Yamakami, Tomoyuki
Publicado: (2017)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
por: Li, Chenyang, et al.
Publicado: (2025)

Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
por: Wilson, Nic, et al.
Publicado: (2024)

On the Number of Quantifiers Needed to Define Boolean Functions
por: Carmosino, Marco, et al.
Publicado: (2024)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
por: Cao, Yang, et al.
Publicado: (2024)

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

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

Probabilistic Generating Circuits -- Demystified
por: Agarwal, Sanyam, et al.
Publicado: (2024)

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

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

ActionReasoningBench: Reasoning about Actions with and without Ramification Constraints
por: Handa, Divij, et al.
Publicado: (2024)

Social Distancing Induced Coronavirus Optimization Algorithm (COVO): Application to Multimodal Function Optimization and Noise Removal
por: Varma, Om Ramakisan, et al.
Publicado: (2024)

Probabilistic Explanations for Linear Models
por: Subercaseaux, Bernardo, et al.
Publicado: (2024)

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

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