Next: Discussion and Perspectives Up: Polynomial Classes Previous: Affine Formulas

## 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 is NP-complete when is given in DNF, even if is a variable and .

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

However, when is represented by a DNF projecting it onto is easy; indeed, the properties of projection show that it suffices to cancel its literals that are not formed upon . Consequently, if is such a DNF containing terms, then a DNF with and containing at most terms can be computed in time .

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; 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 be a class of DNFs that is stable under removal of occurrences of literals and for which the TAUTOLOGY problem is polynomial. If is restricted to belong to , is a clause and is a subset of , then searching for a best explanation for can be done in polynomial time.

Thus we can establish that abduction is tractable if (among others) is in Horn-renamable DNF (including the Horn and reverse Horn cases) or in DNF, and 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 , but weakening that over .

Proposition 5   If is represented by a Horn (resp. reverse Horn) DNF of terms and by a positive (resp. negative) CNF of clauses, and is a subset of , then searching for a best explanation for can be done in time . The same holds if is represented by a positive (resp. negative) DNF of terms and by a Horn (resp. reverse Horn) CNF of 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.

Next: Discussion and Perspectives Up: Polynomial Classes Previous: Affine Formulas
Bruno Zanuttini 2003-06-30