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 (Eiter
& Makino, 2002).

As identified by Selman and Levesque (1990), 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, whi prevents from imposing a sign to the literals the hypotheses are formed upon, contrariwise to more general formalizations proposed for abduction, as Marquis' (Marquis, 2000). Even if we think this is not a pro­
hibiting 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 {0, 1}: e.g., signed formulas (Beckert et al., 1999). This framework is used, for instance, for configuration problems by Amilhastre et al. (2002). 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 (Eiter & Gottlob, 1995). An abducible x is said to be relevant to an abduction problem Π if there is at least one best explanation for Π containing x or ¬ x , and necessary to Π if all the best explanations for Π contain x or ¬ x . It is easily seen that x is necessary for Π = (Σ, α, Α) if and only if Π ′ = (Σ, α, Α\{x}) 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 A\{x} for A, 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.

## Acknowledgments

The author wishes to thank the anonymous referees of this version and those of a previous one (Proc. JNPC'02, in French), as well as Jean-Jacques Hébrard, for very valuable and constructive comments.

## References

Amilhastre, J., Fargier, H., & Marquis, P. (2002). Consistency restoration and explanations in dynamic CSPs - application to configuration. Artificial Intelligence, 135 (1–2),
199-234.