Propositional Abduction Is Almost Always Hard

Abstract

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.