Previous Work

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 $\Sigma^P_2$-complete problem, even if $A\cup Var(\alpha)=Var(\Sigma)$ and $\Sigma$ is in CNF. As stated as well by Selman and Levesque [SL90], they also establish that this problem becomes ``only'' NP-complete when $\Sigma$ is Horn, and even acyclic Horn. Note that when SAT and deduction are polynomial with $\Sigma$ 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):

• $\Sigma$ is in $2$CNF and $\alpha$ is in $2$DNF [Mar00, Section 4.2]
• $\Sigma$ is given as a monotone CNF and $\alpha$ as a clause [Mar00, Section 4.2]
• $\Sigma$ is given as a definite Horn CNF and $\alpha$ as a conjunction of positive literals [SL90,EG95]
• $\Sigma$ is given as an acyclic Horn CNF with pseudo-completion unit-refutable and $\alpha$ is a variable [Esh93]
• $\Sigma$ has bounded induced kernel width and $\alpha$ is given as a literal [Val00]
• $\Sigma$ is represented by its set of characteristics models (with respect to a particular basis) and $\alpha$ is a variable [KR96]; note that a set of characteristic models is not a propositional formula, but that the result is however similar to the other ones
• $\Sigma$ is represented by the set of its models, or, equivalently, by a DNF with every variable occurring in each term, and $\alpha$ is any propositional formula.

The first two classes are proved polynomial with a general method for solving abduction problems with the notion of prime implicants, the last one is obvious since all the information is explicitely given in the input, and the four others are exhibited with ad hoc algorithms.

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 $\{0,1\}$. The authors mainly show, as far as this note is concerned, that deciding whether there exists an explanation is still a $\Sigma_2^P$-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.