Semantics and Complexity of Abduction from Default Theories

1 Introduction

Abductive reasoning has been recognized as an import­ ant principle of common-sense reasoning having fruit­ ful applications in a number of areas such diverse as model-based diagnosis [Poole, 1989], speech recognition (Hobbs et al., 1988], maintenance of database views [Ka­ kas 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 abduc­ tion can be performed from theories (W, D) in default logic. We informally pursue this on an example.

Example 1 Consider the following_ s~t of.?efault _rules, which represent knowledge about Bill s skung habits:

Nicola Leonet

Istituto per la Sistemistica e l'Informatica C.N.R. cjo DEIS- University of Calabria 87036 Rende, Italy

nik~si.deis.unical.it

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 ski­ ing (which is inconsistent with the extension). Abduc­ tion 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, snawing }, D) has a single extension, which contains -.skiing_Bill. We say that snowing is ab­ duced from the observation -.skiing_Bill, or that it is an abductive explanation of -.skiing_Bill . I

Observe that the description of the above situation re­ quires the specification of some default properties that can not be represented properly in classical logic.

In general, as opposed to the example, a default the~ry may have several or even no extensions. For deductive entailment, this gives rise to credulous entailment, un­ der which ¢ is entailed from a default theory T (denoted T f- c ¢) iff ¢ belongs to at least one extension of T, and to skeptical entailment, under which ¢ follows from T (T f- 8 ¢) iff ¢ belongs to all extensions of T. Acc~r­ dingly, two variants of abduction from default theones arise: credulous abduction, where entailment of an ob­ servation is based on f- c, and skeptical abduction, which is based on f- 8 · In practice, the user will choose credu­ lous 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 dia­ gnosis 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 U A, D) is a possible evolution of the system, i.e., each extension represents a possible reaction of the system to A.

Abductive diagnosis consists, loosely speaking, in de­ riving 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 U A, D) is a possible evolution of the sy­ stem with input A, we can assert that A is a possible input that caused F if (W U A, D) 1-c F. Thus, diagno­ stic 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 Mi­ lan and Rome to Vienna will collide if the plane from Mi­ lan 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:

Now, you are informed that planes flying from Milan and Rome to Vienna collided. A diagnosis for the colli­ sion can be obtained by abducing an explanation for the observation collision from the theory T = (0, 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' 1-c collision). Credulous abduction correctly identifies such explanations. For in­ stance, it is easy to recognize that both E1 = {mv1, rv1, m_20minJater} and E2 = { mv2, rv2, m_20minJater} are credulous explanations for collision. I

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 U A, D) 1-s F. Hence, planning activities can be represented by abduc­ tive problems with skeptical entailment.

Example 3 We know that a plane from Rome to Vi­ enna 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 Mi­ lan 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),

As we can not risk a collision, we want that every pos­ sible 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. I

The two examples above support the intuition that credulous abduction is feasible for diagnosis, while skep­ tical 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 sket­ ches. 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 Truszczynski, 1993] for an extensive study). We focus on propositional default theories T = (W, D) over a pro­ positional language£ (including ..l for falsity), i.e. W is a subset of£ and D a set of defaults a:(h, ... ,(3m m > 1 I ' - where a, (31 , ... , f3m, 1 are from £. The extensions of T, which are deductively closed sets E ~ £, are defined by a fixpoint equation; in particular, £ is an extension ofT (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 7f; a normal T always has an extension.

For NP-completeness and complexity theory, cf. [John­ son, 1990]. The classes ~f and IIf of the polynomial hierarchy are defined as follows: ~{; = II{; = P, and

In particular, NP = ~f and co-NP = IIf. The class nr' which is defined as the class of problems that consist of the conjunction of two (independent) pro­ blems from ~f and IIf, respectively, is considered to be further restricted in computational power. For all k 2: 1, clearly ~r ~ nr ~ ~r+l j both inclusions are believed to be strict. Many nonmonotonic reaso­ ning problems are complete for classes at the lower end of the polynomial hierarchy [Cadoli and Schaer£, 1993, Nebel, 1994]. It is well-known that deciding whether a propositional default theory has an extension is ~f­ complete, and that credulous and skeptical reasoning from default theories are complete for ~f and IIf, re­ spectively. This remains true if inconsistent extensi­ ons are excluded and, for the latter problems, if de­ fault 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 ab­ duction from propositional default theories and state the main decisional reasoning tasks for abductive reasoning.

Our formalization of an abduction scenario is as fol­ lows.

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. I

Note that hypotheses and manifestations may be lite­ rals 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 U E, D) 1-c M, and (ii) (W U E, D) has a consistent extension. Similarly, E is a skeptical explanation for P iff (i) (W U E, D) 1-8 M and (ii) (W U E, D) has a consistent extension.

The existence of a consistent extension for (W U E, D) (in this case, all extensions are consistent) assures that the explanation E is consistent with the knowledge re­ presented 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 explana­ tions. 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 Exam­ ple 3 E3 = {m-8.20} and E4 = {mv3} are the minimal explanations; they represent the smallest partial sche­ dules 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 ex­ planations for the PDAP P, abstracting from the chosen type of explanations (credulous, skeptical, minimal cre­ dulous, 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 E H. Then, h is relevant (resp. necessary) for P iff hE E for some (resp. every) E E Exp(P).

The opposite of necessity is also termed dispen­ sability (cf. [Josephson et al., 1987]). In Exam­ ple 2, m-'20minlater is necessary, while each· hypothesis rv1, rv2, mv1, mv2 is relevant, but not necessary. Moreo­ ver, in Example 3 mv3 is relevant w.r.t . minimal (skep­ tical) explanations, but not necessary. Note that in the same example rv1 is relevant under arbitrary explanati­ ons, but not relevant under minimal explanations.

The main decisional problems in abductive reaso­ ning 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 E H relevant for P, i.e., does h contribute to some explanation ofP?

(Necessity): is a given hypothesis hE 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 E 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 re­ sults 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 I a E A} and by A' the set of atoms {a' I a E A}.

4.1 Arbitrary explanations

Our first result shows that abduction from default theo­ ries based on credulous explanations can be efficiently re­ duced 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 de­ fault theory Tp = (Wp,Dp) such that the credulous explanations of P correspond to the extensions of Tp . Indeed, define

• Wp = W U {ah :J hI hE H},

where for each h E H, ah 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 Tp such that E = {hE HI ah E E'}; (ii) if E' is a consistent extension of Tp, then E ={hE HI ah E E'} is a credulous explana­ tion for P.

Using (i) and (ii), the main decisional abductive reaso­ ning tasks can be efficiently transformed to similar de­ ductive reasoning tasks in default logic.

Corollary 1 Let P be a PDAP based on credulous ex­ planations. Then, {i} Consistency, {ii} Relevance, and {iii} Necessity are equivalent to (i ') existence of a con­ sistent extension ofTp, (ii'} membership of ah in some consistent extension of Tp, and {iii') membership of ah in all extensions of Tp, respectively.

By the results on the complexity of propositional de­ fault logic [Gottlob, 1992, Stillman, 1992], it follows that (i) and (ii) are in ~f and that (iii) is in IIf. 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

has a credulous explanation iff T f-c ¢; h is relevant for the PDAP

iff T f-c ¢; and h is necessary for the PDAP

iff T If c ¢. Since the reasoning problems forT in (*), (**) are ~f -hard and the one in (***) is IIf -hard [Gottlob, 1992], the hardness results follow.

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

Theorem 2 Let P = (H, M, W, D) be a PDAP. Deci­ ding if E .~ H is a credulous explanation for P is ~f­ 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 re­ asoning to deductive reasoning which can be computed efficiently. However, by using skeptical reasoning the ab­ ductive 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 skepti­ cal solutions. Clearly, this reduces to deciding if a cer­ tain default theory has a consistent extension (which is in ~f) and if each extension includes all manifestations (IIf). Thus, the problem is a logical conjunction of a problem in ~f and a problem in IIf, and hence in the class D~. Moreover, it is also hard for this class.

Theorem 3 Let P = (H, M, W, D) be a PDAP. Deci­ ding if E ~ H is a skeptical explanation for P is D~­ complete.

Thus, as in the case of credulous explanations, reco­ gnizing a skeptical explanation is at the second level of the polynomial hierarchy. However, since this problems involves both a ~f and a IIf-hard subtask (as opposed to only a ~f -hard one), finding a skeptical explanation resides at the third level.

We sketch here the ~f -hardness proof for Consi­ stency by a transformation of deciding if a quantified Boolean formula (QBF) <P = 3X'v'Y3ZF is valid (cf. [Johnson, 1990) for a definition of QBFs). Define

where f is a new atom. Then, P has a skeptical expla­ nation iff <P is valid.

How does this result compare to other nonmonoto­ nic logics, in particular, which nonmonotonic logic has similar complexity ? We know that Konolige's mo­ derately grounded autoepistemic logic [Konolige, 1988) and several other ground nonmdnotonic modal logics have the same complexity [Eiter and Gottlob, 1992, Donini et al., 1995); thus, we can use a theorem pro­ ver 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 mini­ mal explanations for observations. The results in [Eiter and Gottlob, 1995) were that the complexity of abduc­ tion 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 com­ plexity by one level of the polynomial hierarchy.

Consider first credulous explanations. Checking mi­ nimality of an explanation E has complementary com­ plexity of checking the explanation property. Notice that E is not minimal iff for some h E E, the PDAP (E - { h}, M, W, D) has a credulous solution; hence, it follows that the problem is in IIf. On the other hand, reconsider (***). Clearly, { h} is a credulous explanation; moreover, it is minimal iff h is necessary for P. Thus, IIf -hardness follows.

Note that recognizing minimal credulous explanations, which consists in checkin~ the solution property and te­ sting minimality, is in D 2 , and also complete for this class. Thus, this problem can be transformed into re­ cognition 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 cre­ dulous explanations. Then, problem Relevance is :Ef­ 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 E can be verified by two calls to a IIf oracle. Hence, the problem is in :Ef.

Hardness. We outline a reduction from deciding va­ lidity of a QBF <I> = 3X'v'Y3ZF. Let s and q be new atoms, and define

Let P = (Xu -.XU Y U {s} ,X' U {q} ,0,D) . Then, one can show that s is relevant for a minimal credulous explanation for P iff <I> is valid. I

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 ex­ planation E is in :Ef, 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' c E, we can simultaneously guess E' and its proof, and check the proof in polynomial time with the NP oracle. Howe­ ver, verifying a skeptical explanation E is IIf -hard, and hence E does not have such a "proof". Here, verification needs the full power of a IIf oracle.

Theorem 5 Let P = (H, M, W, D) be a PDAP. Deci­ ding if a skeptical explanation E for P is minimal is IIf -complete, with hardness holding even for normal P. Proof. (Sketch) Membership. A guess for a smaller skeptical explanation E' C E can be verified with two calls to a :Ef oracle, and hence deciding the existence of such an E' is in :Ef. Consequently, the problem is in II f.

Hardness. We describe here a reduction from deciding whether a QBF <I>= 'v'X3Y'v'ZF is valid. Lets and q be new atoms, and define

Let P =(XU {s}, {q} ,0,D). Check that E =XU {s} is a skeptical explanation for P. Moreover, E is minimal iff <I> is valid. I

Note that recognizing minimal skeptical explanations is in IIf, since the complexity of deciding minimality (IIf) dominates the complexity of the solution property ("only" :Ef), 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 ex­ planations. In fact, the problem resides at the fourth level of the polynomial hierarchy.

Theorem 6 Let P be a PDAP based on minimal skeB­ tical explanations. Then, problem Relevance is :E 4 - 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 E can be verified with one call to a :Ef oracle.

Hardness. We outline a reduction from deciding vali­ dity of a QBF \II= 3R'v'X3Y'v'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

where D is the same set of defaults as in the proof of Theorem 5. Define P = (H,R" U {q},0,Dl), where H = R'U-.R'UXU{ 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 Rl ~ R, the set Rl' U -.(R- Rl)' U XU { s} is a skeptical explanation for P. Moreover, it can be shown that s is relevant for a minimal skeptical explanation for P iff \II is valid. I

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 dis­ couraging, 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 num­ ber is (at least) the level at the polynomial hierarchy.

For example, Relevance for P = (H, M, W, D~ using minimal skeptical explanations (complete for :E4 ) suf­ fers from the following four "orthogonal" sources of com­ plexity: (1.) classical deductive inference 0=), (2.) the number of extensions of (W U 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 ~;ood algorithms for handling hard problems like GSAT lSelman 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 lan­ guage, e.g. Hom formulas or Krom formulas (clauses with at most two literals). In such a case, classical infe­ rence F vanishes as source of complexity. In particular, the I: 2 -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 Still­ man [Stillman, 1990] gave a very detailed picture of po­ lynomial vs. intractable cases of deductive default rea­ soning. For the following two classes of default theories (W, D), they proved tractability of credulous inference (W, D) f- c i of a single literal i:

Literal-Horn [Kautz and Selman, 1991]: W is a set of literals and each default in D is Horn, i.e., of form a,A··ta,:l , where the ai's are atoms and i is a literal.

Krom-pf-normal [Stillman, 1990]: W is a set of Krom formulas, and each default in D is of form (.:~~::~~!", where all ii 's are literals.

A natural generalization of the proof in [Kautz and Selman, 1991] yields the following.

Lemma i Let (W, D) be a Literal-Hom default theory, and let i 1 , . · . , in be literals. Then, deciding (W, D) f-c i 1 1\ · · · 1\ in is polynomial.

For Krom-pf-normal, such a generalization is not evi­ dent as (W,D) f-c i 1 /\ · ··/\in is NP-hard. However, it is possible for a small conjunction.

In what follows, we call a set L of literals small iff ILl ~ c for some fixed constant c.

Lemma 2 Let (W, D) be Krom-pf-normal, and let L = {i 1 , .. . ,ik} be a small set of literals. Then, deciding (W, D) f- c i1 1\ · · · 1\ ik is polynomial.

Based on these tractable cases of credulous default re­ asoning, we obtain tractable cases of credulous default abduction. Similar tractability results for skeptical de­ fault abduction are unlikely, since the underlying skep­ tical inference (W, D) f- 8 i 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 ab­ duction are tractable.

Theorem 7 Let P = (H, M, W, D) be a PDAP based on credulous eXplanations and (W, D) Literal-Hom. Then, Consistency, Relevance, and Necessity are polyno­ mial.

Proof. (Sketch) Construct a Literal-Horn T1 = (W, D1) where D1 = { !!..b.l! :~h :!!.. I hE H} where ' h ' ~h' bh ' each bh is a new propositional atom. Then, it can be shown that P has an explanation iff W is consistent and T1 f-c i 1/\· · ·1\ik, where M = {i1, .. . ,ik}· By Lemma 1, this can be decided in polynomial time. Thus, Consi­ stency is polynomial. Relevance and Necessity can be easily reduced to Consistency resp. its complement. I

Notice that a polynomial algorithm for finding acre­ dulous 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 E . Thus, for P as above, one can check in polytime whe­ ther E is minimal and, if not, find a smaller explanation E1 C 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-Hom. Then, a minimal credulous ex­ planation for P can be found in polynomial time.

However, Relevance based on minimal credulous ex­ planations 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 = { i 1 , ... , ik} is small and (W, D) is Krom-pf-normal. Then, Consi­ stency, Relevance, and Necessity are polynomial.

Proof. (Sketch) Construct a Krom-pf-normal default theory T2 = (W2, D2), where

where each ch is a new propositional atom. Then, P has an explanation iff W2 is consistent and T2 f-c i 1 1\ · · · 1\ ik, which are both polynomial. Consistency fo W2 and T2 f- c i1 1\ · · · 1\ ik 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. I

Again, a polynomial time algorithm for finding an ex­ planation can be extracted from the proof. Unfortuna­ tely, Theorem 9 can not be generalized to an arbitrary set M of literals. In fact , due to the NP-hardness of (W, D) f-c £1 1\ · · · 1\ in 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 ma­ nifestations. Intuitively, this is explained by the fact that always a single hypothesis can explain a manifestation.

Proposition 2 Let E be any minimal credulous expla­ nation for P = (H, M, W, D) where (W, D) is Krom-pf­ normal and M = {i1, . . . , in} · Then, lEI~ IMI.

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 lEI ~ IMI 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 polyno­ mial time.

Consequently, also Relevance for minimal explanati­ ons 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 Krom­ pf-normal default theories is tractable.

Besides identifying further tractable and manageable cases of default abduction, the following issues are cur­ rently 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) explanati­ ons. Results for abduction from classical theories [Eiter and Gottlob, 1995] suggest using such explanations, ab­ duction from default theories yields complete problems for the classes 6.f and 6.f[O(logn)J of the polynomial hierarchy.

Another issue is default logic with an underlying lan­ guage richer than a plain propositional one. A genera­ lization of our abduction model to a propositional lan­ guage over atoms p(t1 , .. . , tn) where the ti are varia­ bles 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, abduc­ tion from default theories in this nonground language is expected to be complete for the exponential analogues of ~r ' nr 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".