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

arXiv: https://arxiv.org/abs/2505.10201 · HTML: https://mlsanity.com/paper/2505.10201/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 15 May 2025.

## Builds on (most cited first, 2 of 2)

- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Modelling GDPR-Compliant Explanations for Trustworthy AI](https://mlsanity.com/paper/2109.04165/) (2021)

## Abstract (arXiv)

The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for SigmaP2- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a SigmaP2-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.