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

The Boolean satisfiability problem is a well-known NP-complete problem. Due to the rapid advance of SA T solvers, many combinatorial problems are today solved by reducing to SA T, which can then be solved with off-the-shelf solvers. SA T fundamentally encodes a form of monotonic reasoning in the sense that conclusions remain valid regardless if new information is added. However, the real world is non-monotonic, meaning that one should be able to retract a statement if new data is added which violates the previous conclusion. One of the best known examples of non-monotonic reasoning is abductive reasoning where we are interested in finding an explanation, vis- ` a-vis a hypothesis, of some observed manifestation. Abduction has many practical applications, e.g., scientific discovery [10], network security [1], computational biology [22], medical diagnosis [18], knowledge base updates [23], and explainability issues in machine learning and decision support systems [7, 8, 2, 21]. This may be especially poignant in forthcoming decades due to the continued emergence of AI in new and surprising applications, which need to be made GDPR compliant [26] and explainable. The incitement for solving abduction fast, even when it is classically intractable, thus seems highly practically motivated. Can non-monotonic reasoning be performed as efficiently as monotonic reasoning, or are there fundamental differences between the two?