The main general complexity results about propositional logic-based abduction
with subset-minimality preference were stated by Eiter and Gottlob
[EG95]. The authors show that deciding whether a given abduction
problem has a solution at all is a -complete problem, even if
and
is in CNF. As
stated as well by Selman and Levesque [SL90], they also establish
that this problem becomes ``only'' NP-complete when
is Horn, and
even acyclic Horn. Note that when SAT and deduction are polynomial with
the problem is obviously in NP.
In fact, very few classes of abduction problems are known to be polynomial for the search for explanations. As far as we know, the only such classes are those defined by the following restrictions (once again we refer the reader to the references for definitions):
Let us also mention that Amilhastre et al. [AFM02] study most of
the related problems in the more general framework of multivalued theories
instead of propositional formulas, i.e., when the domain of the variables is
not restricted to be . The authors mainly show, as far as this note
is concerned, that deciding whether there exists an explanation is still a
-complete problem [AFM02, Table 1].
Note that not all these results are stated in our exact framework in the papers cited above, but that they all still hold in it. Let us also mention that the problem of enumerating all the best explanations for a given abduction problem is of great interest; Eiter and Makino [EM02] provide a discussion and some first results about it, mainly in the case when the knowledge base is Horn.