Showing 2025Show all
2 papers · 1 filter
cs.AI2025
Complexity of Faceted Explanations in Propositional Abduction
Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist +1
Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artif…
cs.CC2025
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…