Counting Complexity of Propositional Abduction

1 Introduction

Abduction is a method of non-monotonic reasoning which has taken a fundamental importance in artificial intelligence and related topics. It is widely used to produce explanations for observed symptoms and manifestations, therefore it has an important application field in diagnosis - notably in the medical domain (see [12]). Other important applications of abduction can be found in planning, database updates, datamining and many more areas (see e.g. [9; 10; 11]).

Logic-based abduction can be formally described as follows. Given a logical theory T formalizing an application, a set M of manifestations, and a set H of hypotheses, find an explanation S for M, i.e., a suitable set S ⊆ H such that T ∪ S is consistent and logically entails M. In this paper, we consider propositional abduction problems (PAPs, for short), where the theory T is represented by a propositional formula over a Boolean algebra ({0, 1}; ∨, ∧, ¬, →, ≡) or a Boolean field Z2 = ({0, 1};+, ∧), and the sets of hypotheses H together with the manifestations M consist of variables.

Example 1 Consider the following football knowledge base.

T = {weak defense ∨ weak attack→match lost, match lost →manager sad ∧ press angry star injured→manager sad ∧ press sad }

Moreover, let the set of observed manifestations be M = {manager sad, press angry }

Reinhard Pichler

Institut f¨ur Informationssysteme Technische Universit¨at Wien Favoritenstrasse 9-11, A-1040 Wien

Finally, let the set of hypotheses be given as

H = {weak defense, weak attack, star injured }

This PAP has six abductive explanations (= "solutions").

S1 = {weak defense} S2 = { weak attack } S3 = { weak defense, weak attack } S4 = {weak attack, star injured} S5 = {weak defense, star injured} S6 = {weak defense, weak attack, star injured}

Obviously, in the above example, not all solutions are equally intuitive. Indeed, for many applications, one is not interested in all solutions of a given PAP P but only in all acceptable solutions of P. Acceptable in this context means minimal w.r.t. some preorder ⪯ on the powerset 2H . The most natural preorder is subset-minimality ⊆. This criterion can be further refined by a hierarchical organization of our hypotheses according to some priorities (cf. [7]). In this context, priorities can be considered as a qualitative version of probability. The resulting preorder is denoted by ⊆P . On the other hand, if indeed all solutions are acceptable, then the corresponding preorder is the syntactic equality =.

In Example 1, only the solutions S1 and S2 are subsetminimal. Moreover, suppose that for some reason we know that (for a specific team) weak defense is much less likely to occur than weak attack. This judgment can be formalized by assigning lower priority to the former. Thus, only S2 is considered as ⊆P -minimal w.r.t. these priorities.

The usually observed algorithmic problem in logic-based abduction is the existence problem, i.e. deciding whether at least one solution S exists for a given abduction problem P. Another well-studied decision problem is the so-called relevance problem, i.e. Given a PAP P and a hypothesis h ∈ H, is h part of at least one acceptable solution? However, this approach is not always satisfactory. Especially in database applications, in diagnosis, and in data-mining there exist situations where we need to know all acceptable solutions of the abduction problem or at least an important part of them. Consequently, the enumeration problem (i.e., the computation of all acceptable solutions) has received much interest (see e.g. [5; 6]). Another natural question is concerned with the total number of solutions to the considered problem. The latter problem refers to the counting complexity of abduction.

Clearly, the counting complexity provides a lower bound for the complexity of the enumeration problem. Moreover, counting the number of abductive explanations can be useful for probabilistic abduction problems (see e.g. [13]). Indeed, in order to compute the probability of failure of a given component in a diagnosis problem (under the assumption that all preferred explanations are equiprobable), we need to count the number of preferred explanations as well as the number of preferred explanations that contain a given hypothesis.

The counting complexity has been started by Valiant [15; 16] and is now a well-established part of the complexity theory, where the most known class is #P. Many counting variants of decision problems have been proved #P-complete. Higher counting complexity classes do exist, but they are not commonly known. A counting equivalent of the polynomial hierarchy was defined by Hemaspaandra and Vollmer [8], whereas generic complete problems for these counting hierarchy classes were presented in [3].

Results. The goal of this work is to provide a comprehensive analysis of the counting complexity of propositional abduction in various settings. An overview of our results is given in Table 1. The columns of this table correspond to the three preorders on 2H considered here for defining the notion of acceptable solutions, namely equality =, subsetminimality ⊆, and subset-minimality with priorities ⊆P .

Apart from the general case where the theory T is an arbitrary propositional formula, we also consider the subclasses of Horn, definite Horn, dual Horn, bijunctive, and affine theories T . The aforementioned classes enjoy several favorable properties. For instance, they are closed under conjunction and existential quantification, i.e., a conjunction of two formulas from C belongs to the class C and a formula from C with an existentially quantified variable is logically equivalent to another formula fromC. Moreover, they represent the most studied formulas in logic, complexity, constraint satisfaction problems, and artificial intelligence. This is mainly due to Schaefer's famous result that the satisfiability problem for them is polynomial as opposed to the NP-completeness of the general case (see [14]).

Structure of the Paper. The paper is organized as follows. After recalling some basic definitions and results in Section 2, we analyze the counting complexity of propositional abduction for general theories (Section 3), for Horn, definite Horn, dual Horn and bijunctive theories (Section 4) and finally for affine theories (Section 5). We conclude with Section 6.

2 Preliminaries

2.1 Propositional Abduction

A propositional abduction problem (PAP) P consists of a tuple 〈V, H, M, T 〉, where V is a finite set of variables, H ⊆ V is the set of hypotheses, M ⊆ V is the set of manifestations, and T is a consistent theory in the form of a propositional formula. A set S ⊆ H is a solution (also called explanation) to P if T ∪ S is consistent and T ∪ S |= M holds. Priorities P = 〈H1, . . . ,HK〉 are a stratification of the hypotheses H = H1 ∪ · · · ∪HK into a fixed number of disjoint sets. The subset-minimality with priorities relation A ⊆P B holds if A = B or there exists an i ∈ {1, . . . ,K} such that A∩Hj = B ∩Hj for all j < i and A∩Hi ⊊ B ∩Hi.

In this paper, we follow the formalism of Eiter and Gottlob [4], allowing only positive literals in the solutions, except for the affine case. In contrast, Creignou and Zanuttini [1] also allow negative literals in the solutions S. We apply the latter to affine PAPs, where we need the possibility in the algebraic setting to assign a variable to 0.

Together with the general case where T can be an arbitrary propositional formula, we consider the special cases where T is Horn, definite Horn, dual Horn, bijunctive, and affine. Due to Schaefer's famous dichotomy result (see [14]), these are the most frequently studied sub-cases of propositional formulas. A propositional clause C is said to be Horn, definite Horn, dual Horn, or bijunctive if it has at most one positive literal, exactly one positive literal, at most one negative literal, or at most two literals, respectively. A clause C is affine if it can be written in the form of a linear equation x1 + · · · + xk = b over the Boolean field Z2. A theory T is Horn, definite Horn, dual Horn, bijunctive, or affine if it is a conjunction (or, equivalently, a set) of Horn, definite Horn, dual Horn, bijunctive, or affine clauses, respectively.

2.2 Counting Complexity

The #-abduction problem is the problem of counting the number of solutions of a PAP P. The #-⊆-abduction problem counts the subset-minimal solutions of P, whereas #-⊆Pabduction counts the minimal solutions w.r.t. priorities P .

Formally, a counting problem is presented using a witness function which for every input x returns a set of witnesses for x. A witness function is a function w : Σ∗ → P <ω (Γ∗ ), where Σ and Γ are two alphabets, and P <ω (Γ∗ ) is the collection of all finite subsets of Γ∗ . Every such witness function gives rise to the following counting problem: given a string x ∈ Σ∗ , find the cardinality |w(x)| of the witness set w(x). According to [8], if C is a complexity class of decision problems, we define #·C to be the class of all counting problems whose witness function w satisfies the following conditions.

1. There is a polynomial p(n) such that for every x ∈ Σ∗ and every y ∈ w(x) we have |y| ≤ p(|x|);
2. The problem "given x and y, is y ∈ w(x)?" is in C.

It is easy to verify that #P = #·P. The counting hierarchy is ordered by linear inclusion [8]. In particular, we have that

#P ⊆ #·coNP ⊆ #·Π2P ⊆ #·Π3P, etc. Note that one can, of course, also consider the classes #·NP, #·Σ2P, #·Σ3P, etc. However, they play no role in this work.

The prototypical #·ΠkP-complete problem for k ∈ N is #ΠkSAT [3], defined as follows. Given a formula

where ϕ is a Boolean formula and X, Y1, . . . , Yk are sets of propositional variables, count the number of truth assignments to the variables in X that satisfy ψ.

Completeness of counting problems in #P is usually proved by means of Turing reductions. However, these reductions do not preserve the counting classes #·ΠkP. It is therefore better to use subtractive reductions [3] which preserve the aforementioned counting classes. We write #·R to denote the following counting problem: given a string x ∈ Σ∗ , find the cardinality |R(x)| of the witness set R(x) associated with x. The counting problem #·A reduces to #·B via a strong subtractive reduction if there exist two polynomialtime computable functions f and g such that for each x ∈ Σ∗ :

A strong subtractive reduction with B(f(x)) = ∅ is called parsimonious. A subtractive reduction is a transitive closure of strong subtractive reductions.

3 General Propositional Theories

The decidability problem of propositional abduction was shown to be Σ2P-complete in [4]. The hardness part was proved via a reduction from QSAT2. A modification of this reduction yields the following counting complexity result.

Theorem 2 The #-abduction problem and the #-⊆-abduction problem are #·coNP-complete.

Proof: The #·coNP-membership is clear by the fact that it is in Δ2P to test whether a subset S ⊆ H is a solution (resp. a subset-minimal solution) of a given PAP (see [4], Proposition 2.1.5). The #·coNP-hardness is shown via the following parsimonious reduction from #Π1SAT. Let an instance of the #Π1SAT problem be given by a formula

with X = {x1, . . . , xk} and Y = {y1, . . . , yl}. Moreover, let x′1, . . . , x′k , r1, . . . , rk, t denote fresh, pairwise distinct variables and let X ′ = {x′1 , . . . , x′k } and R = {r1, . . . , rk}. We define the PAP P = 〈V, H, M, T 〉 as follows.

Obviously, this reduction is feasible in polynomial time. We now show that the reduction is indeed parsimonious.

The manifestations R together with the formulas xi → ri , x′i → ri in T enforce that in every solution S of the PAP, we have to select at least one of xi and x′i . The additional formula ¬xi ∨ ¬x′i enforces that we have to select at most one of xi and x′i . By these two conditions, the value of x′i is fully determined by xi, namely x′i is the dual of xi.

Moreover, it is easy to check that there is a one-to-one relationship between the solutions S ⊆ X of P and the models of ∀Y ϕ(X, Y ). Hence, this reduction is indeed parsimonious. The complementarity of X and X ′ enforces each solution to be incomparable with the others and, therefore, to be subsetminimal. ✷

According to the above theorem, #-abduction and #-⊆- abduction have the same counting complexity. Intuitively, this is due to the following equivalence (cf. [4]): S is a ⊆- minimal solution of the PAP P, if and only if S is a solution of P and for every h ∈ S, S ∖ {h} is not a solution. Hence, taking the ⊆-minimality into account makes things only polynomially harder. In contrast, as soon as there are at least 2 priority levels, the following effect may occur. Suppose that S is a solution of the PAP and that S ∖ {h} is not a solution for every h ∈ S. Then it might well happen that, for some h ∈ S, some set of the formS ′ = (S∖{h})∪X is a solution, where all hypotheses in X have higher priority than h. Checking if such a set S ′ (and, in particular, if such a set X) exists comes down to yet another non-deterministic guess. Formally, we thus get the following complexity result.

Theorem 3 The #-⊆P-abduction problem is #·Π2P-complete via subtractive reductions.

Proof: The ⊆P -minimal solutions of a PAP can obviously be computed by a non-deterministic polynomial-time Turing machine that generates all subsets S ⊆ H and (i) checks whether S is a solution of the PAP and (ii) if so, checks whether S is ⊆P -minimal. The latter test - which is the most expensive part - can be done by a Π2P-oracle. Indeed, the problem of testing that S is not ⊆P -minimal can be done by the following Σ2P-algorithm: guess a subset S ′ ⊆ H s.t. S ′ is ⊆P -smaller than S and check that S ′ is a solution of the PAP. Hence, the #-⊆P -abduction problem is in #·Π2P.

The #·Π2P-hardness is shown by the following (strong) subtractive reduction from#Π2SAT. Let an instance of the #Π2SAT problem be given by a formula

with the variables X = {x1, . . . , xk}, Y = {y1, . . . , yl}, and Z = {z1, . . . , zm}. Moreover, let x′1 , . . . , x′k , p1, . . . , pk, y′1, . . . , y′ l , q1, . . . , ql, r, t be fresh, pairwise distinct variables and X ′ = {x′1 , . . . , x′k }, P = {p1, . . . , pk}, Y ′ = {y′1, . . . , y′ l }, and Q = {q1, . . . , ql}. Then we define two PAPs P1 and P2 as follows.

Finally we set P1 = 〈V, H, M, T1〉 and P2 = 〈V, H, M, T2〉.

Obviously, this reduction is feasible in polynomial time. Now let A(ψ) denote the set of all satisfying assignments of a #Π2SAT-formula ψ and let B(P) denote the set of ⊆P - minimal solutions of a PAP P. We claim that the above definition of the PAPs P1 and P2 is indeed a (strong) subtractive reduction, i.e. that

Due to lack of space, the proof of this claim is omitted. ✷

4 Horn, Dual Horn, and Bijunctive Theories

In this section, we consider the special case where the theory T is a set of (arbitrary or definite) Horn, dual Horn, or bijunctive clauses. If no minimality criterion is applied to the solutions then we get the following result.

Theorem 4 The #-abduction problem of Horn, definite Horn, dual Horn, or bijunctive clauses is #P-complete.

Proof: The #P-membership is easily seen by the fact that it can be checked in polynomial time whether some subset S ⊆ H is a solution, since the satisfiability and also the unsatisfiability of a set of (dual) Horn or bijunctive clauses can be checked in polynomial time.

For the #P-hardness, we reduce the #POSITIVE-2SAT problem (which is known to be #P-complete by [16]) to it and show that this reduction is parsimonious. Let an arbitrary instance of #POSITIVE-2SAT be given as a 2CNF-formula

where the pi's and qi's are propositional variables from the set X = {x1, . . . , xk}. Moreover, let g1, . . . , gn denote fresh, pairwise distinct variables and let G = {g1, . . . , gn}. Then we define the PAP P = 〈V, H, M, T 〉 as follows.

Obviously, this reduction is feasible in polynomial time. Moreover, it is easy to check that there is a one-to-one relationship between the solutions S ⊆ X of P and the models of ψ. Note that the clauses in T are at the same time definite Horn, bijunctive, and dual Horn. ✷

Analogously to the case of general theories, the counting complexity remains unchanged when we restrict our attention to subset-minimal solutions.

Theorem 5 The #-⊆-abduction problem of Horn, definite Horn, dual Horn, or bijunctive clauses is #P-complete.

Proof: The #P-membership holds analogously to the case of abduction without subset-minimality. This is due to following property (see [4], Proposition 2.1.5). S ⊆ H is a subsetminimal solution of P, if and only if S is a solution and for all h ∈ S, the set S ∖ {h} is not a solution of P.

For the #P-hardness, we modify the reduction from the #POSITIVE-2SAT problem in Theorem 4. Let ψ, X, and G be defined as before. Moreover, let X ′ = {x′1, . . . , x′k } and R = {r1, . . . , rk} be fresh, pairwise distinct variables. Then we define P = 〈V, H, M, T 〉 as follows.

The idea of the variables X ′ and the additional manifestations G is exactly the same as in the proof of Theorem 2.

Actually, the formula ¬xi ∨¬x′i can even be omitted. This is due to the fact that, whenever a subset S ⊆ H with xi, x′i ∈ S is a solution of P, then S ∖ {x′i} is also a solution since x′i is useless as soon as xi is present (note that the only use of x′i is to derive ri in the absence of xi). Therefore in a subsetminimal solution of the PAP P, we will never select both xi and x′i even without the formula ¬xi ∨ ¬x′i . The remaining formulas are indeed definite Horn and dual Horn. ✷

Below we consider PAPs with ⊆P -minimality. It turns out that for definite Horn and dual Horn clauses, the priorities leave the counting complexity unchanged. In all other cases, the counting complexity increases.

Theorem 6 The #-⊆P -abduction problem of definite Horn and of dual Horn clauses is #P-complete.

Proof: The #P-hardness is clear, since it holds even without priorities. The #P-membership for definite Horn clauses is proved as follows. Let P = 〈V,H,M, T〉 where T consists only of Horn clauses. According to [4], Theorem 5.3.3, for any S ⊆ H, we can check in polynomial time whether S is a ⊆P -minimal solution. The #P-membership for definite Horn clauses is thus proved.

Now suppose that T is dual Horn, i.e. the clauses in T are either of the form ¬p or ¬p ∨ q1 ∨ · · · ∨ qm, or q1 ∨ · · · ∨ qm (for p, q1, . . . , qm ∈ V and m ≥ 1). Moreover, let N denote the propositional variables occurring in negative unit clauses in T , i.e. N = {p | ¬p ∈ T}. Then for every solution S of P we have S ⊆ H ∖ N, since otherwise T ∪ S would be inconsistent. Moreover, for any S′ with S ⊆ S ′ ⊆ H ∖N, the set S ′ is also a solution of P, since (by the special form of dual Horn) S ′ ∪T is also consistent and (by the monotonicity of |=) S ′ ∪T also implies M.

Let H1, . . . ,HK denote the priorities of H. Now S is a ⊆P -minimal solution of P if and only if S is a solution of P and for all i ∈ {1, . . . , k} and for all x ∈ (S ∩Hi) the set

is not a solution of P. The latter test is clearly feasible in polynomial time in the dual Horn case. ✷

Recall from our remark preceding Theorem 3 that the effect of at least 2 priority levels is as follows. In order to check that some solution S is not ⊆P -minimal, we have to test that there exists some solution of the form S ′ = (S ∖ {h}) ∪ X, where all hypotheses in X have higher priority than h. In general, the difficulty of determining if such a set X exists is the following one. If we choose X too small, then S ′ might not entail the manifestations M. If we choose X too big, then S ′ ∪ T might be inconsistent. The intuition underlying Theorem 6 is that the problem of choosing X too big disappears for definite Horn and dual Horn clauses. For definite Horn, the only candidate X that has to be checked is X = Hi+1 ∪ · · · ∪HK. For dual Horn, the only candidate X is X = (Hi+1 ∪ · · · ∪HK) ∩N, where N takes care that if the theory T contains a negative unit clause ¬p, then p must not be included in any solution.

Theorem 7 The #-⊆P-abduction problemof Horn or bijunctive clauses is #·coNP-complete.

Proof: The #·coNP-membership is established as follows: Given a set of variables S, we have to (i) check whether S is a solution of the PAP and (ii) if so, check whether S is ⊆P - minimal. The latter test, which dominates the overall complexity, can be done by a coNP-oracle. Indeed, the problem of testing that S is not ⊆P-minimal can be done by the following NP-algorithm: guess a subset S ′ ⊆ H s.t. S ′ is ⊆P - smaller than S and check (in polynomial time for a Horn or bijunctive theory), that S ′ is a solution of the PAP. Hence, in this case, #-⊆P -abduction in #·coNP.

The #·coNP-hardness is shown by a (strong) subtractive reduction from #Π1SAT. Let an instance of the #Π1SAT problem be given by a formula ψ(X) = ∀Y ϕ(X, Y ) with X = {x1, . . . , xk} and Y = {y1, . . . , yl}. W.l.o.g. (see [17]), we may assume that ϕ(X, Y ) is in 3DNF, i.e., it is of the form C1 ∨ · · · ∨ Cn where each Ci is of the form Ci = li1∧li2∧li3 and the lij 's are propositional literals over X∪Y .

Let x′1 , . . . , x′k , p1, . . . , pk, y′1 , . . . , y′ l , q1, . . . , ql, g1, . . . , gn, r, t denote fresh, pairwise distinct variables and let X ′ = {x′1 , . . . , x′k }, Y ′ = {y′1 , . . . , y′ l }, P = {p1, . . . , pk}, Q = {q1, . . . , ql} and G = {g1, . . . , gn}. Then we define two PAPs P1 and P2 as follows.

where zij is either of the form xk, x′k , yl, or y′ l depending on whether the literal lij in Ci is of the form¬xk, xk, ¬yl, or yl, respectively. In other words, zij encodes the dual of lij.

Obviously, this reduction is feasible in polynomial time. Now let A(ψ) denote the set of all satisfying assignments of a #Π1SAT-formula ψ and let B(P) denote the set of ⊆P - minimal solutions of a PAP P . We claim that P1 and P2 have the following property.

Due to lack of space, the proof of this claim is omitted. ✷

5 Affine Theories

In this section, we consider the special case where the theory T is a set of affine clauses. Recall that such a set can be written as a linear system AX = b over the Boolean field Z2. We change to the Creignou and Zanuttini approach [1] in this case, since we need the possibility to set a variable to 0. If no minimality criterion is applied to the solutions then we get the following result.

Theorem 8 The #-abduction of affine clauses is in FP.

Proof: Given an affine PAP P = 〈V, H, M, T 〉 where T is an affine system AX = b, we reduce it to the problem of counting the satisfying assignments of linear systems over Z2. Recall that T ∪ S |= M means that x = 1 for each x ∈ S and x = 0 for each x ∈ H ∖ (S ∪ M) entails y = 1 for each y ∈ M in the system T . First we check whether T ∪ S |= M can hold. If V ∖(H∪M) is nonempty then P has no solution, since we cannot force all y ∈ M to y = 1. Otherwise transform the system AX = b to EY = b +FZ, where Y ⊆ M and Z ∩ M = ∅, such that EY + FZ = AX. Transform EY by Gaussian elimination to Smith normal form giving E′Y ′ . If E′ Y ′ has a row with more than one variable, say yi1 + · · · + yil for l ≥ 2, then either P has no solution, or each solution S compatible with yi1 = · · · = yil = 1 is also compatible with yij = 0 for some j ∈ {1, . . . , l}. If E′Y ′ has only rows with one variable, then add to AX = b the equations y = 1 for each y ∈ M, resulting in the new system A′X = b′ . Check whether the last system is satisfiable and transform it by Gaussian elimination into the Smith normal form (I B)X = b′′ . Each truth assignment I of the variables H ∖M satisfying the linear system determines a solution S of P, i.e., S = {y ∈ H | I(y) = 1} ∪ {¬y | I(y) = 0}. Let the linear system (I B)X = b′′ have k rows. Then there are 2|H∖M|-k different solutions of P. ✷

Theorem 9 The #-⊆-abduction problem of affine clauses is #P-complete.

Proof: The #P-membership is clear from the fact that it can be checked in polynomial time whether a set S ⊆ H is a subset-minimal solution of an affine system according to Proposition 1 in [2]. The problem of minimal affine extension, namely that given an affine system AX = b and a partial assignment s to the variables X, count the number of extensions s which are minimal solutions of AX = b, is proved to be #P-complete in [2] even if the partial assignment contains no 0. There is a parsimonious reduction to an affine PAP P = 〈V,H,M, T〉 as follows. Let V = H = X, M = {xi ∈ X | s(xi) = 1}, and T = {AX = b}. Let Y ⊆ X be the variables not assigned by s and let ¯ s be an extension of s satisfying the affine system. Then the set of variables S = {xi ∈ Y | ¯ s(xi) = 1} is a subset-minimal solution of P if and only if the extension ¯ s is minimal. ✷

Theorem 10 The #-⊆P -abduction problem of affine clauses is #P-complete.

Proof: The #P-hardness is clear, since it holds without priorities. The #P-membership for affine clauses is proved as follows. Let P = 〈V,H,M, T〉 where T is a linear system AX = b over Z2. Let H1, . . . , HK denote the priorities of H. Now S is a ⊆P -minimal solution of P if and only if S is a solution of P, there exists an i ∈ {1, . . . , k} such that S ∩Hi is subset-minimal , and for each j < i and all other solutions S ′ of P we have S ∩ Hj = S ′ ∩Hj. We can decide in polynomial time if S ∩Hi is a subset minimal solution of an affine system. The second condition is tested in polynomial time as follows. For each j < i we set the variables H ∖Hj in the system AX = b equal to 0, resulting in a systemA′j Yj = b′j . Then the identity S ∩Hj = S ′ ∩Hj holds if and only if the resulting system A′j Yj = b′j has at most one solution, what can be tested in polynomial time. Hence the overall test can be performed in polynomial time. ✷

6 Conclusion

Eiter and Gottlob proved in [4] a plethora of complexity results for propositional abduction. Their results were extended to a trichotomy of PAPs without minimality-criterion by Creignou and Zanuttini [1]. The use of complexity results is usually twofold. Theoretically, they give us a better understanding of the nature of the considered problem class. Practically, they give us a hint as to which subclass of the problem we should aim at, provided that the application in mind admits such a restriction. In this sense, the counting complexity results shown here are important in complementing the already known decision complexity results. Note that our results reveal significant differences between the counting complexity behavior of PAPs and the decision complexity. For instance, definite Horn abduction and bijunctive abduction were shown to be tractable in [1]. In contrast, by our Theorem 4, the corresponding counting problems are #Pcomplete. This is one more example of the often observed "easy to decide, hard to count" phenomenon.

From a complexity theoretic point of view, there is another interesting aspect to the counting complexity results shown here. The class #P has been studied intensively and many completeness results for this class can be found in the literature. In contrast, for the higher counting complexity classes #·ΠkP (with k ≥ 1), very few complete problems are known apart from the generic problems#ΠkSAT. In fact, to the best of our knowledge, our #·Π2P-completeness result in Theorem 3 is the first one apart from#Π2SAT.

In this work, we have considered the complexity of determining the number of all ⪯-minimal explanations of a propositional abduction problem, where ⪯ ∈ {=,⊆,⊆P}. Note that in [4], complexity problems related to abduction with further notions of minimality were analyzed, namely "minimal cardinality" with or without priorities and "minimal weight". Abduction with "minimal weight" can also be considered as cost-based abduction. We are planning to extend our counting complexity analysis to these notions of minimality.