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):
- Σ is in 2 CNF and α is in 2 DNF (Marquis, 2000, Section 4.2)
- Σ is given as a monotone CNF and α as a clause (Marquis, 2000, Section 4.2)

- Σ is given as a definite Horn CNF and α as a conjunction of positive literals (Selman
& Levesque, 1990; Eiter & Gottlob, 1995)
- Σ is given as an acyclic Horn CNF with pseudo-completion unit-refutable and α is a variable (Eshghi, 1993)
- Σ has bounded induced kernel width and α is given as a literal (del Val, 2000)

- Σ is represented by its set of characteristics models (with respect to a particular basis)
and α is a variable (Khardon & Roth, 1996); note that a set of characteristic models is not a propositional formula, but that the result is however similar to the other ones
- Σ is represented by the set of its models, or, equivalently, by a DNF with every variable occurring in each term, and α 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. (2002) 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 E -complete problem (Amilhastre et al., 2002, 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 (2002) provide a discussion and some first results about it, mainly in the case when the knowledge base is Horn.

## 5. A General Algorithm

We now give the principle of our algorithm. Let us stress first that, as well as, e.g., Marquis' construction (Marquis, 2000, Section 4.2), its outline matches point by point the definition of a best explanation; our ideas and Marquis' are anyway rather close.

We are first interested in the hypotheses in which every abducible x ∈ A occurs (either negated or unnegated); let us call them full hypotheses. Note indeed that every explanation E for an abduction problem is a subconjunction of a full explanation F ; indeed, since E is by definition such that Σ ∧ E is satisfiable and implies α , it suffices to let F be Select A ( m )
for a model m of Σ ∧ E ∧ α . Minimization of F will be discussed later on.