Preferred Arguments are Harder to Compute than Stable Extension

1 Introduction

Bondarenko et al. [1997] show that many logics for non­ monotonic reasoning, in particular default logic (DL) [Reiter, 1980] and logic programming (LP), can be un­ derstood as special cases of a single abstract framework. The standard semantics of thes" logics can be under­ stood in terms of stable extensions of a given theory, where a stable extension is a set of assumptions that does not attack itself and it attacks every assumption not in the set. In abstract terms, an assumption is attacked if its contrary can be proven, in some appropriate un­ derlying monotonic logic, possibly with the aid of other conflicting assumptions.

Bondarenko et al. [1997] also propose two new se­ mantics generalising, respectively, the admissibility se­ mantics [Dung, 1991] and the semantics of preferred ex­ tensions [Dung, 1991] and partial stable models [Sacca and Zaniolo, 1990] for LP. In abstract terms, a set of assumptions is an admissible argument of a given the­ ory, iff it does not attack itself and it attacks all sets of assumptions which attack it. A set of assumptions is a preferred argument iff it is a maximal (wrt. set inclusion) admissible argument .

The new semantics are more general than the stabil­ ity semantics since every stable extension is a preferred (and admissible) argument, but not every preferred ar­ gument is a stable extension. Moreover, the new se­ mantics are more liberal because for most concrete log­ ics for nonmonotonic reasoning, admissible and preferred arguments are always guaranteed to exist, whereas sta­ ble extensions are not. Finally, reasoning under the new semantics appears to be computationally easier than rea­ soning under the stability semantics. Intuitively, to show that a given sentence is justified by a stable extension, it is necessary to perform a global search amongst all the assumptions, to determine for each such assump­ tion whether it or its contrary can be derived, indepen­ dently of the sentence to be justified. For the semantics of admissible and preferred arguments, however, a "lo­ cal" search suffices. First, one has to construct a set of assumptions which, together with the given theory, (monotonically) derives the sentence to be justified, and then one has to augment the constructed set with further assumptions to defend it against all attacks.

However, from a complexity-theoretic point of view, it seems unlikely that the new semantics lead to better lower bounds than the standard semantics since all the "sources of complexity" one has in nonmonotonic rea­ soning are present. There are potentially exponentially many assumption sets sanctioned by the semantics. Fur­ ther, in order to test whether a sentence is entailed by a particular argument one has to reason in the underlying monotonic logic. For this reason, one would expect that reasoning under the new semantics has the same com­ plexity as under the stability semantics, i.e. , it is on the first level of the polynomial hierarchy for LP and on the second level for logics with full propositional logic as the underlying logic [Cadoli and Schaer£, 1993]. However, previous results on the expressive power of DATALO�~ queries by Sacca [1997] suggest that this is not the case for LP. Indeed, these results imply that reasoning under the preferability semantics for LP is at the second level of the polynomial hierarchy.

In this paper, we extend these results and show that for LP and DL

• credulous reasoning under the admissibility and preferability semantics has the same complexity as under the stability semantics,
• sceptical reasoning under the admissibility seman­ tics is easier than under the stability semantics - since it reduces to monotonic reasoning with the given theory, and, finally,
• sceptical reasoning under the preferability seman­ tics is harder than under the stability semantics. In other words, here intuition seems to clash severely with the complexity-theoretic results.

The paper is organised as follows. Section 2 sum­ marises the abstract framework introduced by Bon­ darenko et al. [1997], its semantics and concrete in­ stances capturing LP and DL. Section 3 gives complexity theory background and introduces the reasoning prob­ lems. Section 4 gives abstract upper bounds for credu­ lous and sceptical reasoning, parametric wrt. the com­ plexity of the underlying monotonic logic. Section 5 gives the completeness results. Section 6 discusses the results and concludes.

2 Default Reasoning via Argumentation

Assume a deductive system (£, R) where £ is some formal language with countably many sentences and R is a set of inference rules inducing a monotonic deriv­ ability notion r . Given a theory T <;:;: £ and a formula a E £ , T h(T) = {a E £IT r a} is the deductive closure ofT. Then, an abstract (assumption-based) frame­ work is a triple (T, A,-), where T, A <;:;: £ and -is a mapping from A into £. T, the theory, is a (possibly incomplete) set of beliefs, formulated in the underlying language, and can be extended by subsets of A, the set of assumptions. An extension of an abstract framework (T, A,-) is a theory Th(TU D.), with D.<;:;: A (sometimes an extension is referred to simply as TUb. or D.). Finally, given an assumption a E A, a denotes its contrary.

LP is the instance of the abstract framework (T, A,-) where T is a logic program, the assumptions in A are all negations not p of atomic sentences p, and the con­ trary not p of an assumption not p is p. r is Horn logic provability, with assumptions, not p, understood as new atoms, p* .

DL is the instance of the abstract framework (T, A,-) where the monotonic logic is classical logic augmented with domain-specific inference rules of the form

where a;, fJJ, 'Y are sentences in classical logic. T is a classical theory and A consists of all expressions of the form M (3 where (3 is a sentence of classical logic. The contrary M (3 of an assumption M (3 is ·/3.

In the remainder of the paper, without loss of general­ ity, we will assume that the set of assumptions A in the abstract framework for DL consists of all assumptions M (3 occurring in the domain-specific inference rules.

Given an abstract framework (T, A,-) and an assump­ tion set D. <;:;: A, D. attacks an assumption a E A iff a E Th(T U D.) and D. attacks an assumption set D.' C A iff D. attacks some assumption a E D.'.

The standard semantics of extensions of DL [Reiter, 1980] and stable models of LP [Gelfond and Lifschitz, 1988] correspond to the "stability" semantics of abstract frameworks, where an assumption set D. <;:;: A is stable iff

1. D. does not attack itself, and

2. D. attacks each assumption a ¢ D..

A stable extension is an extension Th(T U D.) for some stable assumption set D..

Bondarenko et al. define new semantics for the ab­ stract framework, e.g., by generalising the admissibility semantics originally proposed for LP by Dung [1991]. An assumption set D. <;:;: A is admissible iff

1. D. does not attack itself, and

2. for all D.' <;:;: A, if D.' attacks D. then D. attacks D.'. Maximal (wrt. set inclusion) admissible assumption sets are called preferred. In this paper we use the fol­ lowing terminology: an admissible (preferred) argu­ ment is an extension Th(T U D.) for some admissible (preferred) assumption set D.. Bondarenko et al. show that preferred arguments correspond to preferred exten­ sions [Dung, 1991] and partial stable models [Sacca and Zaniolo, 1990] for LP.

In order to illustrate the effects of the different seman­ tics, let us consider the following logic program:

This logic program has no stable extension, two preferred arguments ( {not r} and {not q, not s}) and four admissi­ ble arguments (additionally 0 and {not q}). If we drop the clause "p +- not p," we get the same admissible and preferred arguments. In addition, the preferred argu­ ments are also stable.

In [Bondarenko et al., 1997], the definition of stable and admissible sets includes a third condition, namely, that the set D. must be dosed, i.e., b.=AnTh(TuD.), and in part 2 of the definition of admissible sets all D.' are required to be closed. Here we omit these conditions because in the LP and DL instances of the framework every set is guaranteed to be closed. Frameworks with this property are called flat.

In the sequel we will use the following properties:

Prop1 : Every preferred assumption set is (trivially) ad­ missible and every admissible assumption set is a subset of some preferred assumption set [Bon­ darenko et al., 1997, Theorem 4.8];

Prop2 : The empty assumption set is always admissible, trivially, for all concrete LP and DL frameworks.

3 Reasoning Problems and Complexity

We will analyse the computational complexity of the fol­ lowing reasoning problems for the propositional variants of the frameworks for LP and DL under admissibility and preferability semantics:

• the credulous reasoning problem, i.e., the prob­ lem of deciding for any given sentence t.p in the set of possible queries whether t.p E T h(T U fl) for some assumption set fl sanctioned by the semantics;
• the sceptical reasoning problem, i.e., the prob­ lem of deciding for any given sentence t.p in the set of possible queries whether t.p E Th(T U fl) for all assumption sets fl sanctioned by the semantics.

The set of possible queries consists of (variable-free con­ junctions of) literals in the LP case and formulas in propositional logic in the DL case.

Instead of the sceptical reasoning problem, we will of­ ten consider its complementary problem, i.e.

• the co-sceptical reasoning problem, i.e, the problem of deciding for any given sentence t.p (in a set of possible queries) whether t.p (/. Th(T U fl) for some assumption set fl sanctioned by the semantics.

The computational complexity 1 of the above problems for all frameworks and semantics we consider is located at the lower end of the polynomial hierarchy. This is an infinite hierarchy of complexity classes above NP defined by using oracle machines, i.e. Turing machines that are allowed to call a subroutine-the oracle-deciding some fixed problem in constant time. Let C be a class of deci­ sion problems. Then, for any class X defined by resource bounds, xc denotes the class of problems decidable on a Turing machine with an oracle for a problem in C and a resource bound given by X. Based on these notions, the sets fl~, ~~, and II~ are defined as follows:

p - EP p - E~ p - EP flk+1 - P k, ~k+l - NP , Ilk+I - co-NP k. The "canonical" complete problems are SAT for ~f=NP and k-QBF for ~~ (k > 1), where k-QBF is the problem of deciding whether the quantified boolean for­

mula

k alternating quantifiers starting with 3 is true. The complementary problem, denoted by co-k­ QBF, is complete for II~.

All problems in the polynomia· ·1ierarchy can be solved in polynomial time iff P = N P. Further, all these prob­ lems can be solved by worst-case exponential time algo­ rithms. Thus, the polynomial hierarchy might not seem too meaningful. However, different levels of the hierar­ chy differ considerably in practice, e.g. methods working for moderately sized instances of NP-complete problems do not work for ~~-complete problems.

The complexity of the problems we are interested in has been extensively studied for existing logics for nonmonotonic reasoning under the standard, stability semantics [Cadoli and Schaer£, 1993; Gottlob, 1992; Niemela, 1990; Marek and Truszczynski, 1993; Stillman, 1992]. In particular, the credulous reasoning problem is NP-complete for LP and ~~-complete for DL, and the sceptical reasoning problem is co-NP-complete for LP and 11~-complete for DL.

1 For the following, we assume that the reader is familiar with the basic concepts of complexity theory [Papadimitriou, 1994], i.e., the complexity classes P, NP, and co-NP and the notion of completeness with respect to log-space reductions.

4 Generic Upper Bounds

We identify upper bounds for the credulous and scepti­ cal reasoning problems by exploiting the following guess­ and-verify algorithm that, in order to decide these prob­ lems, guesses an assumption set, verifies that it is sanc­ tioned by the semantics, and verifies that the formula under consideration is derivable or not derivable, respec­ tively, from the set of assumptions and the given theory in the underlying monotonic logic. The upper bounds are parametric on the complexity of the derivability problem in the underlying monotonic logic. Moreover, the upper bounds are determined by exploiting upper bounds for their sub-problem that an assumption set is sanctioned by the semantics, called the assumption set verification problem.

In LP, the underlying logic is (propositional) Horn logic, hence the derivability problem is P-complete (un­ der log-space reductions) [Papadimitriou, 1994, p.176]. In DL, the underlying logic is classical (propositional) logic extended with domain-specific inference rules. However, these extra inference rules do not increase the complexity of reasoning. It is known (e.g. see [Gottlob, 1995, p.90]) that for any DL like propositional monotonic rule systemS, checking whether S ~ t.p is NP-complete. Therefore, the following proposition follows immediately.

Proposition 1 Given a DL framework (T, A,-), decid­ ing for a sentence t.p E .C and an assumption set fl ~ A whether t.p E Th(T U fl)is co-NP-complete.

We now prove the basic membership result for flat frameworks in general and LP and DL in particular. In fact, flatness seems to be a computationally important property. For non-flat frameworks, the assumption set verification problem under the admissibility and prefer­ ability semantics seems to become harder in general.

Theorem 2 Given a fiat framework with derivability problem in C, the assumption set verification problem is

1. in pc under the stability semantics,
2. in pc under the admissibility semantics, and
3. in co-NPc under the preferability semantics.

Proof: 1. Only polynomially many C-oracle calls are needed to verify that a given assumption set fl does not attack itself and it attacks all assumptions a (/. fl.

2. The following deterministic, polynomial-time algo­ rithm using a C-oracle decides whether a given assump­ tion set fl is admissible:

• (a) Verify that fl does not attack itself (Jill calls to a C-oracle).

• (b) Compute A*={aEA-~1~ does not attack a} (lA- ~~ calls to a C-oracle).
• (c) Verify that A* U ~does not attack~. (Polynomially many C-oracle calls).

If test (c) fails, then ~ is not admissible, since A* U ~ attacks ~ but, by (b), ~ does not attack A* and, by (a), ~ does not attack itself. 2 Otherwise, let ~~ be any attack against ~. If~~ <; A* U ~' then, by monotonicity of the underlying derivability, A* U ~ attacks ~' thus contradicting that test (c) succeeds. Therefore, ~~ Cl A* U ~. Let a E ~~-A* - ~. By (b), ~ attacks a. Thus, ~ attacks~~ and, by (a), ~ is admissible.

1. The following nondeterministic, polynomial-time algorithm using a. pc -oracle decides whether a. given as­ sumption set ~ is not preferred:
2. Verify that ~ is admissible (one call to a pc_oracle, by part (2)). If not, succeed, otherwise
3. Guess a set ~~ ::J ~.
4. Verify that~~ is admissible (one call to a pc_oracle, by part (2)). If it is, succeed, else fail. ·

The guess-and-verify algorithm and Theorem 2 di­ rectly give upper bounds for the credulous and (co­ )sceptica.l reasoning problems. However, properties Prop1 and Prop2 in section 2 allow to reduce these up­ per bounds. Indeed, by Prop1 , credulous reasoning un­ der the preferability semantics is equivalent to credulous reasoning under the admissibility semantics, and the two problems have the same upper bounds. Moreover, by Prop2 , the sceptical reasoning problem under the admis­ sibility semantics reduces to the underlying derivability problem. As a consequence, the following upper bounds hold, for flat frameworks with a derivability problem in C:

In particular, the credulous reasoning problem for sta­ bility, admissibility and preferability semantics is in NP for LP and in I:~ for DL, the sceptical reasoning problem for the stability semantics is in co-NP for LP and II~ for DL, the sceptical reasoning problem for the admissibility semantics is in P for LP and co-NP for DL, and the scep­ tical reasoning problem for the preferability semantics is in II~ for LP and II~ for DL. The results summarised in section 3 imply that these upper bounds are tight for the stability semantics. Since the sceptical reasoning problem for the admissibility semantics reduces to the derivability problems in the underlying monotonic logic for LP and DL, and these are P-complete and co-NP­ complete, respectively, the corresponding upper bounds are also tight. In the next section we will prove that the remaining upper bounds are tight as well.

2 See that if the framework is not flat, the set of assump­ tions A · U 6 need not to be closed. Therefore, even if (c) fails , 6 can be still admissible, since it can be the case that 6 attacks an assumption that is derivable from A · U 6.

5 Completeness Results

By instantiating the generic upper bounds of the previ­ ous section to the concrete reasoning problems we con­ sider in the following, we obtain the necessary member­ ship results. Therefore, in order to show completeness, it is sufficient to prove hardness.

The next two results show that credulous reasoning under the admissibility and preferability semantics is as hard as under the stability semantics. Intuitively, this is the case because the number of assumption sets that need to be considered under the admissibility semantics is not smaller than under the stability semantics, and it can be, as in the case of stability, exponentially large.

The following theorem is a direct corollary of the result by Sacca [1997] that the expressive power of DATALO�~ queries under the "possible M-stable semantics" (corre­ sponding to credulous reasoning under the preferabil­ ity semantics) is DB-NP, i.e., such queries characterise all collections of databases that are recognisable in N P. From that it is immediate that credulous reasoning in propositional logic programs is NP-complete.

Theorem 3 Credulous reasoning in LP under the ad­ missibility and preferability semantics is N P -complete.

As one would expect, reasoning in DL increases the computational complexity to the second level of the poly­ nomial hierarchy.

Theorem 4 Credulous reasoning in DL under the ad­ missibility and preferability semantics is I:~ -complete.

Proof: We have seen that credulous reasoning under the preferability semantics coincides with credulous rea­ soning under the admissibility semantics. We prove the theorem by a straightforward reduction from 2-QBF to the credulous reasoning problem under the admissibil­ ity semantics. Assume the quantified boolean formula :lp1, ... ,pn 'r/q1, ... ,qmiP, with iP a formula in 3CNF over the propositional variables p1 , .. . ,pn, Q1 , .. . , Qm· We con­ struct a default theory (0, D) such that the given quanti­ fied boolean formula is true iff some admissible argument for (0, D) contains iP.

The language of (0, D) consists of atoms p1 , ... ,Pn· D consists of the default rules

for each i = 1, ... , n (simulating the choice of a truth value for the proposi tiona! variable Pi in iP).

Obviously, this construction of (0, D) can be done in log-space. Moreover, it is easy to see that the given 2QBF is true iff there exists an admissible extension of (0, D) containing iP. ·

As noted earlier, sceptical reasoning under the admis­ sibility semantics is "trivial" in the sense that it reduces to the underlying derivability problem. Therefore, the sceptical reasoning problem needs to be considered only for the preferability semantics. Theorem 2 suggests that this problem has higher complexity than the correspond­ ing problem under the stability semantics, since in order to verify that a set is preferred we need to check that none of its supersets is admissible. The following two theorems show that we cannot do better than this.

Again Sacca [1997] has shown that the expressive power of DATALO�~ queries under the "definite M­ stable semantics" (corresponding to sceptical preferabil­ ity semantics) coincides with the class DB-II~. Hence, as a corollary we immediately obtain the following result.

Theorem 5 Sceptical reasoning in LP under the prefer­ ability semantics is II~ -complete.

We now show that sceptical reasoning has a similar effect on DL.

Theorem 6 Sceptical reasoning in DL under the prefer­ ability semantics is II~ -complete.

Proof: We show that co-sceptical reasoning is ~~-hard by a reduction from 3-QBF. Assume the following quanti­ fied boolean formula: :lpi, .. . ,pn Vqi, .. . ,qm :lri, .. . ,rk~, with ~ a formula in 3CNF over the propositional vari­ ables PI,···,Pn, QI, ... ,qm, ri, . . . ,rk. We build a de­ fault theory (0, D) such that the given quantified boolean formula is true iff some sentence F is not contained in some preferred argument for (0, D).

The language of (0,D) contains atoms PI , · . . ,pn, QI, ... ,qm, and ri, ... ,rk as well as atoms ti, ... ,tn, SI , ... , Sm, intuitively holding if a truth value for the variables PI, .. . ,pn, QI , ... , Qm has been chosen. D consists of

for each i = 1, ... , n, j = 1, ... , m (to indicate that vari­ ables are assigned either true or false, but not both, and that a truth value for Pi and Qj has been chosen),

(to prohibit truth choices on Qj that render~ satisfiable),

for each i = 1, ... , n, j = 1, ... , m (to enforce that truth value choices are made either for all Qj 's or for no Qj and truth value choices are made either for all Pi's or for none of the p;'s and qj's), and

for each i = 1, ... , n, j = 1, ... , m (to guarantee that no admissible set contains M~ or any of M-.ti and M·sj).

We will prove that the given quantified boolean for­ mula is true iff there is a preferred argument not con­ taining F=l\j=I,.,mSj·

If v is a truth assignment to the Pi's, we denote by ~~ the assumption set { M(pi 1\ ti)lv(pi) = true} U { M( 'Pi 1\ t;)lv(pi) = false}. Similarly, we denote by ~~ the assumption set {M(qi 1\ si)lv(qi) = true} U {M(-.qi 1\ si)lv(qi) = false} for some truth assignment v to the Qi's.

First of all, it is obvious that no admissible set can contain any of the assumptions M ~, M ·si, M ·ti. Fur­ thermore, it is easy to see that for any truth assignment v to the Pi's, the set ~~ is an admissible set. Moreover, every preferred assumption set must contain a set ~~ for some truth assignment v to the Pi's. Finally, if ~~ is not preferred, then there exists a truth assignment u to the Qi 's such that ~~ U ~~ is preferred.

Assume that the quantified boolean formula is true under a particular truth assignment u to the Pi 's. We will show that the set ~~ is a preferred assumption set. Suppose that we try to extend ~~by adding to it the set ~ k for some truth assignment k to the Qi 's. If the new set is admissible, it means that it counter attacks the attack M~, ie. ·~ E Th(D U ~~ U ~%),hence the QBF is not true for the truth assignment u, a contradiction. Hence, Th(D U ~~) is a preferred argument that does contain F=l\j=I,.,mSj.

Conversely, assume that (0, D) has a preferred ar­ gument P = Th(D, ~) that does not contain F = 1\j=I,.,mSj· Clearly~~<::;;~' for some truth assignment v to the Pi's. Since Pis preferred and does not contain F, none of the sets ~~ U ~k, for every possible truth assignment k to the Qi 's is admissible. This means that none of these sets of assumptions can counter attack the attack M ~ and derive ·~, therefore the QBF is true.

Obviously, the above construction can be done in log­ space. Thus, the construction of (0, D) is a log-space reduction from 3-QBF to co-sceptical reasoning in DL under preferred arguments and ~~-hardness holds. ·

It should be noted that similar results to those for DL have been recently obtained for the case of disjunctive logic programs [Eiter et al., 1998].

6 Discussion

We have shown that credulous reasoning in DL and LP using the admissibility and preferability semantics is as hard as it is under the standard, stability semantics. Moreover, sceptical reasoning under the preferability se­ mantics is harder than under the stability semantics.

There appears to be a clash between these results and the intuition spelled out in the Introduction, namely, that admissibility and preferability arguments are seem­ ingly easier to compute than stable extensions. However, our results are not as surprising as they might appear. Since the admissibility and preferability semantics do not restrict the number of extensions, one would expect that nonmonotonic reasoning under these semantics is as hard as under the stability semantics. The higher complexity of the sceptical reasoning problem under the preferabil­ ity semantics is due to the fact that in order to verify that an assumption set is preferred, one needs to check that none of its supersets is admissible.

Of course, our results do not contradict the expecta­ tion that in practice constructing admissible arguments is often easier than constructing stable extensions. For example, given the propositional logic program P U {p} , with P any set of clauses not defining the atom p, the empty set is an admissible argument for the query p that can be constructed "locally", without accessing P . Moreover, if PU {p} is stratified or order-consistent [Bon­ darenko et al., 1997], p is guaranteed to be a credulous consequence of the program under the stability seman­ tics. Indeed, in all cases where the stability seman­ tics coincides with the preferability semantics (e.g. for stratified and order-consistent abstract frameworks) any sound (and complete) computational mechanism for the admissibility semantics is sound (and complete) for the stability semantics.

The "locality" feature of the admissibility seman­ tics renders it a feasible alternative to the stability semantics in the first-order case, when the proposi­ t ional version of the given abstract framework is infi­ nite. For example, given the (negation-free) logic pro­ gram: {q(f(X)); p(O)} , the empty set of assumptions is an admissible argument for the query p(O) that can be constructed "locally", even though the propositional version of the corresponding abstract framework is infi­ nite.

The complexity results in this paper discredit sceptical reasoning under admissibility and preferability seman­ t ics as trivial and "unnecessarily" complex, respectively. However , this does not seem to matter for the envisioned applications of this semantics, because credulous reason­ ing only is required for these applications [Kowalski and Toni, 1996]. For example, in argumentation in practi­ cal reasoning in general and legal reasoning in particu­ lar, unilateral arguments are put forwards and defended against all counterarguments, in a credulous manner. In­ deed, these domains appear to be particularly well suited for credulous reasoning under the admissibility seman­ tics.

Acknowledgements

The first author has been partially supported by the DFG as part of the graduate school on Human and Ma­ chine Intelligence at the University of Freiburg and the third author has been partially supported by the UK EPSRC project "Logic-based multi-agent systems." We would also like to thank the anonymous reviewers for their comments on an earlier version of this paper.