Propositional Abduction is Almost Always Hard

1 Introduction

In this paper we investigate the computational complexity of abduction, a method of reasoning extensively studied by Peirce [1955]. Abductive reasoning is used to search for explanations of observed manifestations. The importance of this problem to Artificial Intelligence was first emphasized by Morgan [1971] and Pople [1973].

The abductive process has demonstrated its practical importance in many domains. In particular, it has been used to formalize processes in medical diagnosis [Bylander et al., 1991], text interpretation [Hobbs et al., 1993], system diagnosis [Stumptner and Wotawa, 2001] and configuration problems [Amilhastre et al., 2002].

In this paper we are interested in propositional logic-based abduction, i.e., the background knowledge is represented by a propositional theory. Even in this framework several formalizations of the problem have been studied in the literature, depending on the syntactic restrictions imposed to the manifestations and on the hypotheses over which explanations must be formed. We use the following formalization: Given a propositional theory T formalizing a particular application domain, a set M of literals describing a set of manifestations, and a set H of literals containing possible hypotheses, find an

∗Supported by the National Graduate School in Computer Science (CUGS), Sweden.

Bruno Zanuttini

GREYC, UMR CNRS 6072 Universit´e de Caen, Bd. du Mar´echal Juin F-14 032 Caen Cedex, France

zanutti@info.unicaen.fr

explanation for M, that is, a set E ⊆ H such that T ∪ E is consistent and logically entails M. This framework is more general than most frameworks studied in the literature; an exception is the definition by Marquis [Marquis, 2000], which allows the manifestation to be encoded by any propositional formula.

Example 1 Consider the following example from the domain of motor vehicles, inspired by [Console et al., 1991].

T = (¬rich mixture∨¬lean mixture)∧ (rich mixture→¬low fuel consumption)∧ (lean mixture→overheating)∧ (low water→overheating), H = {rich mixture, lean mixture, low water}, M = {¬low fuel consumption, overheating}.

Then E = {rich mixture, low water} is an explanation of M, while, e.g., {lean mixture,low water} is not because it does not explain low fuel consumption, and {rich mixture, lean mixture} is not because it is inconsistent with T .

Formalizations of abduction also differ in the literature in the notions of preferred explanations: In this setting, the aim is to compute an explanation that is minimal among all explanations according to some criteria (e.g., inclusion or cardinality). A good overview is given by Eiter and Gottlob [1995]. However we are not concerned here with these different notions; we indeed focus on the decision problem asking whether there exists an explanation at all for a given instance. This problem is from now on denoted ABDUCTION.

This problem is well studied from the computational complexity perspective [Eshghi, 1993; Selman and Levesque, 1990; Eiter and Gottlob, 1995; del Val, 2000b; 2000a; Zanuttini, 2003], although with different formalizations of the problem, as mentioned above. It has been proved that it is ΣP2 -complete in the general case [Eiter and Gottlob, 1995], while propositional deduction is known to be "only" coNPcomplete [Cook, 1971]. This negative result raises the problem of identifying restricted cases in which ABDUCTION has computational complexity lower than the general case.

The most natural way to study such restrictions is to study restrictions on the theories representing knowledge bases. This is also the approach followed in most of the previous research in the area. For example, it is known that when the knowledge base T is a conjunction of Horn clauses, then ABDUCTION is NP-complete [Selman and Levesque, 1990].

The ultimate goal of this line of research is to determine the complexity of every restricted special case of the problem. The first result of this type was proved by Schaefer [1978], who proved that the satisfiability problem of conjunctions of Boolean constraints over a fixed language is either in P or NPcomplete, depending on the language. Recall the result due to Ladner [1975] stating that if P ̸=NP, then there exist decision problems in NP that are neither in P nor NP-complete. Hence the existence of dichotomy theorems like Schaefer's cannot be taken for granted. Creignou et al.'s book [2001] surveys such results.

In this paper we completely classify the complexity of ABDUCTION in Schaefer's framework and exhibit a trichotomy. More precisely, we prove that ABDUCTION is:

• In P if the language is affine of width 2,
• Otherwise, NP-complete if the language is Horn, dual Horn, bijunctive or affine,
• Otherwise, ΣP2 -complete.

As far as we know, the (only) polynomial case and the minimal NP-hard languages that we exhibit are all new results. Note that the only property that guarantees a polynomial algorithm is that of being affine of width 2, i.e., the case where the theory representing the domain is only a conjunction of constants and (in)equalities between two variables. Thus the problem is very hard as soon as sets of literals are allowed as hypotheses and manifestations (instead of atoms or sets of atoms as in, e.g., [Zanuttini, 2003]).

We do not consider directly the complexity of the search problem consisting of computing an explanation or asserting there is none. It is however easily seen that this problem is hard as soon as ABDUCTION is; as for languages that are affine of width 2, our proof that ABDUCTION is in P exhibits an efficient algorithm.

2 Preliminaries

The set of all n-tuples of elements from {0, 1} is denoted by {0, 1}n. Any subset of {0, 1}n is called an n-ary relation on {0, 1}. The set of all finitary relations over {0, 1} is denoted by BR. A constraint language over {0, 1} is an arbitrary finite set Γ ⊆ BR. Constraint languages are the way in which we impose restrictions on the knowledge bases for the ABDUCTION problem.

A constraint over the constraint language Γ is an application of a relation R in Γ to a tuple of variables, written R(x1, . . . , xn) (possibly with repeated variables). An assignment m to the variables satisfies the constraint R(x1, . . . , xn) if (m(x1), . . . ,m(xn)) is a tuple in R. Such a satisfying assignment m is called a model of R(x1, . . . , xn). A theory T over Γ is a conjunction of constraints over Γ; a model m of T is an assignment that satisfies all its constraints simultaneously, denoted m |= T . If there is such a model, T is said to be satisfiable. Finally, a theory T entails a theory T ′ , written T |= T ′ , if every model of T is a model of T ′ .

The unary relations F = {(0)} and T = {(1)}, which force the value of a variable to 0 and 1 respectively, have a special role for the ABDUCTION problem. We will often use the shorthand notation ¬x and x to denote the constraints F(x) and T(x) respectively. Constraint languages containing F and T will be of particular importance to us. Given a constraint language Γ, the idempotent constraint language corresponding to Γ is Γ ∪ {F, T } which is denoted by Γid .

Given a theory T , V ars(T ) denotes the set of all variables that occurs in T . Given a set of variables V , Lits(V ) denotes the set of constraints ⋃x∈V {F(x) ∪ T(x)} or, equivalently, the set of all literals formed upon the variables in V . The opposite of a literal ℓ is written ℓ. Given a set of literals L, their conjunction is denoted by ∧ L.

The ABDUCTION problem restricted to the finite constraint language Γ is denoted by ABDUCTION(Γ) and is defined as follows; the problem is said to be parameterized by Γ.

Problem 2 (ABDUCTION(Γ)) An instance P of

ABDUCTION(Γ) consists of a tuple (V,H,M, T), where:

• V is a set of variables,
• H ⊆ Lits(V ) is the set of hypotheses,
• M ⊆ Lits(V ) is the set of manifestations, and
• T is a theory over Γ with V ars(T ) = V .

The question is whether there exists an explanation for P, i.e., a set E ⊆ H such that T ∧ ∧ E is satisfiable and T ∧ ∧ E |= ∧ M.

The size of P = (V,H,M, T) is the total number of occurrences of variables in it.

Recall the following standard restrictions on the constraint languages (see, e.g. [Creignou et al., 2001]).

Definition 3 (restrictions on Γ)

• Γ is Horn if every relation R in Γ is the set of models of a CNF formula having at most one unnegated variable in each clause,
• Γ is dual Horn if every relation R in Γ is the set of models of a CNF formula having at most one negated variable in each clause,
• Γ is bijunctive if every relation R in Γ is the set of models of a CNF formula having at most two literals in each clause,
• Γ is affine if every relation R in Γ is the set of models of a system of linear equations over GF(2), the field with two elements,
• Γ is affine of width 2 if every relation R in Γ is the set of models of a system of linear equations over GF(2) in which each equation has at most 2 variables.

We emphasize that Γ is assumed to be finite in the definition of ABDUCTION(Γ). Moreover, it parameterizes the problem, and is not part of its input. Thus we can assume any convenient presentation of the relations in Γ is stored in a catalog; thus we will assume, e.g., that if Γ is Horn then a theory T over Γ is given as a CNF formula with at most one unnegated variable per clause.

We now recall Schaefer's result, which will be of great importance throughout the paper. Call SAT(Γ) the problem of deciding whether a given theory over Γ is satisfiable. Schaefer completely classified the complexity of SAT(Γ); we only report the result for idempotent constraint languages.

Theorem 4 ([Schaefer, 1978]) SAT(Γid ) is in P if Γ is Horn, dual Horn, bijunctive or affine. Otherwise it is NP-complete.

Finally, we assume that the reader is familiar with the basic notions of complexity theory, but we briefly recall the following. P is the class of decision problems solvable in deterministic polynomial time. NP is the class of decision problems solvable in nondeterministic polynomial time. ΣP2 = NPNP is the class solvable in nondeterministic polynomial time with access to an NP-oracle. A problem is NP-complete (ΣP2 - complete) if every problem in NP (ΣP2 ) is polynomial-time reducible to it. Throughout the paper we assume P̸=NP̸=ΣP2 .

3 Polynomial case

The following proposition gives the only (maximal) polynomial case of ABDUCTION(Γ). Note that, as mentioned in the introduction, its proof gives a polynomial algorithm that computes an explanation if there exists one.

Throughout the proof we write (ℓ = a) (a ∈ {0, 1}) for the linear equation (x = a) if ℓ = x, and for the linear equation x = a ⊕ 1 if ℓ = ¬x. The shorthand (ℓ = ℓ′ ) is used in the same manner and is equivalent to (ℓ ⊕ ℓ′ = 0).

Proposition 5 If Γ is affine of width 2, then ABDUCTION(Γ) is polynomial.

Proof Let P = (V,H,M, T) be an instance of ABDUCTION(Γ), where Γ is affine of width 2. If M ′ is the set of all manifestations m such that T ̸|= m, then obviously the explanations of P are exactly those of (V, H,M ′ , T ). Since T |= m can be decided efficiently with Gaussian elimination on T ∧ (m = 0), we assume M ′ = M.

For every manifestation m ∈ M write Em for the set of literals {h ∈ H | T |= (h = m)}; once again every Em can be computed efficiently with Gaussian elimination on T ∧ (h ⊕ m = 1) for every h ∈ H. We show that P has an explanation if and only if T ∧ ∧m∈M ∧ Em is satisfiable and no Em is empty. Since the satisfiability of T ∧ ∧m∈M ∧ Em can be decided efficiently with again Gaussian elimination (on T ∧∧m∈M ∧h∈Em (h = 1)), this will conclude the proof.

Assume first P has an explanation E. Then T ∧ ∧ M is consistent; since for every m ∈ M and h ∈ Em we have T |= (h = m), we also have T ∧ ∧ M |= T ∧ ∧m∈M ∧ Em, and thus T ∧ ∧m∈M ∧ Em is satisfiable. Now we also have ∀m ∈ M, T |= (∧ E → m). Since T is affine of width 2 it is bijunctive, thus every clause entailed by T can be minimized into a bijunctive one; since T ∧∧ E is satisfiable and T ̸|= m, the only possibility is a minimal clause of the form h → m with h ∈ E. But since T is affine this implies that m → h also is an implicate of it, and finally we have T |= (h ⊕m = 0), which shows that Em is nonempty. For more details we refer the reader to [Zanuttini and H´ebrard, 2002]. Conversely, assume T ∧ ∧m∈M ∧ Em is satisfiable and no Em is empty. Then since (h ⊕m = 0) |= (h → m) it is easily seen that ∧m∈M ∧ Em is an explanation for P. ✷

4 NP-complete cases

We now exhibit the NP-complete cases of ABDUCTION(Γ). Since T ∧ ∧ E |= ∧ M holds if and only if T ∧ ∧ E ∧ ℓ is unsatisfiable for every ℓ ∈ M, the following result is obvious.

Lemma 6 If SAT(Γid ) is in P, then ABDUCTION(Γ) is inNP.

We first establish NP-completeness for particular languages. In Section 5 we will establish more general results. Let R¬x∨y = {(1, 1), (0, 1), (0, 0)}, i.e., the set of models of ¬x ∨ y. Observe that R¬x∨y is both Horn and dual Horn.

Proposition 7 ABDUCTION({R¬x∨y}) is NP-complete.

Proof Membership in NP follows from Theorem 4 and Lemma 6. As regards hardness, we give a reduction from the NP-complete problem MONOTONE-SAT [Garey and Johnson, 1979], i.e., the satisfiability problem for CNF formulas where each clause contains either only positive literals or only negative literals. Let ψ = ∧ki=1 Ni ∧ ∧ℓi=1 Pi be such a formula, where each Ni is a negative clause, written Ni = ∨νi j=1 ¬xji , and every Pi is a positive clause written Pi = ∨πi j=1 yj i . We build the instance P = (V,H,M, T) of ABDUCTION(R¬x∨y ) where:

• V = {γi | i = 1, . . . , k} ∪ {δi | i = 1, . . . , ℓ} ∪ V ars(ψ); ¬γi will intuitively represent satisfaction of clause Ni and δi, that of clause Pi
• T = ∧ki=1 ∧νi j=1 (xji ∨¬γi)∧ ∧ℓi=1 ∧πi j=1 (¬yj i ∨δi); this encodes the implications ¬xji → ¬γi and yj i → δi, i.e., the fact that Ni (Pi) is satisfied if at least one of the ¬xji (yj i ), j ∈ {1, . . . , νi} (j ∈ {1, . . . , πi}) is
• H = Lits(V ars(ϕ))
• M = ∧ki=1 ¬γi ∧ ∧ℓi=1 δi.

Obviously enough, the theory T is over the language {R¬x∨y}. Now it is easily seen that if ψ has at least one model, say m, then E = {ℓ | m |= ℓ} is an explanation for P, and that if P has an explanation E, then any assignment m to V ars(ψ) with ∀ℓ ∈ E,m |= ℓ is a model of ψ. ✷

Similarly, we now prove that ABDUCTION(Γ) is NPcomplete if Γ is the singleton language containing only Rx∨y = {(1, 1), (1, 0), (0, 1)}.

Proposition 8 ABDUCTION({Rx∨y}) is NP-complete.

Proof Since Rx∨y is dual Horn, membership in NP follows from Theorem 4 and Lemma 6. As for hardness, we give a reduction from MONOTONE-SAT (see the proof of Proposition 7), where positive clauses in an instance of this problem are restricted to contain at most two literals. Thus an instance of this problem is a formula of the form ψ = ∧ki=1 Ni ∧ ∧ℓi=1 (y1 i ∨ y2 i ), where the yj i 's are variables and every Ni is a negative clause written Ni = ∨νi j=1 ¬xji . The NP-completeness of this restricted problem follows directly from Schaefer's result [1978].

Given an instance ψ of MONOTONE-SAT as above we build the instance P = (V,H,M, T) of ABDUCTION({Rx∨y}) where:

• V = {γi | i = 1, . . . , k} ∪ V ars(ψ); γi will intuitively represent satisfaction of clause Ni
• T = ∧ki=1 ∧νi j=1 (xji ∨ γi) ∧ ∧ℓi=1 (y1 i ∨ y2 i ); clauses (xji ∨ γi) encode the implications ¬xji → γi
• H = Lits(V ars(ϕ))
• M = ∧ki=1 γi.

We show that ψ has a model if and only if P has an explanation. Assume first that ψ has a model m; then it is easily seen that E = {ℓ | m |= ℓ} is an explanation for P. Now assume P has an explanation E. Then from ∀i = 1, . . . , k, T ∧ ∧ E |= γi it follows that for every i = 1, . . . , k E contains at least one ¬xji , and thus any assignment satisfying E satisfies every negative clause of ψ; on the other hand, since T ∧ ∧ E is satisfiable there is a model m of T ∧ ∧ E that satisfies every positive clause of ψ, and this m thus satisfies ψ. ✷

The following proposition can be shown with the same proof as Proposition 8 with all variables renamed.

We finally prove that ABDUCTION(Γ) is NP-complete for a particular affine language. This will be achieved by reducing to it another important problem in nonmonotonic reasoning, namely the inference problem for propositional circumscription. A model m = (m1, . . . ,mn) of a formula ϕ is said to be a minimal model of ϕ if there is no model m′ = (m′1 , . . . ,m′n) of ϕ such that m ̸= m′ and ∀i = 1, . . . , n,m′i ≤ mi.

Durand and Hermann proved that the inference problem for propositional circumscription of affine formulas is coNPcomplete. In the process, they proved the following theorem.

Theorem 10 ([Durand and Hermann, 2003]) The problem of deciding whether there is a minimal model of a given affine formula ϕ that does not satisfy a given negative clause (¬q1 ∨ . . . ∨ ¬qn) (∀i = 1, . . . , n, qi ∈ V ars(ϕ)) is NP-complete.

A careful reading of their proof shows that the theorem remains true even if the linear equations in the input affine formulas are all restricted to contain at most 6 variables. We thus define the language Γ6aff to be the set of all k-ary affine relations with k ≤ 6. Obviously, Γ6aff is finite, which is necessary for problem ABDUCTION(Γ6aff ) to be well-defined.

Proposition 11 ABDUCTION(Γ6aff ) is NP-complete.

Proof Membership in NP follows from Theorem 4 and Lemma 6. As for hardness, let ϕ be a formula and q1, . . . , qn ∈ V ars(ϕ). We show that the clause (¬q1 ∨ . . . ∨ ¬qn) is false in some minimal model of ϕ if and only if the abduction problem with T = ϕ, M = {q1, . . . , qn}, and H = {¬x | x ∈ V ars(ϕ)\{q1, . . . , qn}} has an explanation, which will conclude by Theorem 10 and the above remark.

Assume first that (¬q1 ∨ . . . ∨ ¬qn) is false in a minimal model m of ϕ. Define E to be {¬xi | m |= ¬xi}. Since m |= ϕ by assumption and m |= ∧ E by construction, ϕ ∧ ∧ E is satisfiable. Now assume for sake of contradiction that there is m′ satisfying ϕ ∧ ∧ E ∧ (¬q1 ∨ . . . ∨ ¬qn). Then since m′ |= ∧ E andE is negativewe get ∀x ∈ E,m′ (x) ≤m(x); now for x ∈ V ars(ϕ) \ V ars(E) we have by assumption m(x) = 1 and thus m′ (x) ≤ m(x) again. Finally, we have ∃qi,m′ (qi) = 0 < 1 = m(qi), which contradicts the minimality of m. Thus ϕ ∧ ∧ E |= (q1 ∧ . . . ∧ qn) and E is an explanation.

Conversely, assume that E is an explanation. Then ϕ ∧ ∧ E is satisfiable; write m for one of its minimal models. By assumption the formula ϕ ∧ ∧ E ∧ (¬q1 ∨ . . . ∨ ¬qn) is unsatisfiable, thus m ̸|= (¬q1∨. . .∨¬qk). We also have m |= ϕ by assumption. Finally, assume for sake of contradiction that m is not a minimal model of ϕ, and let m′ be such that m′ |= ϕ, m′ ≤ m and m′ ̸= m. Then since E is negative (because H is) and m |= ∧ E we have m′ |= ∧ E, thus m′ |= ϕ∧∧ E, which contradicts theminimality ofmamong the models of ϕ ∧ ∧ E. ✷

5 Classification

We finally put together the results in the previous sections for obtaining our complete classification. The concept of a relational clone is central to our approach.

Definition 12 (relational clone) Let Γ ⊆ BR. The relational clone of Γ is written 〈Γ〉 and is the set of all relations that can be expressed using relations from Γ ∪ {=} (= is the equality relation on {0, 1}), conjunction, and existential quantification.

Intuitively, the constraints over 〈Γ〉 are those which can be simulated by constraints over Γ.

The following result states that when studying the complexity of ABDUCTION(Γ) it is enough to consider constraint languages that are relational clones.

Lemma 13 Let Γ be a finite constraint language and Γ′ ⊆ 〈Γ〉 finite. Then ABDUCTION(Γ′ ) is polynomial-time reducible to ABDUCTION(Γ).

Proof Let (V ′ ,H ′ ,M ′ , T ′) be an instance of ABDUCTION(Γ′ ). By the definition of a relational clone there is a set of variables W disjoint from V ′ and a theory T= over Γ ∪ {=} with V ars(T=) = V= = V ′ ∪ W and such that T ′ is logically equivalent to the formula ∃W, T=. Since W is disjoint from V ′ there is no variable occurring in H ′ or M ′ and in W at the same time, and it is then easily seen that the abduction problem (V=,H ′ ,M ′ , T=) has an explanation if and only if (V ′ ,H ′ ,M ′ , T ′) has one. Now for every constraint (xi = xj) (i < j) it is enough to replace xj with xi everywhere in V=, T=,M ′ and H ′ and to remove the constraint from T= for obtaining a still equivalent instance (V,H,M, T) of ABDUCTION(Γ), which concludes. ✷

We can reduce even further the set of constraints languages to be considered, namely to idempotent ones.

Lemma 14 Let Γ be a finite constraint language. ABDUCTION(Γid ) is polynomial time reducible to ABDUCTION(Γ).

Proof Let P = (V,H,M, T) be an instance of ABDUCTION(Γid ). We build an instance P′ = (V,H ′ ,M ′ , T ′) of ABDUCTION(Γ) by removing every constraint F(x) or T(x) from T and adding it to H and M. It is then easy to see that (V,H ′ ,M ′ , T ′) has an explanation if and only if (V, H, M, T ) has one. ✷

Given these two lemmas, our classification of the complexity of ABDUCTION(Γ) heavily relies on Post's remarkable classification of all Boolean relational clones [Post, 1941]. Post proved in particular that the relational clones form a lattice under set inclusion. An excellent introduction to Post's lattice can be found in the recent survey articles [B¨ohler et al., 2003; 2004].

Lemmas 13 and 14 say that for any finite Γ′ ⊆ 〈Γid 〉, ABDUCTION(Γ′ ) is polynomial-time reducible to ABDUCTION(Γ). In other words, when studying the complexity of ABDUCTION(Γ) it is enough to consider constraint languages that are idempotent relational clones. The lattice of all idempotent Boolean relational clones is given on Figure 1. Those that are most relevant to our classification are the following:

• BR, the set of all Boolean relations,
• IE2, the set of all Horn relations,
• IV2, the set of all dual Horn relations,
• ID2, the set of all bijunctive relations,
• IL2, the set of all affine relations,
• ID1, the set of all affine relations of width 2,
• IM2, the set of all relations that are Horn and dual Horn.

Thus, according to Post's lattice there is only one idempotent relational clone that is not Horn, not dual Horn, not affine, and not bijunctive, namely the relational clone consisting of all Boolean relations BR. Hence the following result follows intuitively from the result due to Eiter and Gottlob [1995] stating that ABDUCTION is ΣP2 -complete for the general case of theories given by CNF formulas.

Proposition 15 If Γ is not Horn, not dual Horn, not affine and not bijunctive then ABDUCTION(Γ) is ΣP2 -complete.

Proof It is well-known that for any CNF formula ψ there is a set of variables W disjoint from V ars(ψ) and a CNF formula ψ′ over V ars(ψ)∪W with at most 3 variables per clause such that the formulas ψ and ∃Wψ′ are logically equivalent. That fact together with a proof similar to that of Lemma 13 show that the abduction problem for general CNF theories reduces to ABDUCTION(Γ3), where Γ3 is the (finite) set of all ternary relations. Since Γ3 is not Horn, not dual Horn, not affine and not bijunctive, we have 〈Γid 3 〉 = BR, and Lemma 13 and Lemma 14 concludes. ✷

We are finally able to completely classify the complexity of ABDUCTION(Γ).

Theorem 16 (classification) Let Γ be a constraint language. ABDUCTION(Γ) is:

• In P if Γ is affine of width 2,
• Otherwise, NP-complete if Γ is Horn, dual Horn, bijunctive or affine,
• Otherwise, ΣP2 -complete.

Proof Proposition 5 shows the result for languages that are affine of width 2. Now it can be seen that the relations R¬x∨y, Rx∨y and R¬x∨¬y of Propositions 7, 8 and 9 are in the relational clones IM2, IS2 02 and IS2 12 , respectively; this can be verified by checking that they are invariant under the operations defining the corresponding clones (for more details see [B¨ohler et al., 2003; 2004]). Moreover, the language Γ6aff of Proposition 11 is affine, thus it is in IL2. Consequently, Figure 1 shows that the minimal idempotent relational clones that are not affine of width 2, namely IM2, IS2 02 , IS2 12 and IL2 are NP-complete. On the other hand, we know from Theorem 4 and Lemma 6 that the relational clones IL2 (affine), ID2 (bijunctive), IE2 (Horn) and IV2 (dual Horn) are in NP. Thus ABDUCTION(Γ) is NP-complete when 〈Γid 〉 contains IM2, IS2 02, IS2 12 or IL2 and is contained in IL2, ID2, IE2, or IV2. This covers exactly the languages that are Horn, dual Horn, bijunctive, or affine and that are not affine of width 2.

Finally, Proposition 15 concludes the proof. ✷

6 Discussion and future work

We have completely classified the complexity of propositional abduction in Schaefer's framework when manifestations and hypotheses are described by sets of literals. This result can prove useful in helping the designers of knowledge based systems to deal with the expressivity/tractability tradeoff when choosing a language for their system. Our result indeed completes the picture of the complexity of reasoning for propositional constraint languages. In particular, we have shown that this problem is very hard, in the sense that only languages that are affine of width 2 allow for polynomial abduction. Also note that in many cases NP-hardness remains even when restricting further the problem; e.g., to H = Lits(V \V ars(M)) (see the proofs of Propositions 79).

It is important to note that the complexity of abduction for a constraint language given in extension (i.e., by the set of all tuples in every relation) can be determined efficiently; the case of Theorem 16 in which a language falls can indeed be determined efficiently by using the closure properties of the concerned co-clones (see, e.g., [B¨ohleret al., 2004]).

It would be interesting to try to extend this work into at least three directions. First of all, besides the problem of deciding the existence of an explanation for a given instance, of great importance are the problems of relevance and necessity, which ask whether a given hypothesis is part of at least one (resp. of all) preferred explanation(s). These problems involve a preference criterion which can have a great impact on their complexity; for more details we refer the reader to [Eiter and Gottlob, 1995]. Hence, it would be interesting to investigate the complexity of these problems. In the same vein, Eiter and Makino recently studied the problem of enumerating all the explanations of a Horn abduction problem [Eiter and Makino, 2002]; it would be interesting to try to extend their work to other classes of formulas.

Secondly, although Schaefer's framework is quite general, there are restrictions on propositional formulas that it cannot express. For instance, Eshghi [1993] and del Val [2000a] study such restrictions that yield polynomial cases of the abduction problem. It would thus be of great interest to try to identify still more such tractable classes.

Finally, it would be interesting to study the case where the domains of variables are more general, e.g., for conjunctions of constraints over finite domains.