DNFs

Though the class of DNF formulas has very good computational properties, abduction remains a hard problem for it as a whole, even with additional restrictions. Recall that the TAUTOLOGY problem is the one of deciding whether a given DNF formula represents the identically true function, and that this problem is coNP-complete.

Proposition 3   Deciding whether there is at least one explanation for a given abduction problem $(\Sigma,\alpha,A)$ is NP-complete when $\Sigma$ is given in DNF, even if $\alpha$ is a variable and $A\cup\{\alpha\}=Var(\Sigma)$.

Sketch of proof Membership in NP is obvious, since deduction with DNFs is polynomial; now it is easily seen that $\Sigma$ is tautological if and only if the abduction problem $(\Sigma\vee(x),x,Var(\Sigma))$ has no explanation, where $x$ is a variable not occuring in $\Sigma$ (see the DNF $\Sigma\vee(x)$ as the implication $\overline{\Sigma}\rightarrow x$); $\Sigma\vee(x)$ is in DNF, and we get the result. $\square$

However, when $\Sigma$ is represented by a DNF projecting it onto $A$ is easy; indeed, the properties of projection show that it suffices to cancel its literals that are not formed upon $A$. Consequently, if $\phi$ is such a DNF containing $k$ terms, then a DNF $\psi$ with ${\mathcal M}(\psi)=({\mathcal M}(\phi))_{\vert A}$ and containing at most $k$ terms can be computed in time $O(k\vert Var(\phi)\vert)$.

Thus we can show that some subclasses of the class of all DNFs allow polynomial abduction. We state the first result quite generally, but note that its assumptions are satisfied by natural classes of DNFs: e.g., that of Horn DNFs, i.e., those DNFs with at most one positive literal per term; similarly, that of Horn-renamable DNFs, i.e., those that can be turned into a Horn DNF by replacing some variables with their negation, and simplifying double negations, everywhere in the formula; $2$DNFs, those DNFs with at most two literals per term. We omit the proof of the following proposition, since it is essentially the same as that of Proposition 2 (simply follow the execution of the algorithm).

Proposition 4   Let ${\mathcal D}$ be a class of DNFs that is stable under removal of occurrences of literals and for which the TAUTOLOGY problem is polynomial. If $\Sigma$ is restricted to belong to ${\mathcal D}$, $\alpha$ is a clause and $A$ is a subset of $Var(\Sigma)$, then searching for a best explanation for $\Pi=(\Sigma,\alpha,A)$ can be done in polynomial time.

Thus we can establish that abduction is tractable if (among others) $\Sigma$ is in Horn-renamable DNF (including the Horn and reverse Horn cases) or in $2$DNF, and $\alpha$ is a clause.

Finally, let us point out that with a very similar proof we can obtain polynomiality for some problems obtained by strengthening the restriction of Proposition 4 over $\Sigma$, but weakening that over $\alpha$.

Proposition 5   If $\Sigma$ is represented by a Horn (resp. reverse Horn) DNF of $k$ terms and $\alpha$ by a positive (resp. negative) CNF of $k'$ clauses, and $A$ is a subset of $Var(\Sigma)$, then searching for a best explanation for $\Pi=(\Sigma,\alpha,A)$ can be done in time $O((k+\vert A\vert)kk'n)$. The same holds if $\Sigma$ is represented by a positive (resp. negative) DNF of $k$ terms and $\alpha$ by a Horn (resp. reverse Horn) CNF of $k'$ clauses.

Once again note that variables, literals and terms are all special cases of (reverse) Horn CNFs, and that variables, positive (resp. negative) clauses and positive (resp. negative) terms are all special cases of positive (resp. negative) CNFs.