Coherence in finite argument systems.
Argument Systems provide a rich abstraction within which divers concepts of reasoning, acceptability and defeasibility of arguments, etc., may be studied using a unified framework. Two important concepts of the acceptability of an argument p in such systems are credulous acceptance to capture the notion that p can be 'believed'; and sceptical acceptance capturing the idea that if anything is believed, then p must be. One important aspect affecting the computational complexity of these problems concerns whether the admissibility of an argument is defined with respect to 'preferred' or 'stable' semantics. One benefit of so-called 'coherent' argument systems being that the preferred extensions coincide with stable extensions. In this note we consider complexity-theoretic issues regarding deciding if finitely presented argument systems modelled as directed graphs are coherent. Our main result shows that the related decision problem is (p)2 -complete and is obtained solely via the graph-theoretic representation of an argument system, thus independent of the specific logic underpinning the reasoning theory.
Introduction
Since they were introduced by Dung [8], Argument Systems have provided a fruitful
mechanism for studying reasoning in defeasible contexts. They have proved
useful both to theorists who can use them as an abstract framework for the study
and comparison of non-monotonic logics, e.g. [2,5,6], and for those who wish to
explore more concrete contexts where defeasibility is central. In the study of reasoning
in law, for example, they have been used to examine the resolution of conflicting
norms, e.g. [12], especially where this is studied through the mechanism of
Corresponding author.
Email address: ped@csc.liv.ac.uk (Paul E. Dunne).
Preprint submitted to Elsevier Science 13 May 2002
a dispute between two parties, e.g. [11]. The basic definition below is derived from
that given in [8].
argument system is a Ai, in which X is a set of
arguments and A  X  X is the attack relationship for H. Unless otherwise
stated, X is assumed to be finite, and A comprises a set of ordered pairs of distinct
arguments. A pair hx; yi 2 A is referred to as 'x attacks (or is an attacker of y' or
'y is attacked by x'.
For R, S subsets of arguments in the system H(hX ; Ai), we say that
a) s 2 S is attacked by R if there is some r 2 R such that hr; si 2 A.
acceptable with respect to S if for every y 2 X that attacks x there is
some z 2 S that attacks y.
c) S is conflict-free if no argument in S is attacked by any other argument in S.
d) A conflict-free set S is admissible if every argument in S is acceptable with
respect to S.
e) S is a preferred extension if it is a maximal (with respect to ) admissible set.
f) S is a stable extension if S is conflict free and every argument y 62 S is attacked
by S.
g) H is coherent if every preferred extension in H is also a stable extension.
An argument x is credulously accepted if there is some preferred extension containing
it; x is sceptically accepted if it is a member of every preferred extension.
The graph-theoretic representation employed by finite argument systems, naturally
suggests a unifying formalism in which to consider various decision problems. To
place our main results in a more general context we start from the basis of the
decision problems described by Table 1 in is an argument system
as in Defn. 1; x an argument in X ; and S a subset of arguments in X .
Polynomial-time decision algorithms for problems (1) and (2) are fairly obvious.
The results regarding problems (3-7) are discussed below. In this article we are
primarily concerned with the result stated in the final line of Table 1: our proof of
this yields (8) as an easy Corollary.
Before proceeding with this, it is useful to discuss important related work of Dimopoulos
and Torres [7], in which various semantic properties of the Logic Programming
paradigm are interpreted with respect to a (directed) graph translation
of reduced negative logic programs: graph vertices are associated with rules and
the concept of 'attack' modelled by the presence of edges hr; si whenever there is
a non-empty intersection between the set of literals defining the head of r and the
negated set of literals in the body of s, i.e. if z 2 body(s) then :z is in this negated
set. Although [7] does not employ the terminology - in terms of credulous accep-
tance, admissible sets, etc - from [8] used in the present article it is clear that similar
forms are being considered: the structures referred to as 'semi-kernel', 'maximal
Problem Decision Question Complexity
3 PREF-EXT(H; S) Is S a preferred extension? CO-NP-complete.
stable extension? NP-complete.
5 CA(H; x) Is x in some preferred extension? NP-complete
6 IN-STAB(H; x) Is x in some stable extension? NP-complete
7 ALL-STAB(H; x) Is x in every stable extension? CO-NP-complete.
8 SA(H; x) Is x in every preferred extension?  (p)
9 COHERENT(H) Is H coherent?  (p)

Table
Decision Problems in Finite Argument Systems and their Complexity
semi-kernel' and `kernel' in [7] corresponding to 'admissible set', 'preferred exten-
sion' and `stable extension' respectively. The complexity results for problems (3-6)
if not immediate from [7, Thm 5.1, Lemma 5.2, Prop. 5.3] are certainly implied by
these. In this context, it is worth drawing attention to some significant points regarding
[7, Thm. 5.1] which, translated into the terminology of the present article
states:
The problem of deciding whether an argument system H(X ; A) has a non-empty
preferred extension is NP-complete.
First, this implies the complexity classification for PREF-EXT stated, even when the
subset S forming part of an instance is the empty set.
A second point, also relevant to our proof of (9) concerns the transformation used:
present a translation of propositional formulae  in 3-CNF (this easily generalises
for arbitrary CNF formulae) into a finite argument system H  . It is not
difficult, however, given to define CNF-formulae H whose satisfiability
properties are dependent on the presence of particular structures within H, e.g. stable
extensions, admissible subsets containing specific arguments, etc. We thus have
a mechanism for transforming a given H into an 'equivalent' system F the point
being that F may provide a 'better' basis for graph-theoretic analyses of structures
within H.
Our final observation, concerns problem (7): although the given complexity classification
is neither explicitly stated in nor directly implied by the results of [7], that
ALL-STAB is CO-NP-complete can be shown using some minor 're-wiring' of the
argument graph G constructed from an instance  of 3-SAT. 1
The concept of coherence was formulated by [8, Defn. 31(1), p. 332], to describe
those argument systems whose stable and preferred extensions coincide. One significant
benefit of coherence as a property has been established in recent work of
Vreeswijk and Prakken[13] with respect to proof mechanisms for establishing sceptical
acceptance: problem (8) of Table 1. In [13] a sound and complete reasoning
method for credulous acceptance - using a dialogue game approach - is presented.
This approach, as the authors observe, provides a sound and complete mechanism
for sceptical acceptance in precisely those argument systems that are coherent.
Thus a major advantage of coherent argument systems is that proofs of sceptical acceptance
are (potentially) rather more readily demonstrated in coherent systems via
devices such as those of [13]. The complexity of sceptical acceptance is considered
(in the context of membership in preferred extensions) for various non-monotonic
Logics by [5], where completeness results at the third-level of the polynomial-time
hierarchy are demonstrated. Although [5] argue that their complexity results 'dis-
credit sceptical reasoning as . "unnecessarily" complex', it might be argued that
within finite systems where coherence is 'promised' this view may be unduly pes-
simistic. Notwithstanding our main result that testing coherence is extremely hard,
there is an efficiently testable property that can be used to guarantee coherence.
Some further discussion of this is presented in Section 3.
In the next section we present the main technical contribution of this article, that
COHERENT is  (p)
2 -complete: the complexity class  (p)
comprising those problems
decidable by CO-NP computations given (unit cost) access to an NP oracle. Alterna-
tively,  (p)
2 can be viewed as the class of languages, L, membership in which is certified
by a (deterministic) polynomial-time testable ternary relation R L  WXY
such that, for some polynomial bound p(jwj) in the number of bits encoding w,
Our result in Theorem 2 provides some further indications that decision questions
concerning preferred extensions are (under the usual complexity-theoretic assump-
tions) likely to be harder than the analogous questions concerning stable exten-
sions: line (8) of Table 1 is an easy Corollary of our main theorem. Similar conclusions
had earlier been drawn in [5,6], where the complexity of reasoning problems
in a variety of non-monotonic Logics is considered under both preferred and stable
semantics. This earlier work establishes a close link between the complexity of the
reasoning problem and that of the derivability problem for the associated logic. One
feature of our proof is that the result is established purely through a graph-theoretic
interpretation of argument, similar in spirit, to the approach adopted in [7]: thus,
This involves removing all except the edge hAux; Ai for edges hA; xi or hx; Ai: then
the differing complexity levels may be interpreted in purely graph-theoretic terms,
independently of the Logic that the graph structure is defined from.
In Section 3 we discuss some consequences of our main theorem in particular with
respect to its implications for designing dialogue game style mechanisms for Sceptical
Reasoning. Conclusions are presented in Section 4.
2 Complexity of Deciding Coherence
Theorem 2 COHERENT is  (p)
In order to clarify the proof structure we establish it via a series of technical lem-
mata. The bulk of these are concerned with establishing  (p)
-hardness, i.e with
reducing a known  (p)
-complete problem to COHERENT.
We begin with the, comparatively easy, proof that COHERENT(H) is in  (p)
.
.
Proof: Given an instance, H(X ; A) of COHERENT, it suffices to observe that,
i.e. H is coherent if and only if for each subset S of X : either S is not a preferred
extension or S is a stable extension. Since, :PREF-EXT(H; S) is in NP, i.e.  (p)
1 and
STAB-EXT(H; S) in P, we have COHERENT in  (p)
2 as required. 2
The decision problem we use as the basis for our reduction is QSAT 2 . An instance of
QSAT 2 is a well-formed propositional formula, (X; Y), defined over disjoint sets
of propositional variables,
loss of generality we may assume using only the Boolean
operations ^, _, and :; and negation is only applied to variables in X [ Y . An
instance, (X; Y) of QSAT 2 is accepted if and only if 8 X 9 Y
no matter how the variables in X are instantiated ( X ) there is some instantiation
Y ) of Y such that h X ;  Y i satisfies . That QSAT 2 is  (p)
-complete was shown in
[14].
We start by presenting some technical definitions. The first of these describes a
standard presentation of propositional formulae as directed rooted trees that has
often been widely used in applications of Boolean formulae, see e.g. [9, Chapter 4]
Definition 4 Let (Z) be a well-formed propositional formula (wff) over the vari-
AND
AND
Fig. 1. T (z
ables using the operations f^; _; :g with negation applied only
to variables of . The tree representation of  (denoted T ) is a rooted directed tree
with root vertex denoted (T  ) and inductively defined by the following rules.
a) If single literal z or :z - then T  consists of a single vertex
labelled w.
is formed from the k tree
representations hT i
i by directing edges from each (T i ) into a new root
vertex labelled ^.
c) If
is formed from the k tree
representations hT i
i by directing edges from each (T i ) into a new root
vertex labelled _.
In what follows we use the term node of T to refer to an arbitrary tree vertex, i.e.
a leaf or internal vertex.
In the tree representation of , each leaf vertex is labelled with some literal w,
(several leaves may be labelled with the same literal), and each internal vertex with
an operation in f^; _g. We shall subsequently refer to the internal vertices of T  as
the gates of the tree. Without loss of generality we may assume that the successor
of any ^-gate (tree vertex labelled ^) is an _-gate (tree vertex labelled _) and vice-
versa. The size of (Z) is the number of gates in its tree representation T  . For
formulae of size m we denote by hg the gates in T with g m always
taken as the root (T  ) of the tree. Finally for any edge hh; gi in T we refer to the
node h as an input of the gate g. 2
Definition 5 For a formula, (Z), an instantiation of its variables is a mapping,  :
associating a truth value or unassigned status () with each
variable z i . We use  i to denote (z i ). An instantiation is total if every variable is
assigned a value in ftrue; falseg and partial otherwise. We define a partial ordering
We note that since any gate may be assumed to have at most n distinct literals among its
inputs, our measure of formula size as 'number of gates' is polynomially equivalent to the
more usual measure of size as 'number of literal occurrences', i.e. leaf nodes.
over instantiations
and - to Z by writing
< - if: for each i with
and there is at least one i, for which
Given (Z) any instantiation  induces a mapping from the
nodes defining T onto values in ftrue; false; g. Assuming the natural generalisations
of ^ and _ to the domain htrue; false; i, 3 we define for h a node in T , its
value (h; ) under the instantiation  of Z as
if h is a leaf node labelled z i or :z i and
is a leaf node labelled z i and  i 6=
is a leaf node labelled :z i and  i 6=
is an _-gate with inputs hh
is an ^-gate with inputs hh
where  is clear from the context, we write (h) for (h; ).
With this concept of the value induced at a node of T via an instantiation , we
can define a partition of the literals and gates in T  that is used extensively in our
later analysis.
The value partition Val() of T comprises 3 sets hTrue(); False(); Open()i.
T1) The subset True() consists of literals and gates, h, for which
T2) The subset False() consists of literals and gates, h, for which
T3) The subset Open() consists of literals and gates, h, for which
The following properties of this partition can be easily proved:
Fact 6
a)
b) If
< -, then True(
For example in Fig. 1 under the partial instantiation
with all other variables unassigned, we have:
g.
At the heart of our proof that QSAT 2 is polynomially reducible to COHERENT is
a translation from the tree representation T of a formula (X; Y) to an argument
system H (X ; A ). It will be useful to proceed by presenting a preliminary trans-
are true or at least one x j is false; _ k
are
false or at least one is true.
z1 z2 z3 -z4
z4
Fig. 2. The Argument System R from the formula of Fig. 1
lation that, although not in the final form that will be used in the reduction, will
have a number of properties that will be important in deriving our result.
Definition 7 Let (Z) be a propositional formula with tree representation T  having
size m. The Argument Representation of , is the argument system R
defined as follows. R contains the following arguments
literal arguments fz ng.
X2 For each gate g k of T , an argument :g k (if g k is an _-gate) or an argument
k is an ^-gate). If g m , i.e the root of T , happens to be an _-gate,
then an additional argument g m is included. We subsequently denote this set
of arguments by G .
The attack relationship - A - over X contains:
ng
m is an _-gate in T ,
A3 If g k is an ^-gate with inputs fh rg.
k is an _-gate with inputs fh rg.
Fig. 2 shows the result of this translation when it is applied to the tree representation
of the formula in Fig. 1.
The arguments defining R fall into one of two sets: 2n arguments corresponding
to the 2n distinct literals over Z; and m (or m+ 1) 'gate' arguments. The key idea is
the following: any instantiation  of the propositional variables Z of , induces the
partition Val() of literals and gates in T  . In the argument system R the attack
relationship for gate arguments, reflects the conditions under which the corresponding
argument is admissible (with respect to the subset of literal arguments marked
out by ). For example, suppose g 1 is an _-gate with literals z 1 , :z 2 , z 3 as its in-
puts. In the simulating argument system, g 1 is represented by an argument labelled
:g 1 which is attacked by the (arguments labelled with) literals z 1 , :z 2 , and z 3 : the
interpretation being that "the assertion 'g 1 is false' is attacked by instantiations in
which z 1 or :z 2 or z 3 are true". Similarly were g 1 an ^-gate it would appear in
R as an argument labelled g 1 which was attacked by literals :z 1 , z 2 , and :z 3 : the
interpretation now being that "the assertion 'g 1 is true' is attacked by instantiations
in which z 1 or :z 2 or z 3 are false". With this viewpoint, any instantiation  will
induce a selection of the literal arguments and a selection of the gate arguments
(i.e. those for which no attacking argument has been included).
Suppose  is an instantiation of Z. The key idea is to map the partition of the
tree representation T as Val() onto an analogous partition of the literal and gate
arguments in R . Given  this partition comprises 3 sets, hIn(); Out(); Poss()i
defined by:
An argument p is in the subset In() of X if:
(p is the argument z i ,  or (p is the argument :z i ,
or  is in False())
or  is in True())
An argument p is in the subset Out() of X  if:
(p is the argument z i ,  or (p is the argument :z i ,
or  is in True())
or  is in False())
An argument p is in the subset Poss() of X  if:
With the formulation of the argument system R  (X ; A ) from the formula (Z)
and the definition of the partition hIn(); Out(); Poss()i via the value partition
of T we are now ready to embark on the sequence of technical lemmata
which will culminate in the proof of Theorem 2.
Our proof strategy is as follows. We proceed by characterising the set of preferred
extensions of R showing - in Lemma 8 through Lemma 11 - that these consist
of exactly the subsets defined by In(
Z is a total instantiation of Z. In
Lemma 12 we deduce that these are all stable extensions and thus that R  is itself
coherent. In the remaining lemmata, we consider the argument systems arising by
transforming instances (X; Y) of QSAT 2 . In these, however, we add to the basic
system defined by R (which will have 4n literal arguments and m (or
gate arguments) an additional set of 3 control arguments one of which attacks all
of the Y-literal arguments: we denote this augmented system by H  As
will be seen in Lemma 15, it follows easily from Lemma 10 that for any h X ;  Y i
satisfying (X; Y) the subset In( X ;  Y ) is a stable extension of both R and H .
The crucial property provided by the additional control arguments in H  is proved
in Lemma 16: if for  X there is no  Y for which h X ;  Y i satisfies (X; Y) then
the subset In( X ) (defined from R ) is a preferred but not stable extension of H ,
denotes the set In( which every y i is unassigned.
The reason for introducing the control arguments in moving from R  to H is that
not a preferred extension of R : although it is admissible, it could be
extended by adding, for example, Y-literal arguments. The design of H  will be
such that unless the gate argument g m can be used in an admissible extension of
already maximal in H and not a stable extension since the
control arguments are not attacked. Finally, in Lemma 17, it is demonstrated that
the only preferred extensions of H are those arising as a result of Lemma 15 and
Lemma 16. Theorem 2 will follow easily from Lemma 17, since the argument g m
- corresponding to the root node (T  ) of the instance (X; Y) - must necessarily
belong to any stable extension in H  : hence H is coherent if and only if for each
instantiation  X there is an instantiation  Y such that h X ;  Y i satisfies (X; Y), i.e.
for which in the system R and thence in the corresponding stable
extension of H .
We employ the following notational conventions:  X ,  Y , (and
instantiations of X, Y , (and Z); for an argument p in X  , g p (resp. h p ) denotes
the corresponding gate (resp. node) in T , hence if g p is an _-gate, then p is the
argument labelled :g denotes the set of all preferred (resp.
stable) extensions in the argument system M  , where M is one of R or H .
Z In(
Z ) is conflict-free.
Proof: Let
Z be an instantiation of Z and consider the subset In(
Z ) of X in R .
Suppose that there are arguments p and q in In(
Z ) for which hp; qi 2 A . It cannot
be the case that h literal over z i , since exactly one
of fz is in True(
exactly one of the corresponding literal arguments
is in In(
Z ). Thus q must be a gate argument. Suppose g q is an _-gate: q 2 In(
only if g q 2 False(
Z ) and therefore h p , which (since hp; qi 2 A ) must be an input
of g q is also in False(
Z ). This leads to a contradiction: if h p is a gate then it is an
^-gate, so
is a literal u i , then h p 2 False(
would mean that :u i 2 True(
Z ) and hence u i 62 In(
Z ). The remaining possibility
is that g q is an ^-gate: q 2 In(
If h p is a gate it must be an input of g q and an _-gate: h p 2 True(
Finally if the input h p is a literal u i in T then in R the literal :u i
attacks q: u
Z ). We deduce that In(
must be
conflict-free. 2
Lemma 9 8
Z In(
Z ) is admissible.
Proof: From Lemma 8, In(
Z ) is conflict-free, so it suffices to show for all arguments
Z ) that attack some q 2 In(
Z ) there is an argument r 2 In(
that attacks p. Let p, q be such that p 62 In(
Z ) and hp; qi 2 A . If
q is a literal argument, u i say, then p must be the literal argument :u i and choosing
provides a counter-attacker to p. Suppose q is a gate argument. One of
the inputs to g q must be the node h p . If g q is an _-gate then g q 2 False(
Z ) and
Z ). If h p is a literal u i then the literal argument
attacks is an ^-gate then h p 2 False(
Z ) implies there is some input h r
to h p with h r 2 False(
Z ), so that r = :h r is in In(
r is an _-gate
or literal) and r attacks p. Similarly, if g q is an ^-gate then g q 2 True(
Z ) and
Z ). If h p is a literal u i then the attacking argument (on q in R  ) is the
literal
Z ) provides a counter-attack on p. If h p
is an _-gate then h p 2 True(
Z ) indicates that some input h r of h p is in True(
so that r = h r is in In(
Z ) and r attacks p. No more cases remain thus In(
Z ) is
admissible. 2
Z In(
Proof: From Lemma 8, 9 and the fact that every argument in X is allocated
to either In(
Z ) or Out(
Z ) by
Z , cf. Fact 6(a), it suffices to show that for any
argument
Z ) there is some q 2 In(
Z ) such that p and q conflict. Certainly
this is the case for literal arguments, u 2 Out(
Z ) since the complementary literal
:u is in In(
Z ) is a gate argument. If g p is an _-gate then
Z ) and hence some input h q of g p must be in
Z ). The argument q corresponding to this input node will therefore be in
In(
Z ). If g p is an ^-gate then p 2 Out(
Z ) and some input
h q of g p must be in False(
Z ). The argument :h q will be in In(
Z ) and conflicts
with p. 2
Lemma
Proof: First observe that all S 2 PE R must contain exactly n literal arguments:
exactly one representative from fz for each i. Let us call such a subset of the
literal arguments a representative set and suppose that U is any representative set
with S U any preferred extension containing U. We will show that there is exactly
one possible choice for S U and that this is S
(U) is the instantiation
of Z by: z Consider the following
procedure that takes as input a representative set U and returns a subset S U 2 PE R
with U  S U .
g.
We can note three properties of this procedure. Firstly, it always halts: once the
literal arguments in the representative set U and their complements have been removed
from T U (in Steps 2 and 4), the directed graph-structure remaining is acyclic
and thus has at least one argument that is attacked by no others. Thus each iteration
of the main loop removes at least one argument from T U which eventually becomes
empty. Secondly, the set S U is in PE R : the initial set (U) is admissible and the
arguments removed from T U at each iteration are those that have just been added
to S U (Step 2) as well as those attacked by such arguments (Step 4); in addition
the arguments added to S U at each stage are those that have had counter-attacks
to all potential attackers already placed in S U . Finally for any given U the subset
returned by this procedure is uniquely defined. In summary, every S 2 PE R is
defined through exactly one representative set, U S , and every representative set U
develops to a unique S U 2 PE R . Each representative set, U, however, has the form
In(
hence the unique preferred extension, S U ,
consistent with U is In(
Lemma 12 The argument system R (X ; A ) is coherent.
Proof: The procedure of Lemma 11 only excludes an argument, q, from the set S U
under construction if q is attacked by some argument p 2 S U . Thus, S U is always
a stable extension, and since Lemma 11 accounts for all S 2 PE R , we deduce that
R is coherent. 2
Although our preceding three results characterise R as coherent, this, in itself,
does not allow R be used directly as the transformation for instances (X; Y) of
. The overall aim is to construct an argument system from (X; Y) which is
coherent if and only if (X; Y) is a positive instance of QSAT 2 . The problem with
R is that, even though (X; Y) may be a positive instance, there could be instan-
which fail to satisfy (X; Y) but give rise to a stable extension
In order to deal with this
difficulty, we need to augment R (giving a system H ) in such a way that the
admissible set In( X ) is a preferred (but not stable) extension (in H ) only if no
instantiation  Y allows h X ;  Y i to satisfy (X; Y). Thus, in our augmented system,
we will have exactly two mutually exclusive possibilities for each total instantiation
X of X: either there is no  Y for which true, in which event the set
produce a non-stable preferred extension of H ; or there is an appropriate
Y , in which case In( X ;  Y ) (of which In( X ) is a proper subset, cf. Fact 6(b))
Fig. 3. An Augmented Argument Representation H
will yield a stable extension in H  .
Definition 13 For (X; Y) an instance of QSAT 2 , the Augmented Argument Representation
of  - denoted H
X are the arguments arising in the Argument Representation of (X; Y) - R  -
as given in Definition 7 and C are 3 new arguments called the
control arguments. The attack relationship B  contains all of the attacks A  in the
system R together with new attacks,
ng
Using the relabelling of variables in our example formula - Figs. 1,2 - as hx 1
the Augmented Argument Representation for the system
in Fig. 2 is shown in Fig. 3
Lemma 14 If S 2 PE H then C i 62 S for any of fC g. If S 2 SE H then
Proof: Suppose S 2 PE H . If g m 2 S then each of the control arguments is attacked
by g m and so cannot be in S. If g m 62 S then C 3 62 S since the only counter-attack
to C 2 is the argument C 1 which conflicts with C 3 . By similar reasoning it follows
that C 2 62 S and C 1 62 S. For the second part of the lemma, given S 2 SE H , since
6 S, there must be some attacker of these in S. The only choice for
this attacker is g m . 2
Lemma
Proof: From Lemma 10 and 12, the subset In( X ;  Y ) is in SE R . Furthermore,
since that the gate argument g m of R is in In(
For the augmented system, H , the arguments in In(
attacks on Y-literal arguments by the control argument C 1 are attacked in turn by
the gate argument g m . In addition, using the arguments of Lemma 10 no arguments
in Out( X ;  Y ) can be added to the set In( conflict. Thus
Lemma is such that no instantiation  Y of Y , leads to h
Proof: The subset In( X ) of R can be shown to be admissible (in both R  and
H ) by an argument similar to that of Lemma 9. 4 Suppose for all  Y , we have
false, and consider any subset S of W in H for which In( X )  S.
We show that S 62 PE H . Assume the contrary holds. From Lemma 14 no control
argument is in S. If g m 2 S then S must contain a representative set, V Y say, of the Y -
literal arguments matching some instantiation  Y . From the argument used to prove
Lemma is the only preferred extension in R consistent with the
literal choices indicated by  X and  Y , and thus would be the only such possibility
for H . Now we obtain a contradiction since g m 62 In(
and so cannot be used in H to counter the attack by C 1 on the representative set V Y .
Thus we can assume that g m 62 S. From this it follows that no Y-literal argument
is in S (as g m is the only attacker of the control argument C 1 which attacks Y -
literals). Now consider the gates in T topologically sorted, i.e. assigned a number
such that all of the inputs for a gate numbered (g) are from literals
or gates h with (h) < (g). Let q be an argument such that g q is the first gate in
this topological ordering for which q 2 S=In( X ). We must have
would already be excluded from any admissible
set having In( X ) as a subset. Consider the set of arguments in W  that attack
q. At least one attacker, p, must be a node h p in T for which h p 2 Open( X ).
Now our proof is completed: S has no available counter-attack to the attack by
on q since such could only arise from a Y-literal argument (all of which have
been excluded) or from another gate argument r with g r 2 Open( X ), however,
contradicts the choice of q. Fig. 4 illustrates the
possibilities. We conclude that the subset In( X ) of W is in PE H whenever there
is no  Y with which true, and since the control arguments are not
attacked,
4 A minor addition is required in that since  X is a partial instantiation (of hX; Yi) it has
to be shown that all arguments p that attack arguments q 2 In( X ) belong to the subset
are not in Poss( X ). With the generalisation of ^ and _ to allow unassigned
values, it is not difficult to show that if p 2 Poss( X ) then any argument q attacked by p in
R cannot belong to In( X ).
AND
q= -g in Open()
q in S()
Inputs in False()
p=h in Open()
p not in S()
Inputs in True()
r in Open()
k(r)<k(g) or
Inputs in False()
Inputs in True()
AND
q=g in Open()
q in S()
p=-h in Open()
p not in S()
r in Open()
or r in Y:
r not in S()
r in Y:
r not in S()
(a) (b)
Fig. 4. Final cases in the proof of Lemma 16: q 2 Poss( X ) is not admissible
Lemma 17 If S 2 SE H then
Proof: Consider any S 2 PE H . It is certainly the case that S has as a subset
some representative set, V X from the X-literal arguments. Suppose we modify the
procedure described in the proof of Lemma 11, to one which takes as input a representative
set V of the X-literals and returns a subset S V of the arguments W of
H in the following way:
g.
The set S V is an admissible subset of W  that contains only X-literal arguments
and a (possibly empty) subset G of the gate arguments G  . Furthermore, given V ,
there is a unique S V returned by this procedure. It follows that for any S 2 PE H ,
for the representative set V associated with S. This set, V ,
matches the literal arguments selected by some instantiation (V) of X, and so as
in the proof of Lemma 11, we can deduce that S This suffices to
complete the proof: we have established that every set S in PE H contains a subset
instantiation  X : from Lemma 16, In( X ) is not maximal if and
only if
The proof of our main theorem is now easy to construct.
Proof: (of Theorem 2) It has already been shown that COHERENT 2  (p)
2 in
Lemma 3. To complete the proof we need only show that (X; Y) is a positive
instance of QSAT 2 if and only if H is coherent.
First suppose that for all instantiations  X there is some instantiation  Y for which
holds. From Lemma 15 and Lemma 17 it follows that all preferred extensions
in H are of the form In( X ;  Y ), and these are all stable extensions, hence
H is coherent. Similarly, suppose that H  is coherent. Let  X be any total instantiation
of X. Suppose, by way of contradiction, that for all  Y ,
From Lemma 16, In( X ) is a preferred extension in this case, and hence (since H
was assumed to be coherent) a stable extension. From Lemma 14 this implies that
could only happen if i.e. the value of
is determined in this case, independently of the instantiation of Y , contradicting the
assumption that ( X ;  Y ) was false for every choice of  Y . Thus we deduce that
(X; Y) is a positive instance of QSAT 2 if and only if H is coherent so completing
the proof that COHERENT is  (p)
An easy Corollary of the reduction in Theorem 2 is
Corollary
Proof: That SA 2  (p)
2 follows from the fact that x is sceptically accepted in
only if: for every subset S of X either S is not a preferred extension
or x is in S. To see that SA is  (p)
2 -hard, we need only observe that in order for H to
be coherent, the gate argument g m must occur in in every preferred extension of H
in the reduction of Theorem 2 Thus, H is coherent if and only if g m is sceptically
accepted in H . 2
3 Consequences of Theorem 2 and Open Questions
A number of authors have recently considered mechanisms for establishing credulous
acceptance of an argument p in a finitely presented system H(X ;
dialogue games. The protocol for such games assumes two players - the Defender,
(D) and Challenger, (C) - and prescribe a move (or locution) repertoire together
with the criteria governing the application of moves and concepts of 'winning' or
'losing'. The typical scenario is that following D asserting p the players take alternate
turns presenting counter-arguments (consistent with the structure of H) to
the argument asserted by their opponent in the previous move. A player loses when
no legal move (within the game protocol) is available. An important example of
such a game is the TPI-dispute formalism of [13] which provides a sound and complete
basis for credulous argumentation. An abstract framework for describing such
games was presented in [11], and is used in [3] also to define a game-theoretic approach
to Credulous Acceptance. Coherent systems are important with respect to
the game formalism of [13]: TPI-disputes define a sound and complete proof theory
for both Sceptical and Credulous games on coherent argument systems; the Sceptical
Game is not, however, complete in the case of incoherent systems. The sequence
of moves describing a completed Credulous Game (for both [3,13]) can be interpreted
as certificates of admissibility or inadmissibility for the argument disputed.
It may be noted that this view makes apparent a computational difficulty arising in
attempting to define similar 'Sceptical Games' applicable to incoherent systems:
the shortest certificate that CA(H; x) holds, is the size of the smallest admissible
set containing x - it is shown in [10] that there is always a strategy for D that can
achieve this; it is also shown in [10] that TPI-disputes won by C, i.e. certificates
that :CA(H; x), can require exponentially many (in jX moves. 5 If we consider a
sound and complete dialogue game for sceptical reasoning, then the moves of a dispute
won by D constitute a certificate of membership in a  (p)
-complete language:
we would expect such certificates 'in general' to have exponential length; similarly,
the moves in a dispute won by C constitute a certificate of membership in a  (p)
complete language and again these are 'likely' to be exponentially long. Thus a
further motivation of coherent systems is that sceptical acceptance is 'at worst' CO-
NP-complete: short certificates that an argument is not sceptically accepted always
exist.
The fact that sceptical acceptance is 'easier' to decide for coherent argument sys-
tems, raises the question of whether there are efficiently testable properties that can
be exploited in establishing coherence. The following is not difficult to prove:
Fact 19 If H(X ; A) is not coherent then it contains a (simple) directed cycle of
odd length.
Thus an absence of odd cycles (a property which can be efficiently decided) ensures
that the system is coherent. An open issue concerns coherence in random systems.
One consequence of [4] is that random argument systems of n arguments in which
each attack occurs (independently) with probability p, almost surely have a stable
extension when p is a fixed probability in the range 0  p  1. Whether a similar
result can be proven for coherence is open.
As a final point, we observe that the interaction between graph-theoretic models of
argument systems and propositional formulae may well provide a fruitful source
5 Since these are certificates of membership in a CO-NP-complete language, this is unsur-
prising: [10] relates dispute lengths for such instances to the length of validity proofs in the
CUT-free Gentzen calculus.
of further techniques. We noted earlier that [7] provides a translation from CNF-
formulae,  into an argument system H  ; our constructions above define similar
translations for arbitrary propositional formulae. We can equally, however, consider
translations in the reverse direction, e.g. given H(X ; it is not difficult to see that
the
fz:hz;xi2Ag z) is satisfiable if
and only H has a stable extension. Similar encodings can be given for many of the
decision problems of Table 1. Translating such forms back to argument systems, in
effect gives an alternative formulation of the original argument system from which
they were generated, and thus these provide mechanisms whereby any system, H
can be translated into another system H dec with properties of concern holding of
H if and only if related properties hold in H dec . Potentially this may permit both
established methodologies from classical propositional logic 6 and graph-theory to
be imported as techniques in argumentation.
In this article the complexity of deciding whether a finitely presented argument
system is coherent has been considered and shown to be  (p)
-complete, employing
techniques based entirely around the directed graph representation of an argument
system. An important property of coherent systems is that sound and complete
methods for establishing credulous acceptance adapt readily to provide similar
methods for deciding sceptical acceptance, hence sceptical acceptance in coherent
systems is CO-NP-complete. In contrast, as an easy corollary of our main result
it can be shown that sceptical acceptance is  (p)
2 -complete in general. Finally we
have outlined some directions by which the relationship between argument systems,
propositional formulae, and graph-theoretic concepts offers potential for further re-search



--R

reasoning using classical logic.
An abstract
Dialectical proof theories for the credulous preferred semantics of argumentation frameworks.

Preferred arguments are harder to compute than stable extensions.
Finding admissible and preferred arguments can be very hard.
Graph theoretical structures in logic programs and default theories.
On the acceptability of arguments and its fundamental role in nonmonotonic reasoning
The Complexity of Boolean Networks.
Two party immediate response disputes: Properties and efficiency.
Dialectic semantics for argumentation frameworks.
Logical Tools for Modelling Legal Argument.
Credulous and sceptical argument games for preferred semantics.
Complete sets and the polynomial-time hierarchy
--TR
The complexity of Boolean networks
Kernels in random graphs
On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and <italic>n</italic>-person games
reasoning using classical logic
Graph theoretical structures in logic programs and default theories
An abstract, argumentation-theoretic approach to default reasoning
Dialectic semantics for argumentation frameworks
Preferred Arguments are Harder to Compute than Stable Extension
Dialectical Proof Theories for the Credulous Preferred Semantics of Argumentation Frameworks

--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
Pietro Baroni , Massimiliano Giacomin , Giovanni Guida, Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems, Artificial Intelligence, v.165 n.2, p.187-259, July 2005
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
Trevor J. M. Bench-Capon , Sylvie Doutre , Paul E. Dunne, Audiences in argumentation frameworks, Artificial Intelligence, v.171 n.1, p.42-71, January, 2007
argument Systems;sceptical reasoning;coherence;credulous reasoning;computational complexity