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.