A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
This work addresses a gap in fine-grained complexity theory for non-monotonic reasoning, offering foundational insights for researchers in computational logic and AI, though it is incremental in bridging monotonic and non-monotonic reasoning.
The paper tackles the complexity of intractable abduction problems in non-monotonic reasoning by analyzing them under the parameter n (number of variables), achieving positive results for Σ^P_2-, NP-, and coNP-complete fragments, including the first example of beating exhaustive search for a Σ^P_2-complete problem, and provides lower bounds ruling out improvements under the strong exponential-time hypothesis.
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 $Σ^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $Σ^P_2$-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.