Discussion and Perspectives

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 $\Sigma$ in $2$CNF and $\alpha$ in $2$DNF, or $\Sigma$ in monotone CNF and $\alpha$ given as a clause). The following list summarizes the main new polynomial restrictions:

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

Moreover, even if there is no guarantee for efficiency in the general case the presentation of our algorithm does not depend on the syntactic form of $\Sigma$ or $\alpha$, and it uses only standard operations on Boolean functions (projection, conjunction, negation).

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 ($\Sigma'$). 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 $\Sigma$ and $\alpha$ 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 [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 $x$ is said to be relevant to an abduction problem $\Pi$ if there is at least one best explanation for $\Pi$ containing $x$ or $\neg x$, and necessary to $\Pi$ if all the best explanations for $\Pi$ contain $x$ or $\neg x$. It is easily seen that $x$ is necessary for $\Pi=(\Sigma,\alpha,A)$ if and only if $\Pi'=(\Sigma,\alpha,A\backslash\{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\backslash\{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.