on the other hand the affine approximations of a knowledge base can be made very small and are efficiently learnable (Zanuttini, 2002). We show that projecting an affine formula onto a subset of its variables is quite easy too, enabling our algorithm to run in polynomial time.

The proof of the following lemma is easily obtained with gaussian elimination (Curtis, 1984):
triangulate φ with the variables in A put rightmost, and then keep only those equations formed upon A; full details are given in the technical report version (Zanuttini, 2003). Lemma 1 Let φ be an affine formula containing k equations, and A ⊆ Var(φ).  Then an affine formula ψ with M (ψ) = (M(φ)) 14 and containing at most k equations can be computed in time O(k 2 | Var(φ)|).

Proposition 2 If Σ is represented by an affine formula containing k equations and α by a disjunction of k' linear equations, and A is a subset of Var(Σ), then searching for a best explanation for Π = (Σ, α, Α) can be done in time Ο(( k + k ′ )(( k + 1) 2 + ( Α |( k + k ′ )) n ). Sketch of proof  It is easily seen that an affine formula (containing k ′ + k equations and n variables) for Σ ∧ α can be computed in time linear in the size of α; this formula can be projected onto A in time O(( k + k ′ ) 2 n ), and we straightforwardly get a disjunction of at most k + k ′ linear equations for ( M ( Σ ∧ ¤ )) 14 . Then we can use distributivity of ∧ over ∨ for solving the satisfiability problem of the algorithm; recall that SAT can be solved in time O(k 2 n ) for an affine formula of k equations over n variables by the elimination method of Gauss (Curtis, 1984). The remaining operations are straightforward.

□
Note that variables, literals and clauses are special cases of disjunctions of linear equations.

## 6.2 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 TAUTOL OGY 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 A U {α} = V ar (Σ). 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 (Σ V (x), x, Var(Σ)) has no explanation, where x is a variable not occuring in Σ (see the DNF E V ( x ) as the implication E → x ); E V ( x ) is in DNF, and we get the result.

□
However, when Σ 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 φ is such a DNF containing k terms, then a DNF ψ with M(ψ) = ( M(φ) ) LA
and containing at most k terms can be computed in time O(k|Var(¢)|).

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 sssee to the control of the control