--- title: "A Fine-Grained Complexity View on Propositional Abduction - Algorithms and Lower Bounds" authors: - "Victor Lagerkvist" - "Mohamed Maizia" - "Johannes Schmidt" doi: "10.24963/ijcai.2025/508" url: "https://ijcai.org/proceedings/2025/508" pdf: "https://ijcai.org/proceedings/2025/0508.pdf" venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence" year: 2025 pages: "4562-4569" track: "Main Track" keywords: - "Constraint Satisfaction and Optimization: CSO: Constraint satisfaction" - "Knowledge Representation and Reasoning: KRR: Non-monotonic reasoning" - "Constraint Satisfaction and Optimization: CSO: Satisfiabilty" - "Knowledge Representation and Reasoning: KRR: Diagnosis and abductive reasoning" --- # A Fine-Grained Complexity View on Propositional Abduction - Algorithms and Lower Bounds Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt *Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 4562-4569. DOI: [10.24963/ijcai.2025/508](https://doi.org/10.24963/ijcai.2025/508) ## Abstract 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.