Copertina

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lagerkvist, Victor, Maizia, Mohamed, Schmidt, Johannes
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Artificial Intelligence F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
di: Kazakov, Yevgeny, et al.
Pubblicazione: (2009)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
di: Istrate, Gabriel
Pubblicazione: (2024)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
di: von Liechtenstein, Maximilian R. P.
Pubblicazione: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
di: Knop, Dušan, et al.
Pubblicazione: (2017)

On the Complexity of Determinations
di: Hellerstein, Joseph M.
Pubblicazione: (2026)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
di: Saha, Barna, et al.
Pubblicazione: (2024)

A Piecewise Approach for the Analysis of Exact Algorithms
di: Clinch, Katie, et al.
Pubblicazione: (2024)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

Thin Tree Verification is coNP-Complete
di: Moayyedi, Alice
Pubblicazione: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
di: Kiatchaipipat, Nattapol, et al.
Pubblicazione: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
di: Gupta, Chetan, et al.
Pubblicazione: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
di: Fritsch, Timo, et al.
Pubblicazione: (2026)

Fast Simulation of Cellular Automata by Self-Composition
di: Natal, Joseph, et al.
Pubblicazione: (2024)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
di: van Brügge, Jan
Pubblicazione: (2024)

Complexity of Firefighting on Graphs
di: Althoetmar, Julius, et al.
Pubblicazione: (2025)

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

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
di: Kowaluk, Miroslaw, et al.
Pubblicazione: (2025)

Direct Sums for Parity Decision Trees
di: Besselman, Tyler, et al.
Pubblicazione: (2024)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
di: Lingas, Andrzej
Pubblicazione: (2026)

An Algorithm for a Variation of the Shortest Common Superstring Problem
di: Gilfanov, Arthur
Pubblicazione: (2024)

The Complexity of Graph Exploration Games
di: Fuchs, Janosch, et al.
Pubblicazione: (2023)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
di: Krithika, R., et al.
Pubblicazione: (2023)

On the Complexity of Neural Computation in Superposition
di: Adler, Micah, et al.
Pubblicazione: (2024)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
di: Phillips, Reed
Pubblicazione: (2026)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
di: de Rezende, Susanna F., et al.
Pubblicazione: (2019)

The Complexity of Blocking All Solutions
di: Grüne, Christoph, et al.
Pubblicazione: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
di: de Rezende, Susanna F., et al.
Pubblicazione: (2024)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
di: Bartlett, Celina Janet
Pubblicazione: (2025)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
di: Grüne, Christoph, et al.
Pubblicazione: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
di: Salas, Jesus
Pubblicazione: (2025)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
di: Bodirsky, Manuel, et al.
Pubblicazione: (2026)

Enhanced and Efficient Reasoning in Large Learning Models
di: Valiant, Leslie G.
Pubblicazione: (2026)

On Minimum Maximal Distance-k Matchings
di: Kartynnik, Yury, et al.
Pubblicazione: (2016)

Graph Threading with Turn Costs
di: Demaine, Erik D., et al.
Pubblicazione: (2024)