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

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