Propositional Abduction is Almost Always Hard
2005 (English)In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-2005), Edinburgh, Scotland, UK, 2005, 534-539 p.Conference paper (Other academic)
Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. Applications of this process range from car configuration to medical diagnosis. We study here its computational complexity in the case where the application domain is described by a propositional theory built upon a fixed constraint language and the hypotheses and manifestations are described by sets of literals. We show that depending on the language the problem is either polynomial-time solvable, NP-complete, or Σ P 2-complete. In particular, we show that under the assumption P�=NP, only languages that are affine of width 2 have a polynomial algorithm, and we exhibit very weak conditions for NP-hardness.
Place, publisher, year, edition, pages
2005. 534-539 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-14455OAI: oai:DiVA.org:liu-14455DiVA: diva2:23527