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

Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt

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 co…