Parametric Properties of Ideal Semantics

1 Introduction

Argumentation has evolved as an important field in AI with abstract argumentation frameworks (AFs, for short) as introduced by Dung [1995] being its most studied formalism. Meanwhile, a wide range of semantics for AFs has been proposed; for an overview see [Baroni and Giacomin, 2009]. One of the most interesting recent approaches is the ideal semantics which have been introduced as an alternative basis for skeptical argumentation by Dung, Mancarella and Toni [2007]. These define the concept of ideal sets as admissible sets, S, with the property that S is contained in all preferred extensions (i.e. subset-maximal admissible sets) of an AF 〈X,A〉, with the (unique) ideal extension of 〈X,A〉 being its maximal (again, wrt ⊆) ideal set.

Although Dung et al. [2007] present ideal semantics using preferred extensions as the basis, we argue that the approach is appropriately handled as a parametric model of acceptance, applicable to multiple status semantics in general,

∗This work was supported by the Vienna Science and Technology Fund (WWTF) under grant ICT08-028 and by the Austrian Science Fund (FWF) under grant P20704-N18.

Stefan Woltran

Institute of Information Systems Vienna Univ. of Tech., Austria woltran@dbai.tuwien.ac.at

with the specific example of preferred semantics being one instance. In fact, another instance of this schema has been proposed by Caminada [2007], who used semi-stable [Caminada, 2006] instead of preferred extension for the base semantics, and called this approach eager semantics.

A natural question of interest thus concerns to what extent general properties of ideal semantics can be established, particularly in the light of known results for the preferred and eager case. Our aim in this paper is to focus on complexity theoretic properties. In particular, we are interested in the question whether the complexity of ideal reasoning can be derived from known complexity results for the respective base semantics in terms of credulous or skeptical acceptance. As a basis we shall use the characterisations proven by Dunne [2009], who showed that the main reasoning problems here are located between NP resp. coNP and ΘP2 . 1 As we will see these results are due to the fact that the problems of credulous and skeptical acceptance for the base semantics are located on different levels of the polynomial hierarchy. For many other base semantics the complexity of ideal and skeptical reasoning is the same, as we show in this paper.

What we call ideal semantics, is also known as prudent reasoning in the world of non-monotonic reasoning (this should not to be confused with prudent semantics for AFs as proposed in [Coste-Marquis et al., 2005]). Typically, prudent reasoning is considered as an additional reasoning mode besides credulous and skeptical reasoning, and in case of default logic can be defined as follows, see e.g. [Besnard and Schaub, 1998]: a formula ϕ follows from a default theory (W,D) by prudent reasoning if ϕ follows from W plus those defaults from D which are generating defaults for all extensions of (W,D). Another similar concept is the one of free consequences [Benferhat et al., 1993] which are defined as formulas being entailed by the intersection of all maximal consistent subsets of a (possibly inconsistent) knowledge base.

This motivates our view of understanding ideal acceptance as a third reasoning mode for abstract argumentation, different from credulous and skeptical acceptance and, in principle, applicable to any semantics. We recall that here the difference to skeptical acceptance is due to the fact that the intersection of the extensions given by the chosen base semantics is not necessarily an admissible set. A well-known example is the AF ({a, b, c, d}, {(a, b), (b, a), (a, c), (b, c), (c, d)}) where the preferred extensions are {a, d} and {b, d}, thus d is skeptically accepted, but the only ideal set is ∅ (since {d} is not admissible). For prudent reasoning in default logic, the difference to skeptical reasoning is a bit more subtle. As an example, consider, Δ = ({α ∨ β → γ}, { :¬α β , :¬β α }). Here, we also have two extensions, one containing α the other containing β. Hence, γ follows skeptically from Δ but not via prudent reasoning, since none of the defaults is generating in all extensions. Let us finally mention that such a situation is also possible in the argumentation setting as soon as arguments are not fully abstract anymore. As an example, consider the AF from above with additional attack (d, c). Then {d} is the ideal extension coinciding with the intersection of skeptically accepted arguments. If one considers now that, for instance, a's claim is α∧¬β, b's claim is β ∧¬α, and d's claim is α ∨ β → γ, then γ follows skeptically from the AF, but γ is not derivable from the ideal extension.

1 Exact bounds seem to be very hard to establish; Dunne [2009] gives ΘP2 -hardness proofs with respect to randomised reductions.

Our main contributions can be summarised as follows:

• We show general results about properties ideal semantics for abstract argumentation satisfy. Most notably, we show that whenever the base semantics is based on conflict-free sets (which is true for any reasonable semantics) there exists a unique ideal extension. Moreover, it holds that for each base semantics satisfying the reinstatement property [Baroni and Giacomin, 2007], the ideal extension is also complete.
• We provide two alternative algorithms how to compute an ideal extension. One is a generalisation of concepts introduced in [Dunne, 2009] and relies on credulous acceptance for the base semantics. A novel characterisation uses the skeptically accepted arguments instead.
• We provide a thorough complexity analysis. We are able to provide general results for ideal reasoning which can be derived from complexity results for the base semantics. Moreover, we give novel exact bounds for the following realisations of ideal semantics: semi-stable (we note that complexity has not been analysed in [Caminada, 2007]), resolutionbased grounded [Baroni et al., 2011a], stage [Verheij, 1996], and naive semantics. For naive semantics, reasoning in the ideal extension remains tractable.

2 Preliminaries

Throughout 〈X,A〉 is a (finite) AF with argument set X = {x1, . . . , xn} and attack relation A ⊆ X × X. For S ⊆ X, let S- be {x | ∃y ∈ S s.t. 〈x, y〉 ∈ A} and, similarly, S+ be {x | ∃y ∈ S s.t. 〈y, x〉 ∈ A}.

A semantics for AFs is any predicate σ : 2X → 〈⊤,⊥〉 prescribing criteria under which a set of arguments is considered collectively "justified". A semantics is extension-based if it satisfies for all S ⊆ X: if σ(S) then ¬σ(T) for all T ⊃ S. We denote by Eσ(〈X,A〉) the set of subsets within the AF 〈X,A〉, i.e. Eσ(〈X,A〉) = {S ⊆ X : σ(S)}. An (extension-based) semantics, σ, is said to be unique status if for every AF 〈X,A〉, |Eσ(〈X,A〉)| = 1 holds; otherwise the semantics is multiple status. For σ a unique status semantics, Eσ(〈X,A〉) denotes the unique set comprising Eσ(〈X,A〉).

An argument, x ∈ X is acceptable wrt S ⊆ X if for any y ∈ X for which 〈y, x〉 ∈ A there is some z ∈ S such that 〈z, y〉 ∈ A. The characteristic function, F : 2X → 2X , reports the set of arguments that are acceptable to a given set. It is shown by Dung [1995] that the function F has a least fixed point which is called the grounded extension.

We require the following concepts for an AF F = 〈X , A〉:

Ecf(F) are called the conflict-free sets of F, Eadm(F) and Ecomp(F) are the admissible, and respectively, complete sets. The remaining cases define extension-based semantics, and with the exception of the grounded semantics gr, these are all multiple status. In fact, we have defined here naive extensions (Enaive(F)), preferred extensions (Epr(F)), semi-stable extensions (Esst(F)), and stage extensions (Estage(F)).

Definition 1 Let σ and θ be semantics. If for all AFs F, Eσ(F) ⊆ Eθ(F), we call σ a θ-preserving semantics.

All of the above semantics are cf-preserving, but naive and stage semantics are, for instance, not adm-preserving. Moreover, sst is pr-preserving, and stage is naive-preserving.

The resolution-based semantics [Baroni et al., 2011a] are a parametric approach defined in the following way: given an AF F = 〈X,A〉, let μ(F) be the set of (unordered) pairs {{x, y} | {〈x, y〉, 〈y, x〉} ⊆ A}. A (full) resolution, β, of F contains exactly one of each of the attacks 〈x, y〉, 〈y, x〉 for each {x, y} ∈ μ(F). We denote the set of all full resolutions as γ(F). If σ is an extension-based semantics the resolution based σ semantics, σ∗, is given through Eσ∗(〈X,A〉) = min ⋃β∈γ(〈X,A〉) {Eσ(〈X,A \ β〉)} where min is with respect to ⊆. We note that gr∗ - the resolution-based grounded semantics - is multiple status. As is known, gr∗ satisfies many desirable properties, thus we will focus on this instantiation here. In fact, the semantics for which we will consider ideal extensions in this paper, are pr, sst, stage, gr∗, and naive.

We assume the reader has knowledge about standard complexity concepts, as P, NP, ΣP2 , ΠP2 , LOGSPACE (L), and oracles. Beyond these we need the following complexity classes: ΘP2 = PNP ‖ , where PC‖ is the class of decision problems that can be solved by a deterministic polynomial time algorithm which is allowed to make O(n) non-adaptive calls to the Coracle; FPC‖ which is the corresponding class of function problems; DP , the class of decision problems L that can be characterised as L1 ∩ L2 for decision problems L1 ∈ NP and L2 ∈ coNP; DP2 , the class of decision problems L that can be characterised as L1 ∩ L2 for L1 ∈ ΣP2 and L2 ∈ ΠP2 .

Typical computational problems of interest are:

1. Credulous acceptance - CAσ(〈X,A〉, x) (x ∈ X). Is there any S ∈ Eσ(〈X , A〉) for which x ∈ S?

1. Skeptical acceptance - SAσ(〈X,A〉, x) (x ∈ X). Is x ∈ S for every S ∈ Eσ(〈X , A〉)?
2. Verification - VERσ(〈X,A〉, S) (S ⊆ X). Is it the case that S ∈ Eσ(〈X , A〉)?
3. Non-emptiness - NEσ(〈X,A〉). Is there any S ∈ Eσ(〈X , A〉) for which S ̸= ∅?

The complexity of these problems is well explored [Baroni et al., 2011a; Dimopoulos and Torres, 1996; Dunne and BenchCapon, 2002; Dvoˇr´ak and Woltran, 2010] (see Table 1).

3 Parameterised Ideal Semantics

We give a general definition of ideal semantics, abstracting from the approaches in [Caminada, 2007; Dung et al., 2007].

Definition 2 Let 〈X,A〉 be an AF and σ a semantics that promises at least one extension 2 . The ideal sets wrt base semantics σ of 〈X,A〉 are those that satisfy the constraints: (I1) S ∈ Eadm(〈X,A〉) and (I2) S ⊆ ⋂T ∈ Eσ(〈X,A〉) T. We say that S is an ideal extension of 〈X,A〉 wrt σ, if S is a ⊆-maximal ideal set (of 〈X,A〉) wrt σ. E IDL σ denotes the collection of ideal sets wrt σ and E IE σ denotes the set of ideal extensions wrt σ. σ IE denotes the corresponding semantics.

Proposition 1 If a semantics σ is cf-preserving, then σ IE is a unique status semantics.

Proof: It suffices to show that if S ∈ E IDL σ (〈X,A〉) and T ∈ E IDL σ (〈X,A〉) then S ∪ T ∈ E IDL σ (〈X,A〉). First note that S ∪ T ∈ Ecf(〈X,A〉) since, by the definition of E IDL σ , S ⊆ ⋂V∈Eσ(〈X,A〉) V and T ⊆ ⋂V∈Eσ(〈X,A〉) V ; hence S ∪ T ⊆ V for every V ∈ Eσ(〈X,A〉). As by assumption σ promises at least one extension V ∈ Eσ(〈X,A〉) we then have that S ∪ T is a subset of a conflict-free set and thus is itself conflict-free. It must, however, further hold that S∪T ∈ Eadm(〈X , A〉): both S and T are in Eadm(〈X , A〉) (since they are ideal sets wrt σ), hence any y ∈ (S ∪ T)- either belongs to S- (and so is counterattacked by some z ∈ S) or is in T - (and, in the same way, counterattacked by some argument in T). It follows that S ∪ T ∈ Eadm(〈X,A〉) forming a subset of every set in Eσ(〈X,A〉), i.e. S ∪ T ∈ E IDL σ (〈X,A〉). □

Let us now discuss a few further aspects of Definition 2. Indeed, one might ask why the notion of base semantics is parameterised, but the required properties of ideal sets and ideal extensions are to some extent fixed in the following sense: (a) each ideal set is admissible; (b) the ideal extensions are defined wrt subset maximality.

2 Hence we exclude stable semantics as a base semantics here.

Proposition 1 gives an answer to the second issue already. In fact, using this result one can observe that considering admissible sets S ⊆ ⋂T ∈ Eσ(〈X,A〉) T which are maximal with respect to the cardinality |S|, the range S ∪ S+ or the cardinality of the range |S∪S+| would always yield the ideal extension (defined via ⊆-maximality), as well.

Let us thus turn to issue (a). Two directions are possible: (1) weakening the restriction for being an ideal set; (2) strengthening the properties ideal sets have to satisfy. For (1), the only natural such relaxation would be to consider conflictfree (instead of admissible) sets as ideal ones. However, as long as we assume that any reasonable base semantics is cfpreserving, we get that the set of skeptical accepted arguments is already conflict-free. Hence we would end up with the problem of skeptical acceptance. Against (2), one can argue that a restriction to complete sets is the closest reasonable such sharpening. We can give the following result.

Proposition 2 If σ satisfies the reinstatement property 3 then σ IE is comp-preserving.

Proof: Let E ∈ E IE σ (〈X,A〉). By definition E is admissible and it remains to show that every a ∈ X defended by E belongs to E. Thus consider such an a. As E is part of every σ-extension, each σ-extension S defends a and therefore (as σ satisfies the reinstatement property) a ∈ S. Hence a is skeptically accepted and defended by E; thus E ∪ {a} is an ideal set. But as E is already a maximal ideal set, a ∈ E. □

Thus, if the base-semantics satisfies the reinstatement property then the ideal extension is already a complete set and thus considering complete sets (instead of admissible sets in Condition I1 of Definition 2) would not change anything. On the other hand, if the base-semantics σ does not satisfy the reinstatement property, the existence of a complete set S which is contained in all σ-extensions is not guaranteed. For example, consider σ = naive and AF F = ({a, b}, {(a, b)}). Then, Enaive(F) = {{a}, {b}}, but ∅ is not complete here.

4 Algorithms

We discuss two types of algorithms for computing the ideal extension wrt to a given base semantics σ. The first is a generalisation of an algorithm from [Dunne, 2009] and relies on credulous acceptance for σ. We will show that such an algorithm can be used for any base semantics σ which is pr- or naive-preserving. Thus, this algorithm applies also to σ = sst. Our second algorithm is closer to the original definition of ideal sets and thus makes use of skeptical acceptance in σ. It is applicable to any cf-preserving base semantics σ. Having these two algorithms at hand clearly is also of practical value. In fact, whenever both algorithms are applicable, then one can now select in view of the computational complexity of credulous acceptance and skeptical acceptance for the base semantics. We first need a few technical results.

Proposition 3 If σ is pr-preserving, then for each AF F = 〈X,A〉 the following relations hold:

3 The concept of reinstatement [Baroni and Giacomin, 2007] separates complete from admissible sets. A semantics σ satisfies reinstatement iff for every AF 〈X , A〉 and E ∈ Eσ(X , A), we have ∀x ∈ X : (∀y ∈ X((y, x) ∈ A → ∃z ∈ E : (z, y) ∈ A)) → x ∈ E.

In the case of ideal sets wrt preferred extensions the characterisation of Proposition 3 has previously been shown in [Dung et al., 2007; Dunne, 2009]. In addition, we now see that it holds also for the case when semi-stable semantics are employed as base semantics for ideal reasoning.

However, the above characterisation does not apply to semantics which are not based on admissibility, e.g. stage semantics. Thus our next step is to give a similar characterisation for naive-preserving semantics. The only subtle difference is due to the fact that naive semantics do not take the orientation of attacks into account. Thus, we have to add S+ (resp. {x}+) to the conditions from Proposition 3.

Proposition 4 If σ is naive-preserving, then for each AF F = 〈X,A〉 the following relations hold:

The characterisations (C2) and (C2') from above results suggest how to compute the ideal extension w.r.t. a semantics σ, in case we have given a function that decides credulous acceptance for σ. Algorithm 1 describes this idea.

Algorithm 1 Input: AF 〈X,A〉, function CAσ deciding credulous acceptance.

1. Determine the sets XOUT = {x | ¬CAσ(〈X,A〉, x)} and XPSA = {x ∈ X \ XOUT | {x}- ∪ {x}+ ⊆ XOUT}.
2. Form the AF 〈XPSA ∪XOUT , B〉 in which B contains only attacks 〈x, y〉 ∈ A with x ∈ XPSA and y ∈ XOUT or x ∈ XOUT and y ∈ XPSA, i.e. the AF is bipartite.
3. Return max{S⊆XPSA : S∈Eadm(〈XPSA,XOUT , B〉)}.

The correctness of this algorithm (for appropriate base semantics as outlined above) is an immediate consequence of Proposition 3 and Proposition 4. As well there exist simple algorithms for handling bipartite AFs [Dunne, 2007].

Theorem 1 For any semantics σ which is pr-preserving or naive-preserving, Algorithm 1 constructs E IE σ .

Although Algorithm 1 is already applicable to a wide range of base semantics, it does not work for resolution-based grounded semantics. Consider the example in Figure 1. We have Egr∗ = {{P, F}, {Q,B}}, thus E IE GR∗ = ∅. However, {B, F} is admissible and none of its attackers credulously accepted wrt gr∗. In fact, {B, F} is the standard ideal extension (wrt preferred semantics), since the preferred extensions of the framework are {B, F, P} and {B, F, Q}.

This motivates Algorithm 2 which follows the definition of ideal semantics more closely: it first computes the set of all skeptically accepted arguments and then iteratively computes the maximal admissible subset.

Algorithm 2 Input: AF 〈X,A〉, function SAσ deciding skeptical acceptance. 1. Compute XSA = {x | SAσ(〈X,A〉, x)}. 2. Return E = ˆ F |XSA | (XSA), with ˆ F(E) = F(E) ∩ E.

We next show that this algorithm is correct for every reasonable base semantics, i.e. for base semantics that are cfpreserving. The following lemma captures the correctness of the fixed-point iteration in the algorithm.

Lemma 1 Let (X,A) be an AF and S ∈ Ecf(〈X,A〉). The ⊆-maximal admissible set A ⊆ S is ˆ F |S| (S).

Theorem 2 For any semantics σ which is cf-preserving, Algorithm 2 constructs E IE σ .

Proof: Since σ is cf-preserving, the set XSA is also conflictfree. Thus by Lemma 1, E IE σ = ˆ F |XSA | (XSA). □

5 Instantiations

Next, we study ideal reasoning wrt concrete base semantics. In particular, we are interested how the ideal extension wrt to different base semantics relate to each other. In the case of complete sets as base semantics, our schema yields that the ideal extension wrt complete sets matches the grounded extension, i.e. for any AF F, E IE comp (F ) = Egr(F ).

The other base semantics, we are interested here are gr∗, pr, sst, naive, and stage. Since all these semantics σ are cfpreserving, we know that σ IE is a unique status semantics by Proposition 1. Moreover, for σ ∈ {pr, sst, gr∗}, σ has the reinstatement property, and thus by Proposition 2, E IE σ (〈X,A〉) is a complete set for any AF 〈X,A〉. In general, this does not hold for σ ∈ {naive, stage}. However, the ideal extension wrt naive semantics is easily characterised.

We investigate now how ideal extensions of different base semantics are related to each other. Caminada [2007] has already shown that E IE pr (F) ⊆ E IE sst (F) holds and that there exist AFs F, such that E IE pr (F ) ⊂ E IE sst (F). With the following results we give a full analysis of the ⊆ relations between the ideal extensions wrt the base semantics considered here.

Theorem 3 For any AF F the following ⊆-relations hold:

Furthermore, all these ⊆-relations are proper ones.

6 Computational Complexity

In this section we provide two kind of complexity results for ideal reasoning. First we present generic complexity bounds for ideal reasoning problems, i.e. complexity bounds which depend on the complexity of reasoning problems for the base semantics. Then we use these results to draw the complexity landscape for the concrete base-semantics mentioned in Section 5. The computational problems we are interested here, are the following:

1. Credulous acceptance - CA IDL σ (〈X,A〉, x) (x ∈ X). Is there any S ∈ E IDL σ (〈X,A〉) for which x ∈ S?
2. Verification for ideal sets - VER IDL σ (〈X,A〉, S) (S ⊆ X). Is it the case that S ∈ E IDL σ (〈X,A〉)?
3. Non-emptiness - NE IDL σ (〈X,A〉). Is there any S ∈ E IDL σ (〈X,A〉) for which S ̸= ∅?
4. Verification for ideal extension - VER IE σ (〈X,A〉, S) (S ⊆ X). Is it the case that S = E IE σ (〈X,A〉)?
5. Construction - CONS IE σ (〈X,A〉). Reports the ideal extension E IE σ (〈X,A〉.

We first consider the construction problem using the algorithms given in Section 4.

Theorem 4 For any cf-preserving semantics σ, E IE σ can be constructed in FPC‖ , if either SAσ ∈ C or σ is pr-preserving (resp. naive-preserving) and CAσ ∈ C.

We next give a strong connection between the problem CA IDL σ and the function problem CONS IE σ , such that we can extend a hardness result for CA IDL σ to CONS IE σ .

Theorem 5 Let σ be a semantics where unconnected (via attack paths) arguments do not affect each others acceptance status. If CA IDL σ is C-hard then CONS IE σ (〈X,A〉) is FPC‖ -hard (under metric reductions).

Note that upper bounds for the problem CONS IE σ immediately lead to upper bounds for decision problems. The following theorem may provide strictly better upper bounds.

Theorem 6 Let σ be a cf-preserving semantics and let V be the complexity of the problem VERσ. Then, (i) CA IDL σ ∈ coNPV , (ii) VER IDL σ ∈ coNPV , (iii) NE IDL σ ∈ coNPV and (iv) VER IE σ ∈ NPV ∧ coNPV .

Proof: Given an AF F = 〈X,A〉, a base semantics σ, an argument x ∈ X and a set S ⊆ X. Fact (i) follows from the following NPV algorithm for disproving x to be in E IE σ :

1. Guess extensions E1, . . . , En (for n = |X |)
2. Verify extensions using the V-oracle
3. Compute SSA := ⋂ni=1 Ei
4. Compute the ⊆-maximal admissible set A ⊆ SSA.
5. Accept iff x /∈ A

We get (ii) by a simple adaptation of the above algorithm: instead of testing x /∈ A one tests whether S ̸⊆ A. For (iii) we use another adaptation of the above algorithm, now one tests for A = ∅, which proves that E IE σ = ∅. (iv): To verify E IE σ = S, one tests whether S ∈ E IDL σ (F) using the coNPV - algorithm and disproves the ideal acceptance for all a ∈ X \S via the above NPV -algorithm. □

In the following we give generic lower bounds, i.e. generic hardness results, for the problems VER IDL σ and CA IE σ depending on the complexity of the problem CAσ.

To this end, we introduce the following property:

Definition 3 A pair (〈X,A〉, x) of an AF 〈X,A〉 and x ∈ X satisfies the mutual attack property wrt a semantics σ iff CAσ(〈X , A〉, x) ⇒ CAσ(〈X ∪ {y}, A ∪ {〈x, y〉, 〈y, x〉}〉, x) (where y ̸∈ X ). A semantics σ has the mutual attack property iff each (〈X , A〉, x) has the mutual attack property wrt σ.

Semantics adm, comp, pr, gr∗, and naive all have the mutual attack property. But one can construct AFs which do not satisfy the mutual attack property for sst and stage.

Proposition 6 If σ is pr-preserving or naive-preserving, CAσ ∈ C for some complexity class C which is closed under ∪, and there exist C-hard instances of the CAσ problem that satisfy the mutual attack property then (a) VER IDL σ is coCcomplete and (b) CA IDL σ is coC-hard.

We finally provide novel exact bounds for computational problems of ideal reasoning wrt to base semantics stage, sst, gr∗, and naive, partly exploiting the generic results.

Theorem 7 Complexity results as depicted in Table 2 hold (the first two lines contain known results).

Proof: For σ ∈ {sst, stage, gr∗}, membership for the decision problems follows by Theorem 6 and the complexity of VERσ. Membership for CONS IE σ is a consequence of Theorem 4. Hardness for the construction problems will follow by Theorem 5 after having shown hardness for CA IDL σ .

By Theorem 4, we can construct E IE naive in P; thus all the decision problems for naive semantics are in P. VER IDL naive ∈ L follows by Proposition 6. The P-hardness of CA IDL naive , NE IDL naive and VER IE naive can be shown via a reduction from the P-hard problem of deciding whether some atom follows from a propositional definite Horn theory.

The hardness results for σ ∈ {sst, stage} use the following reduction from [Dvoˇr´ak and Woltran, 2010], which maps the ΠP2 -hard problem QBF ∀ 2 to SAσ and co-CAσ: Given a QBF formula Φ = ∀Y ∃Z ∧c∈C c, construct KΦ = (X,A), where X = {Φ,Ψ, b} ∪ C ∪ Y ∪ ¯ Y ∪ Y ′ ∪ ¯ Y ′ ∪ Z ∪ ¯ Z and A = {〈c,Φ〉 | c ∈ C} ∪ {〈Φ,Ψ〉, 〈Ψ,Φ〉, 〈Φ, b〉, 〈b, b〉} ∪ {〈x, ¯x〉, 〈¯x, x〉 | x ∈ Y ∪ Z} ∪ {〈y, y′ 〉, 〈¯ y, ¯ y′ 〉, 〈y′ , y′ 〉, 〈¯ y′ , ¯ y′ 〉 | y ∈ Y } ∪ {〈l, c〉 | literal l occurs in c ∈ C}. In [Dvoˇr´ak and Woltran, 2010], it is shown that Ψ is credulously accepted iff Φ is not valid. Since the pairs (KΦ,Ψ) are ΣP2 -hard instance for CAσ satisfying the mutual attack property, we obtain by Proposition 6 that both VER IDL σ and CA IDL σ are ΠP2 -hard.

To show that NE IDL σ is ΠP2 -hard, we use a variant of this construction by adding an argument y and attacks (y,Ψ), (Ψ, y) to KΦ. Using a restricted class of ΠP2 -hard QBF s ∀Y ∃Z ∧c∈C c (in which ∧c∈C c has a model M, with M ∩ Z = ∅ and a model M ′ , with Z ⊆ M ′ ), one can show that the only argument that can be ideal accepted is y. Hence NE IDL σ is true iff y is ideal accepted iff Φ is valid. Thus NE IDL σ is ΠP2 -hard.

The results for gr∗ can be established by similar techniques (using a different reduction from UNSAT). Since gr∗ preserves neither pr nor naive, a direct use of Proposition 6, is not possible, however. □

7 Discussion

While in their original paper, Dung et al. [2007] have proposed their approach of ideal sets and extensions as a dedicated semantics for abstract AFs (being in the line with the logic programming semantics [Alferes et al., 1993] which motivated their work), we believe that the idea behind ideal semantics is more in the spirit of an alternative, third, notion of acceptance besides credulous and skeptical acceptance. A view which is backed up by the introduction of eager semantics [Caminada, 2007] which is defined as ideal semantics but replacing preferred by semi-stable extensions as a basis.

In this paper we analysed common properties for different formings of ideal semantics and we investigated the instantiation wrt semi-stable, stage, naive, and resolutionbased grounded semantics in detail. Our complexity analysis showed that ideal reasoning in these instantiations is of the same complexity as skeptical reasoning, which is in contrast to the standard ideal semantics, where reasoning is known to be in ΘP2 [Dunne, 2009] and thus easier than the ΠP2 -hard problem of skeptical reasoning (for preferred semantics); see also Table 2. We identified as a main reason for this result the fact that credulous reasoning in preferred semantics is only in NP, while for the semantics we have considered here, credulous acceptance is on the same level of complexity as skeptical reasoning. We therefore also provided two different generic algorithms for computing the ideal extension, one based on the credulous acceptance problem, the other based on the skeptical acceptance problem of the base semantics.

As a final remark, we thus note that the view promoted in our treatment of ideal reasoning is by no means limited to semantics in Dung's AFs but can also be considered, in principle, with respect to such developments as value-based frameworks [Bench-Capon, 2003], extended AFs [Modgil, 2009], or frameworks with recursive attacks [Baroni et al., 2011b].