2025/05/15 by Lagerkvist, Victor, Maizia, Mohamed, Schmidt, Johannes
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.10201
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 ΣP2- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a ΣP2-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.