In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), C. Mellish ed, Morgan Kaufman, 1995. In press.

Semantics and Complexity of Abduction from Default Theories

(Extended abstract^{∗})

Thomas Eiter, Georg Gottlob Christian Doppler Lab for Expert Systems

Technical University of Vienna Paniglgasse 16, A-1040 Wien, Austria

(eiter|gottlob)@dbai.tuwien.ac.at

Nicola Leone^{†}

Istituto per la Sistemistica e l’Informatica C.N.R. c/o DEIS – University of Calabria

87036 Rende, Italy

               nik@si.deis.unical.it

Abstract

Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we analyze the complexity of the main abductive reasoning tasks. They are intractable in the general case; we also present known classes of default theories for which abduction is tractable.

1 Introduction

Abductive reasoning has been recognized as an important principle of common-sense reasoning having fruitful applications in a number of areas such diverse as modelbased diagnosis [Poole, 1989], speech recognition [Hobbs et al., 1988], maintenance of database views [Kakas and Mancarella, 1990], and vision [Charniak and McDermott, 1985]. Until now, mainly abduction from theories of classical logic has been studied. However, logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription. Thus, in such situations it is necessary to perform abductive reasoning from theories (i.e. knowledge bases) of nonclassical logics.

Since default logic is widely proposed for knowledge representation, it is important to investigate how abduction can be performed from theories ⟨W, D⟩ in default logic. We informally pursue this on an example. Example 1 Consider the following set of default rules, which represent knowledge about Bill’s skiing habits:

D =\{ \frac{: ¬skiing Bill}{¬skiing Bill} , \frac{weekend : ¬snowing}{skiing Bill} , \frac{: ¬snowing}{¬snowing} \}

The defaults intuitively state the following: (i) Bill is usually not out for skiing; (ii) Bill is out for skiing on weekends, if we can assume that it is not snowing; (iii) usually it is not snowing. For the certain knowledge W = { weekend } (encoding that it is Saturday or Sunday), the default theory T = ⟨W, D⟩ has one extension which contains ¬snowing and skiing Bill.

Suppose now we observe that Bill is not out for skiing (which is inconsistent with the extension). Abduction means to find an explanation for this observation, that is, to identify a set of facts, chosen from a set of hypotheses, whose presence in the theory at hand would entail the observation ¬skiing Bill, i.e., cause that ¬skiing Bill is in the extension. We find such an explanation by adopting the hypothesis snowing. Indeed, if we add snowing to W, the default theory T′ = ⟨{ weekend, snowing }, D⟩ has a single extension, which contains ¬skiing Bill. We say that snowing is abduced from the observation ¬skiing Bill, or that it is an abductive explanation of ¬skiing Bill. Observe that the description of the above situation requires the specification of some default properties that can not be represented properly in classical logic.

In general, as opposed to the example, a default theory may have several or even no extensions. For deductive entailment, this gives rise to credulous entailment, under which ϕ is entailed from a default theory T (denoted T ⊢_{c} ϕ) iff ϕ belongs to at least one extension of T, and to skeptical entailment, under which ϕ follows from T (T ⊢_{s} ϕ) iff ϕ belongs to all extensions of T. Accordingly, two variants of abduction from default theories arise: credulous abduction, where entailment of an observation is based on ⊢_{c}, and skeptical abduction, which is based on ⊢_{s}. In practice, the user will choose credulous or skeptical abduction on the basis of the particular application domain.

We argue that credulous abduction is well suited for diagnosis, while skeptical abduction is adequate for planning. (Cf. [Poole, 1989] and [Eshghi, 1988; Ng and Mooney, 1991] for abduction in logic-based diagnosis and planning & plan recognition, respectively.) In fact, consider a system represented by a default theory ⟨W, D⟩. If it receives some input, reflected by adding a set A of facts to W, then each extension of ⟨W ∪ A, D⟩ is a possible evolution of the system, i.e., each extension represents a possible reaction of the system to A.

∗A more elaborate version including proofs is available on email request to the authors.

†Work carried out while visiting the Christian Doppler Lab.

Abductive diagnosis consists, loosely speaking, in deriving from an observed system state (characterized by the truth of a set F of facts), a suitable input A which caused this evolution (cf. [Poole, 1989]). Now, since each extension of ⟨W ∪ A, D⟩ is a possible evolution of the system with input A, we can assert that A is a possible input that caused F if ⟨W ∪ A, D⟩ ⊢_{c} F. Thus, diagnostic problems can be naturally represented by abductive problems with credulous entailment.

Example 2 Assume there are two sky routes, rv1 and rv2, between Rome and Vienna, and three sky routes mv1, mv2, and mv3 between Milan and Vienna. Route mv1 intersects route rv1, and mv2 intersects rv2. On normal speed and flight conditions, two planes from Milan and Rome to Vienna will collide if the plane from Milan takes off 20 minutes after the plane from Rome and they fly on intersecting routes. This knowledge about possible collisions is represented in simplified form by the following set D of propositional defaults:

D = \{ \frac{mv1 ∧ rv1 ∧ m 20min later : collision}{collision},

\frac{mv2 ∧ rv2 ∧ m 20min later : collision}{collision},

\frac{: ¬collision}{¬collision}, \frac{: ¬rv1}{¬rv1},

\frac{: ¬rv2}{¬rv2}, \frac{: ¬mv1}{¬mv1}, \frac{: ¬mv2}{¬mv2}, \frac{: ¬mv3}{¬mv3} \}

Now, you are informed that planes flying from Milan and Rome to Vienna collided. A diagnosis for the collision can be obtained by abducing an explanation for the observation collision from the theory T = ⟨∅, D⟩. In this case, we want to know possible flight schedules that can have caused the collision. In other words, we are looking for schedules S such that collision is in some extension of the theory T′ = ⟨S, D⟩ (T′ ⊢_{c} collision). Credulous abduction correctly identifies such explanations. For instance, it is easy to recognize that both E1 = {mv1, rv1, m 20min later} and E2 = {mv2, rv2, m 20min later} are credulous explanations for collision.

Suppose now we want that the system evolves into a certain state (described by a set F of facts), and we have to determine the “right” input that enforces this state of the system (planning). In this case it is not sufficient to choose an input A such that F is true in some possible evolution of the system; rather, we look for an input A such that F is true in all possible evolutions, as we want be sure that the system reacts in that particular way. In other words, we look for A such that ⟨W ∪ A, D⟩ ⊢_{s} F. Hence, planning activities can be represented by abductive problems with skeptical entailment.

Example 3 We know that a plane from Rome to Vienna left at 7.50 (r 7.50), but we do not know on which route. We have to schedule the flight of a plane from Milan to Vienna, where takeoff is possible at 8.10 (m 8.10) and at 8.20 (m 8.20). The collision-free schedules can be obtained by finding an abductive explanation out of the hypotheses m 8.10, m 8.20, mv1, mv2, mv3 for the observation ¬collision from the theory T = ⟨W, D1⟩,

W = { r 7.50, rv1 ∨ rv2, m 8.10 ∨ m 8.20,
mv1 ∨ mv2 ∨ mv3,
r 7.50 ∧ m 8.10 ⊃ m 20min later }
D1 = D ∪ \{ \frac{: ¬m 8.10}{¬m 8.10}, \frac{: ¬m 8.20}{¬m 8.20} \}

As we can not risk a collision, we want that every possible evolution of the system is collision-free. Thus, we have to look for skeptical explanations of ¬collision. For instance, both E3 = {m 8.20} and E4 = {mv3} are skeptical explanations for ¬collision; that is, takeoff at 8.20 or using route mv3 prevents a collision, where the route in E3 and the time in E4 can be chosen freely.

The two examples above support the intuition that credulous abduction is feasible for diagnosis, while skeptical abduction is well-suited for planning. On the other hand, Section 4 shows that skeptical abduction has most likely a higher complexity than credulous abduction; thus, from the above point of view, planning is most likely harder than diagnosis.

For space reasons, we only present some proof sketches. Proofs of all results are given in the full paper.

2 Preliminaries and Notation

We assume that the reader knows the basic concepts of default logic [Reiter, 1980] (cf. also [Marek and Truszczyński, 1993] for an extensive study). We focus on propositional default theories T = ⟨W, D⟩ over a propositional language L (including ⊥ for falsity), i.e. W is a subset of L and D a set of defaults \frac{α:β_{1},...,β_{m}}{γ}, m ≥ 1 where α, β_{1}, …, β_{m}, γ are from L. The extensions of T, which are deductively closed sets E ⊆ L, are defined by a fixpoint equation; in particular, L is an extension of T (and, in this case, unique) iff W is not consistent. Recall that T is normal iff each default in D is normal, i.e., of form \frac{α:β}{β}; a normal T always has an extension.

For NP-completeness and complexity theory, cf. [Johnson, 1990]. The classes Σ_{k}^{P} and Π_{k}^{P} of the polynomial hierarchy are defined as follows: Σ_{0}^{P} = Π_{0}^{P} = P, and

Σ_{k}^{P} = NP^{Σ_{k−1}^{P}}, Π_{k}^{P} = co-Σ_{k}^{P} , for all k ≥ 11.

In particular, NP = Σ_{1}^{P} and co-NP = Π_{1}^{P}. The class D_{k}^{P}, which is defined as the class of problems that consist of the conjunction of two (independent) problems from Σ_{k}^{P} and Π_{k}^{P}, respectively, is considered to be further restricted in computational power. For all k ≥ 1, clearly Σ_{k}^{P} ⊆ D_{k}^{P} ⊆ Σ_{k+1}^{P}; both inclusions are believed to be strict. Many nonmonotonic reasoning problems are complete for classes at the lower end of the polynomial hierarchy [Cadoli and Schaerf, 1993; Nebel, 1994]. It is well-known that deciding whether a propositional default theory has an extension is Σ_{2}^{P} - complete, and that credulous and skeptical reasoning from default theories are complete for Σ_{2}^{P} and Π_{2}^{P}, respectively. This remains true if inconsistent extensions are excluded and, for the latter problems, if default theories are in addition normal [Gottlob, 1992; Stillman, 1992]. Cases of lower complexity and tractable fragments were identified in [Kautz and Selman, 1991; Stillman, 1990].

3 Formalizing default abduction

In this section, we describe a basic formal model for abduction from propositional default theories and state the main decisional reasoning tasks for abductive reasoning.

Our formalization of an abduction scenario is as follows.

Definition 1 A propositional default abduction problem (PDAP) is a quadruple ⟨H, M, W, D⟩ where H is a set of propositional literals (called hypotheses, or abducibles), M is a set of propositional literals (observations, or manifestations), and ⟨W, D⟩ is a propositional default theory. P is normal iff each default in D is normal.

Note that hypotheses and manifestations may be literals rather than atoms. Allowing literals as hypotheses is common in abduction, cf. [Selman and Levesque, 1990]. However, this has no effect on the expressive power or complexity of the formalism in general.

Credulous and skeptical explanations are as follows.

Definition 2 Let P = ⟨H, M, W, D⟩ be a PDAP, and let E ⊆ H. Then, E is a credulous explanation for P iff (i) ⟨W ∪ E, D⟩ ⊢_{c} M, and (ii) ⟨W ∪ E, D⟩ has a consistent extension. Similarly, E is a skeptical explanation for P iff (i) ⟨W ∪ E, D⟩ ⊢_{s} M and (ii) ⟨W ∪ E, D⟩ has a consistent extension.

The existence of a consistent extension for ⟨W ∪E, D⟩ (in this case, all extensions are consistent) assures that the explanation E is consistent with the knowledge represented in ⟨W, D⟩. This is analogous to the consistency criterion in abduction from classical theories.

It is common in abductive reasoning to prune the set of all explanations and to focus, guided by some principle of explanation preference, on a set of preferred explanations. The most important such principle is, following Occam’s principle of parsimony, to prefer nonredundant explanations, i.e., explanations which do not contain any other explanation properly, cf. [Peng and Reggia, 1990; Selman and Levesque, 1990; Konolige, 1992]. We refer to such explanations as minimal explanations. In Example 3 E3 = {m 8.20} and E4 = {mv3} are the minimal explanations; they represent the smallest partial schedules that can be arbitrarily completed to collision-free schedules, and thus provide the greatest flexibility.

In the sequel, we will write Exp(P) for the set of explanations for the PDAP P, abstracting from the chosen type of explanations (credulous, skeptical, minimal credulous, or minimal skeptical).

The following properties of a hypothesis in a PDAP P are important with respect to computing explanations.

Definition 3 Let P = ⟨H, M, W, D⟩ be a PDAP and h ∈ H. Then, h is relevant (resp. necessary) for P iff h ∈ E for some (resp. every) E ∈ Exp(P).

The opposite of necessity is also termed dispensability (cf. [Josephson et al., 1987]). In Example 2, m 20min later is necessary, while each hypothesis rv1, rv2, mv1, mv2 is relevant, but not necessary. Moreover, in Example 3 mv3 is relevant w.r.t. minimal (skeptical) explanations, but not necessary. Note that in the same example rv1 is relevant under arbitrary explanations, but not relevant under minimal explanations.

The main decisional problems in abductive reasoning amount to the following. Given a PDAP P = ⟨H, M, W, D⟩,

(Consistency): does there exist an explanation for P? (Relevance): is a given hypothesis h ∈ H relevant for P, i.e., does h contribute to some explanation of P? (Necessity): is a given hypothesis h ∈ H necessary for P, i.e., is h contained in all explanations of P?

Due to the following simple fact, we shall not deal in our analysis explicitly with Necessity in the case of minimal explanations.

Proposition 1 Let P = ⟨H, M, W, D⟩ be a PDAP and let h ∈ H. Then, h is necessary for P under minimal credulous (resp. skeptical) explanations iff h is necessary for P under credulous (resp. skeptical) explanations.

4 Results

The main results on the complexity of abduction from general propositional default theories are summarized in Table 1. In our analysis, we pay particular attention to normal PDAPs, since this class corresponds to the most important fragment of default logic. All hardness results in Table 1 have been derived for the case where the underlying default theory ⟨W, D⟩ is normal. Thus like deduction, abduction from normal default theories is as hard as abduction from arbitrary default theories.

We introduce some additional notation. For a set A of propositional atoms, we denote by ¬A the set {¬a | a ∈ A} and by A′ the set of atoms {a′ | a ∈ A}.

4.1 Arbitrary explanations

Our first result shows that abduction from default theories based on credulous explanations can be efficiently reduced to deductive reasoning from propositional default theories. This is somewhat unexpected and surprising, since in case of classical theories, abduction can not be efficiently reduced to deduction.

Given a PDAP P = ⟨H, M, W, D⟩, we construct a default theory T_{P} = ⟨W_{P}, D_{P}⟩ such that the credulous explanations of P correspond to the extensions of T_{P}. Indeed, define

• W_{P} = W ∪ {a_{h} ⊃ h | h ∈ H},

• D_{P} = D∪\{ \frac{:¬m}{⊥} | m ∈ M\}∪\{ \frac{:a_{h}}{a_{h}} , \frac{:¬a_{h}}{¬a_{h}} | h ∈ H\}

where for each h ∈ H, a_{h} is a new propositional atom. Then, we have:

Theorem 1 Let P = ⟨H, M, W, D⟩ be a PDAP. Then,

(i) if E is a credulous explanation for P, then there exists a consistent extension E′ of T_{P} such that E = {h ∈ H | a_{h} ∈ E′}; (ii) if E′ is a consistent extension of T_{P}, then E = {h ∈ H | a_{h} ∈ E′} is a credulous explanation for P.

PDAP P = ⟨H, M, W, D⟩ arbitrary explanations minimal explanations
Problem:  credulous skeptical credulous skeptical
Exp(P) ≠ ∅  Σ_{2}^{P}  Σ_{3}^{P}  Σ_{2}^{P}  Σ_{3}^{P}
E ∈ Exp(P)  Σ_{2}^{P}  D_{2}^{P}  D_{2}^{P}  Π_{3}^{P}
E ∈ Exp(P) is minimal  Π_{2}^{P}  Π_{3}^{P}
h ∈ H is relevant for P  Σ_{2}^{P}  Σ_{3}^{P}  Σ_{3}^{P}  Σ_{4}^{P}
h ∈ H is necessary for P  Π_{2}^{P}  Π_{3}^{P}  Π_{2}^{P}  Π_{3}^{P}

Table 1: Complexity results for abduction from propositional default theories

Using (i) and (ii), the main decisional abductive reasoning tasks can be efficiently transformed to similar deductive reasoning tasks in default logic. Corollary 1 Let P be a PDAP based on credulous explanations. Then, (i) Consistency, (ii) Relevance, and (iii) Necessity are equivalent to (i’) existence of a consistent extension of T_{P}, (ii’) membership of a_{h} in some consistent extension of T_{P}, and (iii’) membership of a_{h} in all extensions of T_{P}, respectively.

By the results on the complexity of propositional default logic [Gottlob, 1992; Stillman, 1992], it follows that (i) and (ii) are in Σ_{2}^{P} and that (iii) is in Π_{2}^{P}. We also obtain matching hardness by reductions from deductive default reasoning. Let T = ⟨W, D⟩ be a normal default theory such that W is consistent, and ϕ a formula. Let h, q be new propositional atoms. Then, the PDAP

(∗) ⟨∅, {q} , W ∪ {ϕ ⊃ q} , D⟩ has a credulous explanation iff T ⊢_{c} ϕ; h is relevant for the PDAP

(∗∗) ⟨{h} , {q} , W ∪ {ϕ ⊃ q} , D⟩ iff T ⊢_{c} ϕ; and h is necessary for the PDAP

(∗ ∗ ∗) ⟨{h} , {q} , W ∪ {ϕ ∨ h ⊃ q} , D⟩ iff T ⊬_{c} ϕ. Since the reasoning problems for T in (*), (**) are Σ_{2}^{P} -hard and the one in (***) is Π_{2}^{P} -hard [Gottlob, 1992], the hardness results follow.

It is interesting to note that verifying a credulous explanation is as hard as finding one. The former problem can be easily reduced to the latter; moreover, ∅ is the only possible credulous explanation for the PDAP (*).

Thus, Theorem 2 Let P = ⟨H, M, W, D⟩ be a PDAP. Deciding if E ⊆ H is a credulous explanation for P is Σ_{2}^{P} - complete, with hardness holding even for normal P.

Now consider abduction based on skeptical reasoning. It would be useful to have a reduction of abductive reasoning to deductive reasoning which can be computed efficiently. However, by using skeptical reasoning the abductive reasoning tasks grow more complex, by one level of the polynomial hierarchy. This strongly suggests that such an efficient reduction is not possible.

We first consider the problem of recognizing skeptical solutions. Clearly, this reduces to deciding if a certain default theory has a consistent extension (which is in Σ_{2}^{P}) and if each extension includes all manifestations (Π_{2}^{P}). Thus, the problem is a logical conjunction of a problem in Σ_{2}^{P} and a problem in Π_{2}^{P}, and hence in the class D_{2}^{P}. Moreover, it is also hard for this class. Theorem 3 Let P = ⟨H, M, W, D⟩ be a PDAP. Deciding if E ⊆ H is a skeptical explanation for P is D_{2}^{P}- complete.

Thus, as in the case of credulous explanations, recognizing a skeptical explanation is at the second level of the polynomial hierarchy. However, since this problems involves both a Σ_{2}^{P} and a Π_{2}^{P} -hard subtask (as opposed to only a Σ_{2}^{P} -hard one), finding a skeptical explanation resides at the third level.

We sketch here the Σ_{3}^{P} -hardness proof for Consistency by a transformation of deciding if a quantified Boolean formula (QBF) Φ = ∃X∀Y ∃ZF is valid (cf. [Johnson, 1990] for a definition of QBFs). Define

D = \{ \frac{:¬a}{¬a}, \frac{:a}{a} | a ∈ X ∪ Y \} ∪ \{ \frac{:F}{F} \} ,

P = ⟨X ∪ {¬x | x ∈ X} , {f} , { f ≡ F } , D⟩,

where f is a new atom. Then, P has a skeptical explanation iff Φ is valid.

How does this result compare to other nonmonotonic logics, in particular, which nonmonotonic logic has similar complexity ? We know that Konolige’s moderately grounded autoepistemic logic [Konolige, 1988] and several other ground nonmonotonic modal logics have the same complexity [Eiter and Gottlob, 1992; Donini et al., 1995]; thus, we can use a theorem prover for such logics to perform abductive reasoning from default theories based on skeptical explanations.

4.2 Minimal explanations

As mentioned above, one is usually interested in minimal explanations for observations. The results in [Eiter and Gottlob, 1995] were that the complexity of abduction from classical theories does not increase if minimal explanations are used instead of arbitrary explanations. However, this is not true in for abduction from default logic. Here, checking minimality of an explanation is a source of complexity, which causes an increase in complexity by one level of the polynomial hierarchy.

Consider first credulous explanations. Checking minimality of an explanation E has complementary complexity of checking the explanation property. Notice that E is not minimal iff for some h ∈ E, the PDAP ⟨E − {h} , M, W, D⟩ has a credulous solution; hence, it follows that the problem is in Π_{2}^{P}. On the other hand, reconsider (***). Clearly, {h} is a credulous explanation; moreover, it is minimal iff h is necessary for P. Thus, Π_{2}^{P} -hardness follows.

Note that recognizing minimal credulous explanations, which consists in checking the solution property and testing minimality, is in D_{2}^{P}, and also complete for this class. Thus, this problem can be transformed into recognition of skeptical explanations for a certain PDAP and vice versa. Due to the complexity of minimality checking, problem Relevance migrates to the next level of the polynomial hierarchy. Theorem 4 Let P be a PDAP based on minimal credulous explanations. Then, problem Relevance is Σ_{3}^{P} - complete, with hardness holding even for normal P. Proof. (Sketch) Membership. A guess E for a minimal credulous explanation for P such that h ∈ E can be verified by two calls to a Π_{2}^{P} oracle. Hence, the problem is in Σ_{3}^{P}.

Hardness. We outline a reduction from deciding validity of a QBF Φ = ∃X∀Y ∃ZF. Let s and q be new atoms, and define

D = \{ \frac{:¬s}{¬s}, \frac{s∧Y:q}{q} , \frac{¬s∧¬F:q}{q} \} ∪

\{ \frac{x:x′}{x′} , \frac{¬x:x′}{x′} | x ∈ X \} ∪ \{ \frac{:¬y}{¬y} | y ∈ Y \} .

Let P = ⟨X ∪ ¬X ∪ Y ∪ {s} , X′ ∪ {q} , ∅, D⟩. Then, one can show that s is relevant for a minimal credulous explanation for P iff Φ is valid.

Now let us consider minimal skeptical explanations. Testing minimality of a skeptical explanation is much more involved than of a credulous explanation. While the latter has roughly the same complexity as testing the explanation property, the former is harder by one level of the polynomial hierarchy. Intuitively, this can be explained as follows. Since verifying a credulous explanation E is in Σ_{2}^{P}, it has a polynomial-size “proof” which can be checked with an NP oracle in polynomial time. Thus, if we ask for a smaller explanation E′ ⊂ E, we can simultaneously guess E′ and its proof, and check the proof in polynomial time with the NP oracle. However, verifying a skeptical explanation E is Π_{2}^{P} -hard, and hence E does not have such a “proof”. Here, verification needs the full power of a Π_{2}^{P} oracle. Theorem 5 Let P = ⟨H, M, W, D⟩ be a PDAP. Deciding if a skeptical explanation E for P is minimal is Π_{3}^{P} - complete, with hardness holding even for normal P. Proof. (Sketch) Membership. A guess for a smaller skeptical explanation E′ ⊂ E can be verified with two calls to a Σ_{2}^{P} oracle, and hence deciding the existence of such an E′ is in Σ_{3}^{P}. Consequently, the problem is in Π_{3}^{P}.

Hardness. We describe here a reduction from deciding whether a QBF Φ = ∀X∃Y ∀ZF is valid. Let s and q be new atoms, and define

D = \{ \frac{:¬s}{¬s}, \frac{s∧X:q}{q} , \frac{¬s:¬F ∧q}{¬F ∧q} \} ∪ \{ \frac{:¬x}{¬x} | x ∈ X \}
∪ \{ \frac{:y}{y} , \frac{:¬y}{¬y} | y ∈ Y \} .

Let P = ⟨X ∪ {s} , {q} , ∅, D⟩. Check that E = X ∪ {s} is a skeptical explanation for P. Moreover, E is minimal iff Φ is valid.

Note that recognizing minimal skeptical explanations is in Π_{3}^{P}, since the complexity of deciding minimality (Π_{3}^{P}) dominates the complexity of the solution property (“only” Σ_{2}^{P}), and is also complete for this class.

The complexity of deciding relevance of a hypothesis increases by the same amount as testing minimality if skeptical explanations are used instead of credulous explanations. In fact, the problem resides at the fourth level of the polynomial hierarchy.

Theorem 6 Let P be a PDAP based on minimal skeptical explanations. Then, problem Relevance is Σ_{4}^{P} - complete, with hardness holding even for normal P. Proof. (Sketch) Membership. A guess for a minimal skeptical explanation E for P such that h ∈ E can be verified with one call to a Σ_{3}^{P} oracle.

Hardness. We outline a reduction from deciding validity of a QBF Ψ = ∃R∀X∃Y ∀ZF, which is an extension to the reduction in the proof of Theorem 5. Let as there be s and q new atoms, and define

D1 = D ∪ \{ \frac{r′:r∧r′′}{r∧r′′} , \frac{¬r′:¬r∧r′′}{¬r∧r′′} | r ∈ R \} ,

where D is the same set of defaults as in the proof of Theorem 5. Define P = ⟨H, R′′ ∪ {q} , ∅, D1⟩, where H = R′∪¬R′∪X ∪{s}. (Note that if W would be empty, then P would be identical to the PDAP in the proof of Theorem 5). It holds that for each subset R1 ⊆ R, the set R1′ ∪ ¬(R − R1)′ ∪ X ∪ {s} is a skeptical explanation for P. Moreover, it can be shown that s is relevant for a minimal skeptical explanation for P iff Ψ is valid.

There is no well-known nonmonotonic logic that has similar complexity, and thus one can not take advantage of theorem provers for such logics to perform skeptical abduction from default theories.

4.3 Tractable cases

From the practical side, the results from above are discouraging, since abduction from default theories has even higher complexity than deduction, in particular for skeptical explanations. The reasoning tasks suffer from several intermingled sources of complexity, whose number is (at least) the level at the polynomial hierarchy. For example, Relevance for P = ⟨H, M, W, D⟩ using minimal skeptical explanations (complete for Σ_{4}^{P}) suffers from the following four “orthogonal” sources of complexity: (1.) classical deductive inference (⊧), (2.) the number of extensions of ⟨W ∪ E, D⟩, (3.) the number of candidates E for a skeptical explanation, and (4.) the number of possible smaller explanations, where each number can be exponential.

For dealing with abduction from default theories in practice, we have to find tractable cases or cases where good algorithms for handling hard problems like GSAT [Selman et al., 1992] are applicable.

An example of the latter case is credulous abduction from default theories where all propositional formulas are from a tractable fragment of the propositional language, e.g. Horn formulas or Krom formulas (clauses with at most two literals). In such a case, classical inference ⊧ vanishes as source of complexity. In particular, the Σ_{2}^{P} -complete abductive reasoning tasks fall back to NP. Thus, we can use e.g. GSAT [Selman et al., 1992], which provides a good heuristics for solving NP-complete problems, to solve the problems quickly.

For tractable cases of default abduction, all sources of complexity must be eliminated. In particular, the underlying default reasoning tasks must be tractable. Kautz and Selman [Kautz and Selman, 1991] and Stillman [Stillman, 1990] gave a very detailed picture of polynomial vs. intractable cases of deductive default reasoning. For the following two classes of default theories ⟨W, D⟩, they proved tractability of credulous inference ⟨W, D⟩ ⊢_{c} ℓ of a single literal ℓ:

Literal-Horn [Kautz and Selman, 1991]: W is a set of literals and each default in D is Horn, i.e., of form \frac{a_{1}∧···∧a_{k}:ℓ}{ℓ}, where the a_{i}’s are atoms and ℓ is a literal.

Krom-pf-normal [Stillman, 1990]: W is a set of Krom formulas, and each default in D is of form \frac{:ℓ_{1}∧···∧ℓ_{k}}{ℓ_{1}∧···∧ℓ_{k}}, where all ℓ_{i}’s are literals.

A natural generalization of the proof in [Kautz and Selman, 1991] yields the following. Lemma 1 Let ⟨W, D⟩ be a Literal-Horn default theory, and let ℓ_{1}, …, ℓ_{n} be literals. Then, deciding ⟨W, D⟩ ⊢_{c} ℓ_{1} ∧ ⋯ ∧ ℓ_{n} is polynomial.

For Krom-pf-normal, such a generalization is not evident as ⟨W, D⟩ ⊢_{c} ℓ_{1}∧⋯∧ℓ_{n} is NP-hard. However, it is possible for a small conjunction.

In what follows, we call a set L of literals small iff |L| ≤ c for some fixed constant c. Lemma 2 Let ⟨W, D⟩ be Krom-pf-normal, and let L = {ℓ_{1}, …, ℓ_{k}} be a small set of literals. Then, deciding ⟨W, D⟩ ⊢_{c} ℓ_{1} ∧ ⋯ ∧ ℓ_{k} is polynomial.

Based on these tractable cases of credulous default reasoning, we obtain tractable cases of credulous default abduction. Similar tractability results for skeptical default abduction are unlikely, since the underlying skeptical inference ⟨W, D⟩ ⊢_{s} ℓ is co-NP-complete in both cases (cf. [Kautz and Selman, 1991] for Literal-Horn).

Literal-Horn default theories In this case, the main reasoning tasks for credulous abduction are tractable. Theorem 7 Let P = ⟨H, M, W, D⟩ be a PDAP based on credulous explanations and ⟨W, D⟩ Literal-Horn. Then,

Consistency, Relevance, and Necessity are polyno-

mial. Proof. (Sketch) Construct a Literal-Horn T 1 = ⟨W, D1⟩, where D1 = \{ \frac{b_{h}:h}{h}, \frac{:¬b_{h}}{¬b_{h}} , \frac{:b_{h}}{b_{h}} | h ∈ H\} , where each b_{h} is a new propositional atom. Then, it can be shown that P has an explanation iff W is consistent and T 1 ⊢_{c} ℓ_{1}∧⋯∧ℓ_{k}, where M = {ℓ_{1}, …, ℓ_{k}}. By Lemma 1, this can be decided in polynomial time. Thus, Consistency is polynomial. Relevance and Necessity can be easily reduced to Consistency resp. its complement.

Notice that a polynomial algorithm for finding a credulous explanation (even containing a given hypothesis), can be extracted from the proof.

Moreover, there is also a polynomial algorithm for finding a minimal credulous explanation. Indeed, an explanation E for P = ⟨H, M, W, D⟩ is minimal iff ⟨E − {h} , M, W, D⟩ has no explanation for each h ∈ E. Thus, for P as above, one can check in polytime whether E is minimal and, if not, find a smaller explanation E1 ⊂ E. By repeating this test, we can minimize E. Theorem 8 Let P = ⟨H, M, W, D⟩ be a PDAP where ⟨W, D⟩ is Literal-Horn. Then, a minimal credulous explanation for P can be found in polynomial time.

However, Relevance based on minimal credulous explanations for PDAPs with Literal-Horn default theories can be shown to be NP-complete.

Krom-pf-normal default theories

For this fragment, we have the following results.

Theorem 9 Let P = ⟨H, M, W, D⟩ be a PDAP based on credulous explanations such that M = {ℓ_{1}, …, ℓ_{k}} is small and ⟨W, D⟩ is Krom-pf-normal. Then, Consis-

tency, Relevance, and Necessity are polynomial.

Proof. (Sketch) Construct a Krom-pf-normal default theory T 2 = ⟨W 2, D2⟩, where

W 2 = \{c_{h} ⊃ h | h ∈ H\} , D2 = D ∪ \{ \frac{:c_{h}}{c_{h}} , \frac{:¬c_{h}}{¬c_{h}} | h ∈ H\} ,

where each c_{h} is a new propositional atom. Then, P has an explanation iff W 2 is consistent and T 2 ⊢_{c} ℓ_{1} ∧ ⋯ ∧ ℓ_{k}, which are both polynomial. Consistency fo W 2 and T 2 ⊢_{c} ℓ_{1} ∧ ⋯ ∧ ℓ_{k} can be decided in polynomial time (cf. Lemma 2). Hence, Consistency is polynomial. Since Relevance and Necessity can be easily reduced to Consistency resp. its complement, these problems are also polynomial.

Again, a polynomial time algorithm for finding an explanation can be extracted from the proof. Unfortunately, Theorem 9 can not be generalized to an arbitrary set M of literals. In fact, due to the NP-hardness of ⟨W, D⟩ ⊢_{c} ℓ_{1} ∧ ⋯ ∧ ℓ_{n} for Krom-pf-normal ⟨W, D⟩, the problem is NP-hard.

Interestingly, the number of hypotheses in a minimal credulous explanation is bounded by the number of manifestations. Intuitively, this is explained by the fact that always a single hypothesis can explain a manifestation. Proposition 2 Let E be any minimal credulous explanation for P = ⟨H, M, W, D⟩ where ⟨W, D⟩ is Krom-pf-normal and M = {ℓ_{1}, …, ℓ_{n}}. Then, |E| ≤ |M|.

In particular, for a single manifestation (M = {ℓ}), the minimal explanations consist of single hypotheses, if hypotheses are needed for an explanation.

A consequence of this characterization and Lemma 2 is that all minimal credulous explanations for a small set M can be computed by exhaustive testing of all subsets E ⊆ H with |E| ≤ |M| in polynomial time. Theorem 10 Given a PDAP P = ⟨H, M, W, D⟩ where ⟨W, D⟩ is Krom-pf-normal and M is small, all minimal credulous explanations for P can be computed in polynomial time.

Consequently, also Relevance for minimal explanations is polynomial if M is small.

5 Conclusion and further research

We proposed a basic model of abduction from default theories, and analyzed its computational complexity. Moreover, we have shown that credulous abduction from the previously known classes of Literal-Horn and Krompf-normal default theories is tractable.

Besides identifying further tractable and manageable cases of default abduction, the following issues are currently under investigation.

The size of an explanation (cf. [Peng and Reggia, 1990]) or, more general, its cost, given by the sum of the predefined costs of its hypotheses, can be used for further pruning minimal (i.e., nonredundant) explanations. Results for abduction from classical theories [Eiter and Gottlob, 1995] suggest using such explanations, abduction from default theories yields complete problems for the classes Δ_{k}^{P} and Δ_{k}^{P} [O(log n)] of the polynomial hierarchy.

Another issue is default logic with an underlying language richer than a plain propositional one. A generalization of our abduction model to a propositional language over atoms p(t_{1}, …, t_{n}) where the t_{i} are variables or constants, is straightforward; here, an instance of an abduction problem reduces to the propositional abduction problem obtained by replacing formulas with all ground instances. Since the grounded propositional version can be exponentially larger, this leads intuitively to an exponential increase in complexity. Thus, abduction from default theories in this nonground language is expected to be complete for the exponential analogues of Σ_{k}^{P}, Π_{k}^{P} etc.

Acknowledgment Nicola Leone has been partially supported by the EC-US project ”Deus ex Machina” and by MURST40% project ”Sistemi formali e strumenti per basi di dati evolute”.

References

[Cadoli and Schaerf, 1993] M. Cadoli and M. Schaerf. A Survey of Complexity Results for Non-monotonic Logics. Journal of Logic Programming, 17:127–160, 1993.

[Charniak and McDermott, 1985] E. Charniak and P.

Mc Dermott. Introduction to Artificial Intelligence. 1985.

[Donini et al., 1995] F.M. Donini, D. Nardi, and R. Rosati. Ground Nonmonotonic Modal Logics for Knowledge Representation. In Proc. World Congress for AI (WOCFAI-95), 1995. Forthcoming.

[Eiter and Gottlob, 1992] Thomas Eiter and Georg Gottlob. Reasoning with Parsimonious and Moderately Grounded Expansions. Fundamenta Inform., 17(1,2):31–53, 1992.

[Eiter and Gottlob, 1995] Thomas Eiter and Georg Gottlob. The Complexity of Logic-Based Abduction. Journal of the ACM, January 1995. Abstract in Proc. STACS-93, LNCS 665, pp. 70–79, 1993.

[Eshghi, 1988] K. Eshghi. Abductive Planning with Event Calculus. In Proc. 5th Int’l Conf. and Symp. on Logic Programming, pp. 562–579. 1988.

[Gottlob, 1992] Georg Gottlob. Complexity Results for Nonmonotonic Logics. Journal of Logic and Computation, 2(3):397–425, June 1992.

[Hobbs et al., 1988] J. R. Hobbs, M. E. Stickel, P. Martin, and D. Edwards. Interpretation as Abduction. In Proc. 26th Annual Meeting of the Assoc. for Computational Linguistics, pp. 95–103, Buffalo (NY), 1988.

[Johnson, 1990] D. S. Johnson. A Catalog of Complexity

Classes. In Handbook of Theoret. Comp. Sc. A, 1990. [Josephson et al., 1987]

J.R. Josephson, B. Chandrasekaran, Jr. J. W. Smith, and M.C. Tanner. A Mechanism for Forming Composite Explanatory Hypotheses. IEEE Transactions, TSMC-17:445–454, 1987.

[Kakas and Mancarella, 1990] A.C. Kakas and P. Mancarella. Database Updates Through Abduction. In Proc. VLDB-90, pp. 650–661, 1990.

[Kautz and Selman, 1991] H. Kautz and B. Selman. Hard Problems for Simple Default Logics. Artificial Intelligence, 49:243–279, 1991.

[Konolige, 1988] K. Konolige. On the Relationship between Default and Autoepistemic Logic. Artificial Intelligence, 35:343–382, 1988, + 41:115, 1989/90.

[Konolige, 1992] K. Konolige. Abduction versus closure

in causal theories. Art. Intell., 53:255–272, 1992. [Marek and Truszczyński, 1993] W. Marek and M.

Truszczyński. Nonmonotonic Logics. Springer, 1993. [Nebel, 1994] B. Nebel. Artificial Intelligence: A Com-

putational Perspective. November 1994. To appear in “Logic and Computation in AI”, G. Brewka ed.

[Ng and Mooney, 1991] H. T. Ng and R. J. Mooney. An efficient first-order Horn clause abduction system based on the ATMS. In Proc. AAAI-91, pp. 494–499.

[Peng and Reggia, 1990] Y. Peng and J.A. Reggia. Abductive Inference Models for Diagnostic Problem Solving. 1990.

[Poole, 1989] D. Poole. Normality and Faults in Logic

Based Diagnosis. In Proc. IJCAI-89, pp. 1304–1310. [Reiter, 1980] R. Reiter. A Logic for Default Reasoning.

Artificial Intelligence, 13:81–132, 1980. [Selman and Levesque, 1990] Bart Selman and Hec-

tor J. Levesque. Abductive and Default Reasoning: A Computational Core. In Proc. AAAI-90, pp. 343– 348, July 1990.

[Selman et al., 1992] B. Selman, H. Levesque, and D. Mitchell. A New Method for Solving Hard Satisfiability Problems. In Proc. AAAI-92, pp. 440–446.

[Stillman, 1990] J. Stillman. It’s Not My Default: The Complexity of Membership Problems in Restricted Propositional Default Logic. In Proc. AAAI-90, pp. 571–579, 1990.

[Stillman, 1992] J. Stillman. The Complexity of Propositional Default Logic. In Proc. AAAI-92, pp. 794–799.