On the computational complexity of assumption-based argumentation for default reasoning.
Bondarenko et al. have recently proposed an abstract framework for default reasoning. Besides capturing most existing formalisms and proving that their standard semantics all coincide, the framework extends these formalisms by generalising the semantics of admissible and preferred arguments, originally proposed for logic programming only.In this paper we analyse the computational complexity of credulous and sceptical reasoning under the semantics of admissible and preferred arguments for (the propositional variant of) the instances of the abstract framework capturing theorist, circumscription, logic programming, default logic, and autoepistemic logic. Although the new semantics have been tacitly assumed to mitigate the computational hardness of default reasoning under the standard semantics of stable extensions, we show that in many cases reasoning under the admissibility and preferability semantics is computationally harder than under the standard semantics. In particular, in the case of autoepistemic logic, sceptical reasoning under preferred arguments is located at the fourth level of the polynomial hierarchy, whereas the same form of reasoning under stable extensions is located at the second level.
Introduction
Bondarenko et al. [1] show that many logics for default reasoning, i.e., theorist
[25], (many cases of) circumscription [20], Default Logic (DL) [26], Nonmonotonic
Modal Logic [21], Autoepistemic Logic (AEL) [22], and Logic Programming
(LP) can be understood as special cases of a single abstract framework. The
standard semantics of all these logics can be understood as sanctioning a set of
assumptions as a stable extension of a given theory, formulated in an underlying
monotonic logic, iff the set of assumptions does not attack itself and it attacks
every assumption not in the set. In abstract terms, an assumption can be attacked
if its contrary can be proved, in the underlying monotonic logic, possibly with the
aid of other conflicting assumptions.
Bondarenko et al. also propose two new semantics generalising, respectively,
the admissibility semantics [8] and the semantics of preferred extensions [8] or
partial stable models [27] for LP. In abstract terms, a set of assumptions is an
admissible argument of a given theory, formulated in an underlying monotonic
logic, 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 (with respect
to set inclusion) admissible argument.
The new semantics are more general than the stability semantics since every
stable extension is a preferred (and admissible) argument, but not every preferred
argument is a stable extension. Moreover, the new semantics are more liberal
because for most concrete logics for default reasoning, admissible and preferred
arguments are always guaranteed to exist, whereas stable extensions are not. Fi-
nally, reasoning under the new semantics appears to be computationally easier
than reasoning 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 assumption whether it
or its contrary can be derived, independently of the sentence to be justified. 1 For
the semantics of admissible and preferred arguments, however, a "local" 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 [18, 6, 7].
1 See [18, 7] for a more general discussion of the problems associated with computing the
stability semantics.
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 default reasoning are still present. There
are potentially exponentially many assumption sets sanctioned by the semantics.
Further, 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 complexity as under
the stability semantics, i.e., it is complete for the first level of the polynomial
hierarchy for LP and on the second level for logics with full propositional logic
as the underlying logic [3]. However, previous results on the expressive power of
queries by Sacc-a [28] suggest that this is not the case for LP. Indeed,
Sacc-a's results imply that reasoning under the preferability semantics for LP is at
the second level of the polynomial hierarchy.
In this paper we extend this analysis and provide complexity results for reasoning
in the propositional variants of theorist, circumscription, LP, DL, and AEL
under the new semantics. As it turns out, reasoning under the new semantics can
be much harder than reasoning under the standard semantics. In particular, we
show that sceptical reasoning in DL under the preferability semantics is on the
third level of the polynomial hierarchy, that credulous reasoning in AEL under
the admissibility semantics is on the third level of the polynomial hierarchy, and
that sceptical reasoning in AEL under the preferability semantics is on the fourth
level of the polynomial hierarchy.
The paper 2 is organised as follows. Section 2 summarises relevant features
of the abstract framework of [1], its semantics and concrete instances. Section 3
gives complexity theory background and introduces the reasoning problems. Section
4 gives generic upper bounds for credulous and sceptical reasoning, parametric
with respect to the complexity of the underlying monotonic logics. The
generic results are instantiated to provide upper bounds for concrete instances of
the abstract framework. Section 5 gives then completeness results for theorist and
circumscription, Section 6 gives the completeness results for LP and DL, and Section
7 gives the completeness results for AEL. Section 8 discusses the results and
concludes.
This paper combines earlier papers [4, 5] by the same authors and it contains all formal proofs
of the results in full.
Reasoning via Argumentation
Assume a deductive system (L, R), where L is some formal language with
countably many sentences and R is a set of inference rules inducing a monotonic
derivability notion '. Given a theory T  L and a formula  2 L,
is the deductive closure of T . Then, an abstract
(assumption-based) framework is a triple hT; A; i, where T; A  L and is
a mapping from A into L. T , the theory, is a set of beliefs, formulated in the underlying
language, and can be extended by subsets of A, the set of assumptions.
Indeed, an extension of an abstract framework hT; A; i is a theory Th(T [
with   A (sometimes an extension is referred to simply as T [ or ). Finally,
given an assumption  2 A,  denotes the contrary of .
Theorist can be understood as a framework hT; A; i where T and A are both
arbitrary sets of sentences of classical (first-order or propositional) logic and the
contrary  of an assumption  is just its negation. ' is ordinary classical provability

Many cases of circumscription 3 can be understood similarly, except that the
assumptions are negations of atomic sentences :p(t), for all predicates p which
are minimised, and atomic sentences q(t) or their negations, for all predicates q
which are fixed.
LP is the instance of the abstract framework hT; A; i where T is a logic pro-
gram, the assumptions in A are all negations not p of atomic sentences p, and the
contrary not p of an assumption is p. ' is Horn logic provability, with assump-
tions, not p, understood as new atoms p  , as in [12].
DL is the instance of the abstract framework hT; A; i where the monotonic
logic is first-order logic augmented with domain-specific inference rules of the
are sentences in classical logic. T is a classical theory and A
consists of all expressions of the form M where  is a sentence of classical
logic. The contrary M of an assumption M is :.
AEL has, as the underlying language L, a modal logic with a modal operator
L, but the inference rules are those of classical logic. The assumptions have the
form :L or L. The contrary of :L is , and the contrary of L is :L.
3 Namely, all cases where every model of the theory to be circumscribed is a Herbrand model
of the theory, see [1] for more details.
Given an abstract framework hT; A; i and an assumption set   A:
attacks an assumption  2 A iff
attacks an assumption set  0  A iff  attacks some assumption  2
Given that an assumption set   A is closed iff
the standard semantics of extensions of theorist [25], minimal models of circumscription
[20], extensions of DL [26], stable expansions of AEL [22], and stable
models of LP [14] correspond to the stability semantics of abstract frameworks,
where an assumption set   A is stable iff
1.  is closed,
2.  does not attack itself, and
3.  attacks each assumption  62 .
Assumption sets are always closed in the case of LP and DL. Frameworks
with this property are referred to as flat [1]. Assumption sets might not be closed
in the case of AEL. For example, given the theory in AEL, the
empty assumption set is not closed. Furthermore, assumption sets might not be
closed in the case of theorist and circumscription. For example, if a formula is
an assumption in theorist that is already derived by the theory, then the empty
assumption set is not closed.
A stable extension is an extension Th(T [) for some stable assumption set
. The standard semantics of circumscription [20] corresponds to the intersection
of all stable extensions of the abstract framework corresponding to circumscription

Bondarenko et al. argue that the stability semantics is unnecessarily restric-
tive, because it insists that an assumption set should take a stand on every issue
(assumption). Thus, they define new semantics for the abstract framework, by
generalising the argumentation-theoretic reformulation of [17] for the semantics
originally proposed for LP by Dung [8]. The new semantics are defined in terms
of "admissible" and "preferred" sets of assumptions/extensions. An assumption
set   A is admissible iff
1.  is closed,
2.  does not attack itself, and
3. for all closed sets of assumptions  0  A, if  0 attacks  then  attacks
Maximal (with respect to set inclusion) admissible assumption sets are called
preferred. In this paper we use the following terminology: an admissible (pre-
ferred) argument is an extension Th(T [ ) for some admissible (preferred)
assumption set . Bondarenko et al. show that preferred arguments correspond
to preferred extensions [8] and partial stable models [27] for LP.
Every stable assumption set/extension is preferred (and thus admissible) [1,
Theorem 4.6], but not vice versa, in general. However, if the framework is nor-
mal, i.e., if every maximal closed assumption set that does not attack itself is
a stable set, then the semantics of preferred and stable assumption sets coincide
[1, Theorem 4.8]. Theorist and circumscription are normal frameworks, which
implies that stability and preferability semantics are identical in these cases.
In the sequel we will use the following:
preferred assumption set is (trivially) admissible and every admissible
assumption set is a subset of some preferred assumption set;
The empty assumption set is always admissible, trivially, for all flat
frameworks;
preferred extension is stable and every stable extension is pre-
ferred, for all normal frameworks.
Moreover, for any given semantics amongst the stability, admissibility and
preferability semantics, we will use the terminology that "a set of assumptions is
sanctioned by a semantics" to mean that the set of assumptions is stable/admissible/preferred,
respectively.
Reasoning Problems and Computational Complexit

We will analyse the computational complexity of the following reasoning problems
for the propositional variants of the frameworks for theorist, circumscription,
LP, DL, and AEL under admissibility and preferability semantics:
the credulous reasoning problem, i.e., the problem of deciding for any
given sentence assumption set
sanctioned by the semantics;
the sceptical reasoning problem, i.e., the problem of deciding for any
given sentence ' 2 L whether ' 2 Th(T [ ) for all assumption sets
sanctioned by the semantics.
Instead of the sceptical reasoning problem, we will often consider its complementary
problem, i.e.
the co-sceptical reasoning problem, i.e, the problem of deciding for any
given sentence ' whether ' 62 Th(T [ ) for some assumption set
sanctioned by the semantics.
Note that we are not advocating co-sceptical reasoning as interesting or useful
epistemologically. Rather, we use it to support our complexity analysis.
In addition, we will consider a sub-problem of all these problems, namely:
the assumption set verification problem, i.e., the problem of deciding
whether a given set of assumptions  is sanctioned by the semantics.
We briefly revise fundamental notions from complexity theory. 4 We assume familiarity
with the complexity classes P, NP, and co-NP, and with the notions
of many-one-reductions, Turing reductions, and hardness and completeness with
respect to these reductions.
The complexity of the above problems for all frameworks and semantics we
consider is located at the lower end of the polynomial hierarchy. This is a (pre-
sumably) 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 decision
problems. Then, P C denotes the class of problems that can be solved on
a deterministic oracle machine in polynomial time with an oracle that decides a
problem in C. In general, for any class X defined by resource bounds, X C denotes
the class of problems decidable on a Turing machine with a resource bound given
4 Good textbooks covering the notions we introduce here have been written by Garey and Johnson
[13] and Papadimitriou [24].
by X and an oracle for a problem in C. 5 Based on these notions, the sets  p
and  p
are defined as follows: 6
The "canonical" complete problems are SAT for  p
1 =NP and k-QBF for  p
is the problem of deciding whether the quantified boolean
| {z }
alternating quantifiers starting with 9
is true, for a formula . The above problems remain complete for their respective
classes when the innermost quantifier is 9 and the formula  is in 3CNF, as well
as when the innermost quantifier is 8 and the formula  is in 3DNF [30]. The
complementary of a k-QBF problem, denoted by co-k-QBF, is complete for  p
k .
All problems in the polynomial hierarchy can be solved in polynomial time
these problems can be solved by worst-case exponential
time algorithms. Thus, the polynomial hierarchy might not seem too meaning-
ful. However, different levels of the polynomial hierarchy differ considerably in
practice, e.g. methods working for moderately sized instances of NP-complete
problems do not work for  p
-complete problems.
The complexity of the problems we are interested in has been extensively studied
for existing logics for default reasoning under the standard, stability semantics
[3, 15, 23, 19, 29, 2, 10].

Table

1 gives a partial summary of these results
for the different logics. We note here that the semantics of circumscription has
been originally proposed with respect to sceptical reasoning only. In this case, as
shown in [1], reasoning in circumscription (restricted to Herbrand models) coincides
with sceptical reasoning in theorist under the stability semantics. Moreover,
we can naturally extend circumscription and define its credulous reasoning via a
one-to-one correspondence with credulous reasoning in theorist under the stability
semantics (see [1] for more details). Hence the complexity result for credulous
reasoning in circumscription is a direct consequence of the respective result for
5 Note that because using an oracle for a problem from C is identical to using an oracle for a
problem from co-C, we have X . For this reason, one usually does not use the notation
6 The super-script p is only used to distinguish these classes from the analogous classes in the
Kleene hierarchy.
theorist. The complexity results for reasoning in circumscription under the admissibility
semantics, presented later in the paper, can be understood in a similar
way.
credulous sceptical
reasoning reasoning
Logic Programming NP-complete co-NP-complete
Theorist  p
Circumscription  p-complete  p-complete
Autoepistemic Logic  p-complete  p-complete

Table

1: Existing computational complexity results for the stability semantics
4 Generic Upper Bounds
In this section we give a number of generic upper bounds for reasoning under the
admissibility and preferability semantics that are parametric on the complexity
of the derivability problem in the underlying monotonic logic. This allows us to
derive upper bounds for a wide range of concrete logics for default reasoning.
In the case of LP, the underlying logic is propositional Horn logic, hence the
derivability problem is P-complete (under log-space reductions) [24, p. 176]. In
the case of theorist, circumscription and AEL, the underlying logic is classical
propositional logic, hence the derivability problem is co-NP-complete. Finally,
in the case of DL, the underlying monotonic derivability is classical derivability
extended with domain-specific inference rules. However, these extra inference
rules do not increase the complexity of reasoning. Indeed, it is known (e.g. see
[16, p.90]) that for any DL-like propositional monotonic rule system S, checking
whether S 6j= ' is NP-complete. Therefore, the following proposition follows
immediately.
Proposition 1 Given a DL framework hT; A; i, deciding for a sentence ' 2 L
and an assumption set A whether '2Th(T [ ) is co-NP-complete.
In order to decide the credulous and co-sceptical reasoning problems, one can
apply the following non-deterministic algorithm:
Algorithm 2
1. Guess an assumption set,
2. verify that it is sanctioned by the semantics, and
3. verify that the formula under consideration is derivable from the set of assumptions
and the monotonic theory or not derivable from it, respectively.
From this it follows that credulous reasoning and co-sceptical reasoning is in the
complexity class NP C , provided reasoning in the underlying logic is in C and the
verification that an assumption set is sanctioned by the semantics can be done with
polynomially many calls to a C-oracle. For the stability semantics, we need indeed
only polynomially many C-oracle calls in order to verify that the assumption set
is not self-attacking and that it is closed and attacks all assumptions  62 .
However, for the admissibility and preferability semantics the verification step
does not seem to be so easy, as suggested by the following theorem.
Theorem 3 For frameworks with an underlying monotonic logic with a derivability
problem in C, the assumption set verification problem is
in P C under the stability semantics,
in co-NP C under the admissibility semantics, and
in co-NP NP C
under the preferability semantics.
Proof: The first claim follows from the argument above that polynomially many
C-oracle calls are sufficient to verify that an assumption set is stable.
In order to prove the second claim, we give the following nondeterministic,
polynomial-time algorithm that uses a C-oracle and decides whether   A is not
admissible:
1. Check whether  is closed. If not, succeed, otherwise continue.
2. Guess an assumption set  0  A.
3. Verify that  0 is closed, using jA  0 j C-oracle calls.
4. Verify that  0 attacks , using jj C-oracle calls.
5. Verify that  does not attack  0 , using calls.
Obviously, this algorithm succeeds iff  is not admissible, i.e., it decides the
complement of the assumption set verification problem, thus proving the claim.
In order to prove the third claim, for any assumption set   A that we want
to verify, we give the following nondeterministic, polynomial-time algorithm that
uses an NP C -oracle:
1. Check whether  is admissible, using one NP C -oracle call (by the second
claim). If it is not, succeed. Otherwise continue.
2. Guess an assumption set  0  .
3. Check whether  0 is admissible, using one NP C -oracle call (by the second
claim). If it is, succeed. Otherwise fail.
Obviously, this algorithm succeeds iff  is not preferred. This means it decides
the complement of the assumption set verification problem, thus proving
the claim.
Furthermore, in the general case, there does not appear to be more efficient
algorithms for the assumption set verification problems than the ones given in
Theorem 3. For the special flat and normal frameworks, however, more efficient
algorithms can be found, as demonstrated by the following two theorems.
Theorem 4 For flat frameworks with an underlying monotonic logic with a derivability
problem in C, the assumption set verification problem is
in P C under the admissibility semantics, and
in co-NP C under the preferability semantics.
Proof: We prove the first claim by giving the following deterministic, polynomial-time
algorithm using a C-oracle, for any assumption set   A that we want to
verify:
1. Check whether  attacks itself, using polynomially many C-oracle calls. If
it does, succeed. Otherwise continue.
2. Compute does not attack g, using jA j calls to
a C-oracle.
3. Check whether A  [  attacks , using polynomially many C-oracle calls.
If it does, succeed. Otherwise fail.
It is easy to see that if this algorithm succeeds then  is not admissible, as A  [
attacks  but, by (2),  does not attack A  and, by (1),  does not attack itself. 7
Moreover, if the algorithm fails then  is admissible. Indeed, let  0 be any attack
against . If  0  A  [, then, by monotonicity of the underlying logic, A  [
attacks , thus contradicting that the algorithm fails. Therefore,  0 6 A  [ .
Let  2  0 A  . By (2),  attacks . Thus,  attacks  0 , and, by (1),  is
admissible.
The second claim of the theorem follows by reconsidering the algorithm used
in the proof of Theorem 3 for the third claim, but using P C -oracle calls at steps (1)
and (3).
Due to (Prop 3 ), for normal frameworks the assumption set verification task
under the preferability semantics is easier, as it can be reduced to that under the
stability semantics. Therefore, the following result is a direct corollary of Theorem
3.
Proposition 5 For normal frameworks with an underlying monotonic logic with
a derivability problem in C, the assumption set verification problem under the
preferability semantics is in P C .
We could now apply directly algorithm 2 described above in combination with
the above results for deriving upper bounds for the credulous and sceptical reasoning
problems. However, some of the upper bounds thus obtained can be reduced,
as follows.
Directly from (Prop 1 ), we have the following result.
7 Note that if the framework is not flat, then the assumption set A  [  might not be closed.
Therefore, even if (3) succeeds,  can still be admissible, as it may attack an assumption that is
derivable from A  [ .
Proposition 6 Credulous reasoning under the admissibility semantics is equivalent
to credulous reasoning under the preferability semantics.
Thus, it follows directly that credulous reasoning under the admissibility semantics
has the same upper bound as credulous reasoning under the preferability
semantics. In particular, for normal frameworks we get the same upper bound for
credulous reasoning under the admissibility semantics as for the stability semantics

In addition, co-sceptical and sceptical reasoning under the admissibility semantics
is often much simpler than suggested by the upper bounds of the respective
assumption set verification problem combined with algorithm 2. For example,
in flat frameworks hT; A; i the sceptical reasoning problem reduces to the classical
derivability from the theory T , because of (Prop 2 ). This might be the case
even for non-flat frameworks. We call an assumption-based framework hT; A; i
simple iff there is no admissible assumption set whenever T is inconsistent in the
underlying monotonic logic 8 , and otherwise there exists a minimal (with respect
to set inclusion) admissible set
Proposition 7 For flat frameworks and for simple frameworks with an underlying
monotonic logic with a derivability problem in C, the sceptical reasoning problem
under the admissibility semantics is in C.
All the results in this section combined with algorithm 2 give the next the-
orem, specifying upper bounds for the reasoning problems for all the types of
frameworks considered so far.
Theorem 8 Upper bounds for the different reasoning problems, types of frame-
works, and semantics are as specified in the following table:
Frameworks Stability Admissibility Preferability
cred. scept. cred. scept. cred. scept.
general NP C co-NP C NP NP C
co-NP NP NP C
normal NP C co-NP C NP C co-NP NP C
flat NP C co-NP C NP C C NP C co-NP NP C
simple NP C co-NP C NP NP C
co-NP NP NP C
8 Note that not all deductive systems underlying an abstract framework are equipped with a
notion of inconsistency. For example, the instance of the framework for LP is not. Moreover, note
that the notion of inconsistency is a separate notion from that of contrary.
Proof: The results for the stability semantics follow from applying algorithm 2,
with step (2) of the algorithm solvable by a call to a P C oracle (by Theorem 3), and
step (3) solvable by a call to a C-oracle. This gives an upper bound of NP P C
, which
coincides with NP C , for both the credulous and co-sceptical reasoning problems.
The results for the admissibility semantics in the first row and for sceptical
reasoning under the preferability semantics in the first row follow by the same
argument.
The result for credulous reasoning under the preferability semantics in the first
row follows from Proposition 6 and the corresponding result for the admissibility
semantics.
The results for admissibility and preferability semantics in the second row are
justified as follows. Credulous reasoning under admissibility and preferability
semantics as well as co-sceptical reasoning under the preferability semantics can
be shown to be in NP P C
, which equals NP C , by using algorithm 2 and applying
Propositions 6 and 5. Further, the upper bound for sceptical reasoning under the
admissibility semantics is the general upper bound given in the first row.
The results for admissibility and preferability semantics in the third row follow
by applying Proposition 7 for sceptical reasoning under admissibility and, for the
other columns, algorithm 2 and Theorem 4.
Finally, the results for admissibility and preferability semantics in the fourth
row are the general results in the first row, with the exception of the result for
sceptical reasoning under the admissibility semantics given by Proposition 7.
As shown in the table, the upper bounds derived for sceptical reasoning under
the admissibility semantics are sometimes lower than those derived for sceptical
reasoning under the stability semantics. However, in these cases it amounts to
deriving monotonic conclusions from the theory T and ignoring the assumptions
completely. In other words, in these cases, default reasoning is trivialised.
5 Simple, Normal Frameworks: Theorist and Cir-
cumscription
The concrete frameworks for theorist and circumscription are normal [1] and sim-
ple, as shown below.
Lemma 9 The frameworks for theorist and circumscription are simple.
Proof: Circumscription is a special instance of theorist. Thus, we only need to
prove the theorem for theorist.
If the given theorist theory T is inconsistent then the corresponding framework
admits no admissible argument, as any closed assumption set attacks itself.
Assume that T is consistent. Then, we only need to prove that
attacks every closed assumption set  0 which attacks . Now, if ;, then there
is no set  0 that attacks . If  6= ;, then  0 attacks  iff T [  0 is inconsistent
and, as  0 is closed,  A. Thus, necessarily  attacks  0 .
For both frameworks, the credulous and sceptical reasoning problems reach
the respective upper bounds specified in Theorem 8. Indeed, due to Proposition 6
and (Prop 3 ), credulous reasoning under admissibility and preferability semantics
is identical to credulous reasoning under the standard, stability semantics, leading
to the result that the complexity is also identical. Thus, the next proposition
follows immediately from the results in Table 1.
Credulous reasoning in theorist and circumscription under the
admissibility and preferability semantics is  p-complete.
Directly by (Prop 3 ), sceptical reasoning under the preferability semantics is
identical to sceptical reasoning under the stability semantics. Thus, the next
proposition follows immediately from the results in Table 1.
Proposition 11 Sceptical reasoning in theorist and circumscription under the
preferability semantics is  p-complete.
Finally, sceptical reasoning under the admissibility semantics is trivial because
the frameworks are simple and sceptical reasoning reduces to monotonic derivability
from the theory.
Proposition 12 Sceptical reasoning in theorist and circumscription frameworks
under the admissibility semantics is co-NP-complete.
In other words, for the concrete frameworks for theorist and circumscription,
we either get the same results as under the stability semantics or we get trivial
results.
6 Flat Frameworks: Logic Programming and Default
Reasoning
As in the case of theorist and circumscription, in the case of LP and DL the upper
bounds specified in Theorem 8 are tight.
Since the concrete framework for LP is flat, sceptical reasoning under the
admissibility semantics reduces to reasoning in the underlying monotonic logic,
i.e., derivability in propositional Horn theories, which is P-complete.
Proposition 13 Sceptical reasoning in LP under the admissibility semantics is
P-complete.
From Theorem 8, again because the LP framework is flat, credulous reasoning
under the admissibility and preferability semantics is in NP P , which equals
NP. NP-completeness can be obtained as a direct corollary of an earlier result
by Sacc-a [28], that the expressive power of DATALOG : queries under the "pos-
sible M-stable semantics" (corresponding to credulous reasoning under the admissibility
and preferability semantics) coincides with DB-NP, i.e. the class of
all databases that are recognisable in NP. From this result the following theorem
immediately.
Theorem 14 Credulous reasoning in LP under the admissibility and preferability
semantics is NP-complete.
Again from Theorem 8, sceptical reasoning in LP under the preferability semantics
is in co-NP NP P
, which coincides with  p
2 -completeness can be obtained
again as a direct corollary of the result proven again by Sacc-a [28], that the
expressive power of DATALOG : queries under the "definite M-stable semantics"
(corresponding to sceptical preferability semantics) coincides with the class DB-
2, i.e. the class of all databases that are recognisable in DB- p. From this result
the following theorem follows immediately.
Theorem 15 Sceptical reasoning in LP under the preferability semantics is  p-
complete.
Therefore, for LP, credulous reasoning under admissibility and preferability
semantics has the same complexity as under the stability semantics (see Table 1),
whereas sceptical reasoning is either one level lower but trivial, under the admissibility
semantics, or one level higher, under the preferability semantics, than under
the stability semantics.
Since the instance of the framework for DL is flat, sceptical reasoning under
the admissibility semantics reduces to reasoning in the underlying monotonic
logic, i.e., derivability in propositional classical logic, which is co-NP-complete.
Proposition Sceptical reasoning in DL under the admissibility semantics is
co-NP-complete.
By Proposition 6, credulous reasoning under the preferability semantics coincides
with credulous reasoning under the admissibility semantics. From Theorem
credulous reasoning under the admissibility and preferability semantics is
in NP NP , which coincides with  p.  p-hardness, and therefore  p-completeness,
can be proven by a reduction from 2-QBF.
Theorem 17 Credulous reasoning in DL under the admissibility and preferability
semantics is  p
Proof: By Proposition 6, it suffices to prove the theorem for the admissibility
semantics. Membership follows from Theorem 8. To prove hardness, we use a
straightforward reduction from 2-QBF to the credulous reasoning problem under
the admissibility semantics.
Assume the quantified boolean formula 9p
formula in 3DNF over the propositional variables p 1 We construct
a DL theory (;; D) such that the given quantified boolean formula is true iff
some admissible argument for the framework corresponding to (;; D) contains .
Let D consists of the default rules
for each simulating the choice of a truth value for each propositional
variable p i in . Obviously, (;; D) can be constructed in log-space. Moreover, it
is easy to see that the given 2-QBF is true iff there exists an admissible extension
of the framework corresponding to (;; D) containing .
Again from Theorem 8, in DL, sceptical reasoning under the preferability semantics
is in co-NP NP NP
, which coincides with  p.  p-hardness, and therefore
3 -completeness, can be proven by a reduction from 3-QBF.
Theorem Sceptical reasoning in DL under the preferability semantics is  p-
complete.
Proof: Membership follows from Theorem 8. To prove hardness, we use a reduction
from 3-QBF to the co-sceptical reasoning problem under the preferability
semantics.
Assume the quantified boolean
with  a formula in 3CNF over the propositional variables
We construct a DL theory (;; D) such that is true iff some sentence
F is not contained in some preferred argument for the framework corresponding
to (;; D).
The language of (;; D) contains atoms
well as atoms t intuitively holding true iff a truth value for the
variables respectively, has been chosen. D consists of the
default rules
for each simulating the choice of a truth value for each
to prohibit choices of truth values for all the q j 's that render  satisfiable,
for each to enforce that truth value choices are made
either for all q j 's or for no q j and that truth value choices are made either for all
's or for none of the p i 's and q j 's, and finally
for each to guarantee that no admissible assumption
set contains M or any of M:t i and M:s j .
Obviously, (;; D) can be constructed in log-space. Moreover, we prove that
is true iff there is a preferred argument not containing F =^ j=1;:::;m s j . In other
words, the 3-QBF can be reduced to co-sceptical reasoning in DL under the
preferability semantics.
In the sequel we will use the following terminology. If v is a truth assignment
to the p i 's, we denote by  p
v the assumption set
Similarly, if u is a truth assignment to the q j 's, we denote by  q
u the assumption
set
First of all, it is obvious that no admissible assumption set can contain any of the
assumptions M, M:s i , M:t i (as, if it did, it would attack itself). Furthermore,
it is easy to see that for any truth assignment v to the p i 's, the set  p
v is an admissible
set. Moreover, every preferred assumption set must contain a set  p
v for some
truth assignment v to the p i 's. Finally, if  p
v is not preferred, then there exists a
truth assignment u to the q i 's such that  p
u is preferred.
Assume that is true under a particular truth assignment v to the p i 's. Obvi-
ously,  p
v does not derive F =^ j=1;:::;m s j . We show that the set  p
v is a preferred
assumption set.
Suppose that it is not, and that we can extend  p
v by the set  q
u , for some truth
assignment u to the q i 's, thus obtaining an admissible set. Then,  p
attacks the attack fMg, i.e. : belongs to the extension given by  p
u . As
a consequence, is not true under the truth assignment v: contradiction.
Conversely, assume that the framework corresponding to (;; D) admits a preferred
argument  that does not derive F =^ j=1;:::;m s j . We prove that is true.
there exists some truth assignment v to the p i 's such that  p
v  .
Since  is preferred and it does not contain F , none of the sets  p
every possible truth assignment u to the q i 's, is admissible. This means that none
of these sets of assumptions can counter attack the attack fMg and derive :.
Therefore, is true.
Therefore, as in the LP case, in the DL case credulous reasoning under the
admissibility and preferability semantics has the same complexity as under the
stability semantics (see Table 1), whereas sceptical reasoning is either one level
lower but trivial, under the admissibility semantics, or one level higher, under the
preferability semantics, than under the stability semantics.
Note that similar results to the one obtained above for DL have been recently
obtained for disjunctive logic programming [11].
7 General Frameworks: Autoepistemic Logic
AEL is neither flat, simple, nor normal. This means that we cannot expect any
simplifications when reasoning in AEL frameworks. As a matter of fact, the upper
bounds for general frameworks, which apply of course, are also tight for AEL.
By Proposition 6, credulous reasoning under the preferability semantics coincides
with credulous reasoning under the admissibility semantics. From Theorem
8, since the reasoning problem in the underlying monotonic logic for AEL is
classical reasoning in propositional logic (coNP-complete), credulous reasoning
under the admissibility and preferability semantics is in NP NP NP
, which coincides
with  p.  p-hardness, and therefore  p-completeness, can be proven by a reduction
from 3-QBF.
Theorem 19 Credulous reasoning in AEL under the admissibility and preferability
semantics is  p
3 -complete.
Proof: By Proposition 6, it suffices to prove the theorem for the admissibility
semantics. Membership follows from Theorem 8. To prove hardness, we use a
reduction from 3-QBF to the credulous reasoning problem under the admissibility
semantics.
Assume the following quantified boolean
with  a formula in 3CNF over the propositional variables
We construct an AEL theory T such that is true iff some
sentence F is contained in some admissible argument for the framework corresponding
to T .
The language of T contains atoms
as atoms t intuitively holding if a truth value for the variables p 1
has been chosen, and an atom s used to prevent that any truth value for the q j 's
can be chosen. T consists of the sentences:
for each
Obviously, T can be constructed in log-space. Now we prove that the frame-work
corresponding to T admits an admissible extension containing
iff is true. This means that the given 3-QBF can be reduced to credulous reasoning
under the admissibility semantics.
Assume that the framework corresponding to T admits an admissible extension
deriving F . Then, for each is part of ,
for F to be derived by it. Further, :L: must be part of , for  to be closed,
and thus admissible. Finally, none of the assumptions :L:q i , :Lq i can be part of
, for otherwise , if closed, would attack itself and thus be non-admissible.
Consider any assumption set A that attacks . A must attack one of the assumptions
or :L:. However, if A attacked any of :L:p i , :Lp i ,
then  would immediately counter-attack A. Therefore, for A to be an assumption
set that can possibly render  non-admissible, it must make the same choices on
the p i 's as , and attack :L:. For A to attack :L:, then A must derive :,
by including, in addition to the assumptions from f:L:p
chosen by , assumptions from the set f:L:q j ; :Lq j g j=1;:::;m . Such choices cannot
be counter-attacked by  without making it self-attacking. Therefore, since
is admissible, no such A exists. This means that, for the given choices on the
in , no choices for the q j 's exist that make : true. In other words, for the
given choice of the p i in , and for all choices of the truth values for the q j 's, there
exists an assignment of truth values to the r l 's that makes  true, which implies
that is necessarily true.
Conversely, assume that there is no admissible extension of the framework
corresponding to T deriving F above. Then, regardless of the choices for the p i 's,
there is always an attack on :L:, deriving :, that cannot be counter-attacked
while keeping the candidate set of assumptions non-self-attacking. Then, by the
arguments presented above, the given 3-QBF formula cannot be true.
Again from Theorem 8, sceptical reasoning under the admissibility and preferability
semantics in AEL is in co-NP NP NP
, which coincides with  p.  p-hardness,
and therefore  p
3 -completeness, can be proven by a reduction from 3-QBF.
Theorem 20 Sceptical reasoning in AEL under the admissibility semantics is  p-
complete.
Proof: Membership follows from Theorem 8. To prove hardness, we use a reduction
from 3-QBF to the co-sceptical reasoning problem under the admissibility
semantics.
We use the reduction in the proof of the previous Theorem 19, but extend the
theory T constructed there to the theory T
g.
Any admissible set  must contain the assumptions :L: and L V
for  to be closed. Furthermore, any admissible extension of T 0 must contain V
because otherwise it is attacked by :L V
having a counter-attack. From
this fact and the above observations it follows that T 0 has an admissible extension
iff the given 3-QBF formula is true. Given that if no admissible extension exists
all co-sceptical queries will be answered negatively, the above is equivalent to
the fact that : V
is not a sceptical consequence of T 0 iff is true, i.e., the
construction is a log-space reduction from 3-QBF to co-sceptical reasoning under
the admissibility semantics.
Again from Theorem 8, in AEL, sceptical reasoning under the preferability
semantics is in co-NP NP NP NP
, which coincides with  p.  p-hardness, and therefore
4 -completeness, can be proven by a reduction from 4-QBF.
Theorem 21 Sceptical reasoning in AEL under the preferability semantics is  p-
complete.
Proof: Membership follows from Theorem 8. To prove hardness, we use a reduction
from 4-QBF to the co-sceptical reasoning problem under the preferability
semantics.
Assume the following quantified boolean
with  a formula in 3DNF over the propositional variables
We construct an AEL theory
T such that is true iff a particular sentence F is not contained in some
preferred argument of T .
The language of T contains atoms
as well as atoms t , the latter intuitively holding iff a truth value for the
variables q 1 ;: : :; q m has been chosen. Finally, we have atoms v and w. The atom
v is used to block the truth assignment to the q j 's and w is used to prohibit any
choices on assumptions f:L:r h ; :Lr h g in the preferred argument.
T consists of the following sentences:
for each
Now we claim that there exists a preferred extension not containing
iff is true.
First, one notes that an assumption set containing non-conflicting assumptions
from the set f:L:p is an admissible set. Let  be a maximal such set.
Secondly, it is obvious that  can be expanded (in a non-trivial way) only by
adding the assumption :Lv and assumptions from the set f:L:q g. Let us
call this expanded set  0 . Such a set  0 is only admissible if we make choices
for all q j 's because otherwise  0 can be attacked by :Lt j (using :Lt
which there is no counter-attack from  0 .
Thirdly, the set  0 cannot be further expanded using assumptions from f:L:r h ; :Lr h g,
because these assumptions lead to an immediate self-attack.
Fourthly, an assumption set  0 containing assumptions from f:L:q
together with :Lv can only be admissible if :Lv cannot be attacked by any assumption
set.
The only way to construct an attack A against :Lv in  0 , which is not immediately
counter-attacked by  0 , would be to use all assumptions in  0 and assumptions
from f:L:r h ; :Lr h g. Note that such assumptions cannot be counter-
attacked by  0 . Now the only way to attack :Lv would be to make v true, and in
order to do so, one has to make  true.
Assuming now that  0 is admissible means that for all possible choices for
the r h 's,  is not derivable, i.e., there is always a truth assignment to the s k 's
that makes : true. This means that  cannot be expanded by assumptions from
together with :Lv, if under the truth assignment to the p i 's corresponding
to the assumptions in , for all truth assignments to the q j 's, there is
always an truth assignment to the r h 's that makes  true. In other words, if there
exists a preferred assumption set that does not render V
Conversely, let us assume that is true. Let  be an assumption set containing
assumptions from f:L:p corresponding to a truth assignment to the p i 's
that makes 8q This assumption set cannot be
expanded to  0 by assumptions from f:L:q together with :Lv, because
for any such expansion there exists a value assignment to the r h 's which makes
true, corresponding to a set of choices from f:L:r h ; :Lr h g which together
with  0 is an assumptions set that leads together with T to the derivation of
and v, hence attacking  0 . For this reason, there exists a preferred extension not
containing both :Lv and choices from f:L:q j ; :Lq j g, and hence this preferred
extension does not contain V
Therefore, all reasoning problems are harder in AEL under the admissibility
and preferability semantics than under the stability semantics (see Table 2). In-
deed, credulous reasoning under admissibility and preferability semantics is one
level higher than under the stability semantics (Theorem 19); sceptical reasoning
under the admissibility semantics is one level higher than under the stability
semantics (Theorem 20); sceptical reasoning under the preferability semantics is
two levels higher than under the stability semantics (Theorem 21).
Moreover, whereas reasoning under the stability semantics has the same complexity
in AEL as in DL, reasoning under the admissibility and preferability semantics
is harder in AEL than in DL. Indeed, sceptical reasoning under the preferability
semantics and credulous reasoning under the admissibility and preferability
semantics are one level harder for AEL than for DL, and sceptical reasoning under
the admissibility semantics is two levels harder.
We note that various complexity results for the parsimonious and moderately
grounded semantics for AEL are presented in [9]. It would be interesting to see
how the semantics for AEL provided by preferred/admissible arguments (for the
instance of the abstract framework for AEL) relate to the semantics of [9]. This is
however outside the scope of the present paper.
8 Conclusion and Discussion
We have studied the computational complexity of the credulous and sceptical reasoning
problems under the new admissibility and preferability semantics for the
abstract framework for default reasoning proposed in [1], for a number of concrete
instances of the abstract framework, namely theorist, circumscription, logic
programming (LP), default logic (DL) and autoepistemic logic (AEL). These new
semantics are presented in [1] as "simpler" alternatives to the conventional stability
semantics for all instances of the framework (see Section 1 for a discussion of
this issue).

Table

2 summarises the results we have proven (for the admissibility and
preferability semantics) as well as existing results in the literature (for the stability
semantics). In the table, "X -c." stands for "X -complete." We have proven
the results by appealing to properties of the frameworks, whenever possible. In
particular, we have used the properties (proven in [1]) that default logic and logic
programming are flat frameworks and that theorist and circumscription are normal
frameworks. In addition, we have introduced the new property that frameworks
are simple, and proven that theorist and circumscription satisfy such property.
Autoepistemic logic is a general framework in that it does not satisfy any special
property amongst the ones considered.
Framework Property Admissibility Preferability Stability
cred. scept. cred. scept. cred. scept.
AEL general  p-c.  p-c.  p-c.  p-c.  p-c.  p-c.
3 -c.  p
flat NP-c. P-c. NP-c.  p
-c. NP-c. co-NP-c.
Theorist simple &  p
Circumscription normal  p-c. co-NP-c.  p-c.  p-c.  p-c.  p-c.

Table

2: Overview of complexity results
The table shows that reasoning under the new semantics can be much harder
than reasoning under the conventional stability semantics. In particular, for AEL,
sceptical reasoning under the admissibility and preferability semantics is one and
two level harder, respectively, than under the stability semantics, whereas credulous
reasoning under both new semantics is one level harder than under the stability
semantics. Also, for DL and LP, sceptical reasoning under the preferability
semantics is one level harder than under the stability semantics, whereas sceptical
reasoning under the admissibility semantics is one level simpler than under the
stability semantics, but it reduces to monotonic reasoning in the logic underlying
the framework, thus becoming a trivial form of non-monotonic reasoning.
There appears to be a clash between these results and the intuition spelled out
in Section 1, that admissibility and preferability arguments are seemingly easier to
compute than stable extensions. However, our results are not as surprising as they
might at first appear. Since the admissibility and preferability semantics do not
restrict the number of extensions, one would expect that default reasoning under
these semantics is as hard as under the stability semantics. The higher complexity
of the sceptical reasoning problem under the preferability 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 expectation that in practice constructing
admissible arguments is often easier than constructing stable extensions.
For example, given the propositional logic program P [ fpg, with P any set of
clauses not defining the atom p, the empty set for the query p that can be constructed
"locally", without accessing P . Moreover, if P [ fpg is locally stratified
or order-consistent [1], p is guaranteed to be a credulous consequence of
the program under the stability semantics. Indeed, in all cases where the stability
semantics 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 semantics renders it a feasible alternative
to the stability semantics in the first-order case, when the propositional version
of the given abstract framework is infinite. For example, given the (negation-
logic program: fq(f(X)); p(0)g, the empty set of assumptions is an admissible
argument for the query p(0) that can be constructed "locally", even though
the propositional version of the corresponding abstract framework is infinite.
The complexity results in this paper show that sceptical reasoning under admissibility
and preferability semantics is trivial and highly complex, respectively.
However, this does not seem to matter for the envisioned applications of this se-
mantics, because credulous reasoning only is required for these applications [18].
For example, in argumentation in practical reasoning in general and legal reasoning
in particular, unilateral arguments are put forwards and defended against all
counterarguments, in a credulous manner. Indeed, these domains appear to be particularly
well suited for credulous reasoning under the admissibility semantics. In
general, the results presented in this paper indicate that reasoning under the new
semantics is harder. On the positive side, they indicate that the new semantics
allows us to encode more complex reasoning patterns than when reasoning with
the stability semantics.

Acknowledgments

The first author has been partially supported by the DFG as part of the graduate
school on Human and Machine Intelligence at the University of Freiburg and the
second author has been partially supported by the University of Cyprus.



--R

An abstract
The Complexity of Propositional Closed World Reasoning and Circumscription.
A survey of complexity results for non-monotonic logics
Preferred Arguments are Harder to Compute than Stable Extensions
Finding Admissible and Preferred Arguments Can Be Very Hard
Synthesis of Proof Procedures for Default Reasoning

Negation as hypothesis: an abductive foundation for logic programming.
Reasoning with parsimonious and moderately grounded expansions.
Propositional Circumscription and Extended Closed-World Reasoning are  p 2 -Complete
Expressive power and complexity of partial models for disjunctive deductive databases.
Abduction compared with negation as failure.
Computers and Intractability-A Guide to the Theory of NP-Completeness
The stable model semantics for logic programming.
Complexity results for nonmonotonic logics.
The complexity of default reasoning under the stationary fixed point semantics.
The role of abduction in logic programming.
Abstract argumentation.
Nonmonotonic logic: context-dependent reasoning

Nonmonotonic logic II: Nonmonotonic modal theories.
Semantical considerations on nonmonotonic logic.
Towards automatic autoepistemic reasoning.
Computational Complexity.
A logical framework for default reasoning.
A logic for default reasoning.
--TR
Semantical considerations on nonmonotonic logic
A logical framework for default reasoning
Towards automatic autoepistemic reasoning
Propositional circumscription and extended closed-world reasoning are MYAMPERSANDPgr;<supscrpt>p</supscrpt><subscrpt>2</subscrpt>-complete
Reasoning with parsimonious and moderately grounded expansions
The complexity of propositional closed world reasoning and circumscription
The complexity of default reasoning under the stationary fixed point semantics
An abstract, argumentation-theoretic approach to default reasoning
The expressive powers of stable models for bound and unbound DATALOG queries
Expressive power and complexity of partial models for disjunctive deductive databases
Stable models and non-determinism in logic programs with negation
Computers and Intractability
Preferred Arguments are Harder to Compute than Stable Extension
Synthesis of Proof Procedures for Default Reasoning
Word problems requiring exponential time(Preliminary Report)

--CTR
P. M. Dung , R. A. Kowalski , F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence, v.170 n.2, p.114-159, February 2006
Paul E. Dunne , T. J. M. Bench-Capon, Two party immediate response disputes: properties and efficiency, Artificial Intelligence, v.149 n.2, p.221-250, October
default reasoning;non-monotonic reasoning;abduction;argumentation;assumption-based reasoning;computational complexity