The general algorithm presented in this note allows us to derive new polynomial restrictions of abduction problems; even if this is not discussed here, for lack of space, it also allows to unify some previously known such restrictions (such as in CNF and in DNF, or in monotone CNF and given as a clause). The following list summarizes the main new polynomial restrictions:

- given as an affine formula and as a disjunction of linear equations (Proposition 2)
- in Horn-renamable DNF and given as a clause (Proposition 4)
- in DNF and given as a clause (Proposition 4)
- in Horn (reverse Horn) DNF and in positive (negative) CNF (Proposition 5)
- in negative (positive) DNF and in reverse Horn (Horn) CNF (Proposition 5).

Another interesting feature of this algorithm is that before minimization it
computes the explanations *intentionnally*. Consequently, all the full
explanations can be enumerated with roughly the same delay as the models of
the formula representing them (). However, of course, there is
no guarantee that two of them would not be minimized into the same
*best* explanation, which prevents from concluding that our algorithm
can enumerate all the *best* explanations; trying to extend it into
this direction would be an interesting problem. For more details about
enumeration we refer the reader to Eiter and Makino's work [EM02].

As identified by Selman and Levesque [SL90], central to the task is the notion of projection over a set of variables, and our algorithm isolates this subtask. However, our notion of projection only concerns variables, and not literals, which prevents from imposing a sign to the literals the hypotheses are formed upon, contrariwise to more general formalizations proposed for abduction, as Marquis' [Mar00]. Even if we think this is not a prohibiting restriction, it would be interesting to try to fix that weakness of our algorithm while preserving its polynomial classes.

Another problem of interest is the behaviour of our algorithm when
and are not only propositional formulas, but more generally
*multivalued theories*, in which the domain of variables is not
restricted to be : e.g., signed formulas [BHM99]. This
framework is used, for instance, for configuration problems by Amilhastre et
al. [AFM02]. It is easily seen that our algorithm is still correct
in this framework; however, there is still left to study in which cases its
running time is polynomial.

Finally, problems of great interest are those of deciding the
*relevance* or the *necessity* of an abducible [EG95].
An abducible is said to be *relevant* to an abduction problem
if there is at least one best explanation for containing or
, and *necessary* to if all the best explanations for
contain or . It is easily seen that is necessary for
if and only if
has no explanation, hence showing
that polynomial restrictions for the search for explanations are polynomial
as well for deciding the necessity of an hypothesis as soon as they are
stable under the substitution of
for , which is the
case for all restrictions considered in this note. Contrastingly, we do not
know of any such relation for relevance, and the study of this problem would
also be of great interest.