(the substantial introduction of [1] provides other concrete examples of applications of in nite AFs, e.g., to multiagent negotiations).
Fortunately, recent years have seen a growing interest in in nite AFs, with special focus
on how the existence and interplay of various semantics—well-understood for nite AFs—are
a ected in the in nite realm (see, e.g., [
However, the literature still lacks a comprehensive framework for systematically exploring
all logical aspects of in nite AFs, particularly regarding their core computational issues. A
signi cant research avenue in nite AFs has been determining the algorithmic complexity of
tasks associated with nding acceptable collections of arguments (up to suitable collection of
semantics), with numerous complexity theoretic results highlighting their inherent
computational di culty (see, e.g., [
This paper addresses this gap by initiating a systematic study of the complexity of computational problems in in nite AFs. For this endeavor, we bring into the subject of argumentation theory the machinery of computability theory, which may be regarded as an in nitary companion of computational complexity theory and abounds with concepts and hierarchies for measuring the complexity of computing or de ning countably in nite objects.
The application of computability theoretic tools outside of mathematical logic is a
wellestablished idea. Over the past decades, computability theory has been applied to a wide array
of mathematical disciplines, and computability theoretic concepts have found applications in
other formal subjects, such as theoretical computer science, economics, and linguistics (see, e.g.,
[
The present paper, we argue, provides compelling evidence of the bene ts of viewing in nite AFs through a computability theoretic lens. We assess the complexity of many computational problems—both established and novel—within our framework, illustrating their undecidability while providing precise measures of their complexity.
Section 2 brie y reviews the main semantic concepts from argumentation theory that are relevant to this paper, along with the fundamental computational problems associated with them. In Section 3, we introduce the key notions of computability theory employed in the work and we de ne the concept of computable AFs and the computational issues emerging from it. Finally, in Section 4, we provide lower bounds for the complexity of our computational problems. Our results are collected in Table 2.
To keep our paper self-contained, we now brie y review some key concepts of Dung-style
argumentation theory, focusing on the semantics notions considered in this paper and the
fundamental computational problems associated with them (the surveys [
An argumentation framework (AF) F is a pair (AF , RF ) consisting of a set AF of arguments and an attack relation RF ✓ AF ⇥ AF . If some argument a attacks some argument b, we may write a ⇢ b instead of (a, b) 2RF . Collections of arguments S ✓ AF are called extensions. For an extension S, the symbols S+ and S denote, respectively, the arguments that S attacks and the arguments that attack S:
S+ = {x : (9 y 2S)(y ⇢ x)}; S
= {x : (9 y 2S)(x ⇢ y)}.
S defends an argument a, if any argument that attacks a is attacked by some argument in S (i.e., {a} ✓ S+). The characteristic function of F is the following mapping fF which sends subsets of AF to subsets of AF :
fF (S) := {x : x is defended by S}.
All AFs investigated in this paper are in nite.
A semantics assigns to every AF F a set of extensions (F ) which are deemed as acceptable. A huge number of semantics, fueled by di erent motivations, have been proposed and analyzed. Here, we focus on three prominent choices, whose computational aspects are well-understood in the nite setting: admissible, complete, and stable semantics (abbreviated by ad, co, stb, respectively).
Let F = (AF , RF ) be an AF. Denote by cf(F ) the collection of extensions of F which are con ict-free (i.e., S 2cf(F ) i a 6⇢ b, for all a, b 2S). Then, for S 2cf(F ), • S 2ad(F ) i S is self-defending (i.e., S ✓ fF (S)); • S 2co(F ) i S is a xed point of fF (i.e., S = fF (S)); • S 2stb(F ), i S attacks all arguments outside of it (i.e., S+ = AF r S).
In discussing the complete extensions, we will also brie y mention the grounded extension, which is the unique smallest xed point of fF ; in any AF, the grounded extension always exists [2, Theorem 3].
For a given semantics , the following are well-known computational problems related to : • Cred (for credulous acceptance) is the decision problem whose accepting instances are the pairs (F , a) so that a 2S for some S 2 (F ); • Skept (for skeptical acceptance) is the decision problem whose accepting instances are the pairs (F , a) so that a 2S for all S 2 (F ); • Exist is the decision problem whose accepting instances are the AFs F so that (F ) 6= ; ; • NE is the decision problem whose accepting instances are the AFs F so that (F )r{;} 6 = ; ; • Uni is the decision problem whose accepting instances are the AFs F so that | (F )| = 1.
In formal argumentation theory, evaluating the computational complexity of the
aforementioned problems for various semantics has been a noteworthy research thread for more than 20
years [
Cred NP-c NP-c NP-c
Skept trivial coNP-c P-c
Exist trivial NP-c trivial
NE Uni NP-c coNP-c NP-c DP-c NP-c coNP-c
In this section, we introduce computable AFs and we revisit the computational problems of
the last section through the lens of computability theory. We aim at conveying the main ideas
without delving into too many technical details. A more formal and comprehensive exposition of
the fundamentals of computability theory can be found, e.g., in [
As is common in computability theory, we denote the set of natural numbers by !. Since there is no risk of ambiguity, we simply refer to the elements of ! as numbers. The symbol !! denotes the set of all functions from ! to !. For our purposes, it is convenient to represent elements of !! as in nite sequences of numbers; we denote by 01 the in nite sequence consisting of only 0’s (or, equivalently, the constant function to 0). The restriction of an in nite sequence ⇡ 2!! to its rst n-many bits is denoted by ⇡ n.
We use standard notation and terminology about strings: The set of all nite strings of numbers is denoted by !<! . The symbol denotes the empty string. The concatenation of strings , ⌧ is denoted by _⌧ . The length of a string is denoted by | |. If there is ⇢ so that _⇢ = ⌧ , we say that is a pre x of ⌧ and we write ⌧ . Similarly, if ⇡ 2!<! and = ⇡ n for some n, we write ⇡ .
In order to formulate our problems as subsets of !, it will be convenient to encode pairs of numbers into single numbers. The pairing function does this. Fix p : ! ⇥ ! ! ! to be a computable bijection. We adopt the common habit of denoting p(x, y) by hx, yi.
The encodings discussed in Section 4 heavily rely on the di culty of calcuting paths through trees. As is common in computability theory, we say that a tree is a set T ✓ !<! closed under pre xes. We picture trees growing upwards, with _i to the left of _j, whenever i < j. A path ⇡ 2!! through a tree T ✓ !<! is an in nite sequence so that ⇡ n 2 T, for all numbers n. The set of paths through a tree T is denoted by [T ]. T is well-founded if [T ] = ; and otherwise is ill-founded. Note that we follow the standard terminology in computability theory requiring that paths be in nite. Indeed, if one were to allow paths to be nite, then these notions trivialize, since one could computably nd a path through any given computable tree. For example, the set of strings
T := { } [ { , _1 : (8 n < | |)( (n) = 0)} is an ill-founded tree with [T ] = {01 }. If T contains strings of arbitrary length, then T has in nite height. Note that there are trees of in nite height which are well-founded, e.g., T = {n_ : | | n}.
A basic problem that one encounters when attempting to calibrate the algorithmic complexity of in nite AFs is that of describing in nite objects in a nitary way. Computability theory o ers a wide range of tools designed for this endeavour. Here, we will concentrate on AFs that are computably presentable, in the sense that there are Turing machines (or, equivalently, modern computer programs) that, in nitely many steps, decide whether a given pair of arguments belongs to the attack relation.
Notation. Let ( e)e2 ! be a uniformly computable enumeration of all computable functions from ! to {0, 1}.
De nition 3.1. A number e is a computable index for an AF F = (AF , RF ), if there is a computable bijection f : ! ! AF so that e(hx, yi) = (1 0 if f (x) ⇢ f (y) otherwise.
An AF F is computably presented, if it has a computable index e 2!.
We use the notation Fe to refer to the AF with computable index e (note that every computable AF possesses in nitely many computable indices.). We let an refer to the element of AFe given by f (n).
Remark 3.2. The collection of computable indices for AFs just de ned is noncomputable (in particular, any index e for a non-total computable function e cannot be a computable index for an argumentation framework). There are alternative indexings that circumvent this issue; yet, adopting another indexing would not alter the complexity of the computational problems we analyze, though it would make the proofs slightly more cumbersome. Hence, we opt for the simplicity of De nition 3.1.
The bene t of dealing with computable AFs is that the complexity of the decision problems associated with them do not arise due to complexity of the argumentation framework itself, but rather re ects the inherent complexity of the decision problem. Further, the computational problems associated with computable AFs can be naturally represented as subsets of !, which are suitable to be classi ed by computability theoretic means: De nition 3.3. For a semantics : 1. Cred1 := {he, ai 2! : (9 S 2 (Fe))(a 2S)}; 2. Skept1 := {he, ai 2! : (8 S 2 (Fe))(a 2S)}; 5. Uni1 := {e : (9 !S ✓ AFe )(S 2 (Fe))}.
We also introduce new semantics which make sense only in the in nite setting. This is motivated by the idea that, given an in nite AF, we might hope for our accepted sets to give us in nitely much information:
In a sense, these new semantics give a measure of how much con ict lies in a given AF. For example, if infad(F ) = ; for an AF F , then the size of any of its admissible extensions are negligible in comparison to the size of F , suggesting that the attack relation in F prevents simultaneously accepting any signi cant fraction of F -arguments.
As an illustration of why we might want to accept only in nite extensions, we consider that a given in nite AF may contain a single argument b so that b attacks every other argument, and every other argument attacks b. We imagine that b is a statement of extreme solipsism denying the truth of any other statement. While {b} is a stable extension, it represents a negligible fraction of arguments, and we may prefer not to accept it. In an in nite AF, any nite set is as negligible as {b}, so we may prefer to accept only in nite extensions.
The complexity classes that most naturally match the problems of De nition 3.3 are those of the ⌃ 11 and ⇧ 11 sets. The ⌃ 11 sets are formally de ned as those subsets of ! that are de nable in the language of second-order arithmetic using a single second-order existential quanti er ranging over subsets of ! followed by number quanti ers and the rst order functions and relations (+, ·, <, 0, 1, 2); for more details, see [18, §16]. ⇧ 11 sets are the complements of ⌃ 11 sets.
Proposition 3.4. For
2 {ad, stb, co, infad, infstb, infco}, Cred1 , Exist1 , NE1 , are ⌃ 11.
Proof. We rst consider 2 {ad, stb, co}. To de ne Cred1 , we see from De nition 3.3: Cred1 := {he, ai 2 ! : (9 S 2 (Fe)(a 2 S))} uses a single existential quanti er over sets S. This is similarly true for the de nitions of Exist1 and NE1 in De nition 3.3. Thus, it su ces to see that the condition S 2 (Fe) can be de ned with only quanti cation over arguments (which are encoded as numbers), not needing quanti cation over sets of arguments. Note that the de nition of S+ and S uses only quanti ers over arguments. Thus, the de nition of fF (S) given by a 2fF (S) if and only if {a} ✓ S+ uses only quanti ers over arguments. Finally, S 2ad(F ), S 2stb(F ), S 2co(F ) are all de ned from fF (S) and S+ using only quanti ers over arguments.
In the case of 2 {infad, infstb, infco}, we need to also observe that S being in nite is de ned via 8 n9 m(am 2S ^ m > n), which uses only quanti ers over numbers.
Proposition 3.5. For Uni1 is ⇧ 11.
2 {ad, stb, co, infad, infstb, infco}, Skept1 is ⇧ 11 and, for 2 {ad, co}, Proof. The de nition of Skept1 in De nition 3.3 uses a single universal set-quanti er followed by only number quanti ers in the de nition of (Fe).
For 2 {ad, co}, e 2Uni1 if and only if there are not two di erent extensions (as there is always at least one extension). This is de ned by the negation of the following formula: (9 S19 S2)(9 x 2S1 r S2) ^ S1 2 (Fe) ^ S2 2 (Fe)).
Note that 9 S19 S2 can be replaced by a single existential quanti er by encoding the pair (S1, S2) as a single set {h1, xi : x 2S1} [ {h 2, yi : y 2S2}. This shows that Uni1 is the complement of a ⌃ 11 set, thus is ⇧ 11.
Remark 3.6. The above argument does not su ce to show that Uni1stb is also ⇧ 11, since some AFs have no stable extension. The most obvious de nition says there exists one stable extension and there does not exist two, which gives a de nition which is a conjunction of a ⌃ 11 and a ⇧ 11 condition, i.e., a so-called d-⌃ 11 de nition. This is analogous to the fact that in the nite case Unistb is DP-complete. Similarly, the argument above does not show that Uni1 is ⇧ 11 for 2 {infad, infstb, infco}. It is true that Uni1 is ⇧ 11 for 2 {stb, infad, infstb, infco}, but we will not include a proof in this paper.
We note that knowing that a problem is ⌃ 11 does not necessarily mean the problem is complicated. This only gives an upper bound for its complexity. Sometimes, a simpler de nition is achievable. As an example, we consider Credcf := {ha, ei : (9 S 2cf(Fe))(a 2S)}. Though the given de nition is ⌃ 11, to know if an argument a belongs to a con ict-free extension of Fe, it su ces to check whether a is non-self-defeating, i.e., a 6⇢ a, which is equivalent to checking the computable fact that e(hf 1(a), f 1(a)i) = 0. In contrast, we will show that for the computational problems associated to the admissible, stable, and complete semantics, the use of the quanti er ranging over all sets cannot be avoided.
We will heavily rely on the following fundamental theorem by Kleene which o ers a natural
way of representing ⌃ 11 sets:
Theorem 3.7 (Kleene [
We call (TnX )n2 ! a tree-sequence for X. As a corollary of Kleene’s theorem, one obtains that the problem of deciding which computable trees in !<! are ill-founded (or well-founded) is as hard as any other ⌃ 11 (resp., ⇧ 11) problem.
Theorem 3.7 gives a reason to consider the ⌃ 11 sets as the natural in nite analogs of the NP problems. Namely, given an ill-founded computable tree T and a sequence ⇡ which is a path through T , it’s relatively simple to check that ⇡ 2[T ] (it requires checking in nitely many simple facts: ⇡ n 2 T, for each n), but nding a sequence ⇡ 2[T ]—or even knowing whether there exists a sequence ⇡ 2[T ]—is a far harder problem.
Our main goal is to exactly characterize the complexity of the computational problems described in De nition 3.3. To do so, we need to show that they are complete for their respective complexity classes. The following de nition formalizes this notion. De nition 3.8. Let be a complexity class (e.g., 2 {⌃ 11, ⇧ 11}). A set V ✓ ! is -hard, if for every X 2 there is a computable function f : ! ! ! so that x 2X if and only if f (x) 2V . If V is -hard and belongs to , then it is -complete.
Proposition 3.9. It follows from Theorem 3.7 that the set of indices for ill-founded computable trees is a ⌃ 11-complete set. Similarly, the set of indices for well-founded computable trees is a ⇧ 11-complete set.
The following result is far less obvious, but will be useful below to examine Uni1 . Theorem 3.10 ([21, Theorem 18.11]). The set UB of indices for computable trees with exactly one path is a ⇧ 11-complete set.
Remark 3.11. The hardness in Theorem 3.10 is quite easy. We can reduce the question of whether a tree T is well-founded to whether a tree T 0 has two paths, where T 0 always has at least one path, by simply giving T 0 one more path than T (e.g. T 0 = {1_ : 2 T } [ { : (8 n < | |) (n) = 0}). The fact that UB is itself ⇧ 11 is the subtle part of Theorem 3.10.
Theorem 3.7 along with De nition 3.8 suggest a natural approach for gauging the complexity of the computational problems of De nition 3.3. Namely, given another ⌃ 11 (or ⇧ 11) set X, we translate the question asking whether n 2X to the question of if the tree TnX is ill-founded (resp., well-founded), and then we need to computably nd an instance of our computational problem which should be accepted if and only if TnX is ill-founded (resp., well-founded). This involves coding a tree, or more precisely, the collection of paths through a tree into the extensions in an argumentation framework. We do exactly this in Section 4.
Remark 3.12. As noted before, the ⌃ 11 sets are natural analogs in the in nitary setting of the NP sets, and the ⇧ 11 sets are the natural analogs of the coNP sets. With the exception of Skept1co and Uni1stb, Table 2 follows this translation from Table 1 for the rst three rows. These two results mark surprising di erences in the in nite setting.
The trivial entries are due to the fact that ; is always an admissible extension and the grounded extension is always a complete extension.
We propose a way to more fully understand the complexity of the problem of nding a extension in a given AF F .
De nition 3.13. For each e 2! and semantics , let Spec¬; (Fe) be the set of Turing degrees of non-empty sets X ✓ ! so that {an : n 2X} is a extension in Fe.
The notion Spec¬; (Fe) exactly captures the di culty of computing a non-empty extension in Fe. We will be relating the problem of computing a extension in Fe to the problem of nding a path through a particular tree. So, we de ne the analogous notion of the spectrum of a tree.
De nition 3.14. Given any computable tree T , we let Spec(T ) be set of Turing degrees of paths X 2[T ].
Our main result in this direction is the following: Theorem 3.15. For 2 {ad, stb, co, infad, infstb, infco} and for any computable tree T , there exists a computable AF Fe so that Spec¬; (Fe) = Spec(T ).
When 2 {ad, stb, infad, infstb}, future work will show the converse, namely that for every e, there is a computable tree so that Spec¬; (Fe) = Spec(T ). Table 3 collects our results on Spectra of extensions.
ad stb co infad infstb infco
Spec¬; Exactly Spec(T ) Exactly Spec(T ) Any Spec(T ) Exactly Spec(T ) Exactly Spec(T )
Any Spec(T )
We now discuss some consequences of these characterizations on the problem of, given a computable argumentation framework, computing some extension. The hyperarithmetical sets are, in a very general sense, considered the collection of constructible subsets of the natural numbers. Formally, a set is hyperarithmetical if and only if it is both ⌃ 11 and ⇧ 11. The hyperarithmetical degrees are particularly useful as a yardstick of complexity because a set X is hyperarithmetical if and only if it is computed from a set Y which can be reached by (trans nitely) iterating the halting jump operator. Thus, the number of iterations of the halting jump needed to compute X yields a useful yardstick for the complexity of X. For more information about the hyperarithmetical hierarchy, see [19, Chapter 5].
Proposition 3.16. For each 2 {ad, stb, co, infad, infstb, infco}, there is a computable argumentation framework Fe which has continuum many non-empty extensions, yet no hyperarithmetical non-empty extension.
(We take this to mean that there is no uniform way to construct—even with arbitrary access to the halting jump operator—a extension).
Proof. There exists a computable tree with uncountably many paths yet no hyperarithmetical path [18, Corollary XLI(b)]. Applying Theorem 3.15 to this tree yields a computable argumentation framework with uncountably many non-empty extensions, yet no hyperarithmetical non-empty extension.
In the case of Proposition 3.16, there are extensions that are not particularly computationally powerful. They are not hyperarithmetical, but they also compute no hyperarithmetical sets. We can think of them as on the side of the hyperarithmetical hierarchy, thus simply not measured by the yardstick. This is always the case if an in nite AF has continuum many extensions. On the other hand, if a computable argumentation framework has a unique extension, the picture is quite di erent. In forthcoming work, we will settle the following conjecture. Conjecture 3.17. Let be in {ad, stb, co, infad, infstb, infco} and suppose that Fe is a computable argumentation framework with a unique non-empty extension. Then, the non-empty extension of Fe is hyperarithmetical.
On the other hand, we can show that there is no bound in the hyperarithmetical hierarchy on how complicated this extension might be.
Theorem 3.18. Let be in {ad, stb, co, infad, infstb, infco} and let H be a hyperarithmetical set. Then, there exists a computable AF Fe with a single non-empty extension X so that X computes H .
Proof. This follows from Theorem 3.15 by encoding a tree with a single path ⇡ so that ⇡ computes H . Such a tree is known to exist for any hyperarithmetical H [18, Corollary XLIV(d)].
This section is devoted to our hardness results: we provide lower bounds for the complexity of our computational problems. In particular, given a tree T ✓ ! <! , we will de ne an argumentation framework F T = (AT , RT ). The set of arguments AT of F T is computable and consists of {a : 2 T } [ { b : 2 T }. The attack relation RT of F T contains all and only the following edges: For all 2 T, 10
11 0 1 a10 a0 b10 b0 a a11 a1 b b11 b1
.
Notation. For ⇡ 2[T ] and n 2!, let S⇡n be the set {a : ⇡ and | | n}.
Lemma 4.1. A non-empty extension S of F T is admissible i S is exactly S⇡n for some ⇡ 2[T ] and n 2!.
Proof. ()): Suppose that S 6= ; belongs to ad(F T ). First, observe that no b can be in S, as all such arguments are self-defeating and S must be con ict-free. Next, observe that, if a⌧ 2S, then there must be some i so that a⌧ _i 2S: this is because some element of S must defend a⌧ from b⌧ and such an element must be an a with | | = |⌧ | + 1. But it must have ⌧ as otherwise a would attack a⌧ .
Finally, take ⇢ of minimal length so a⇢ 2S. Then the previous paragraph shows that S contains S⇡|⇢ | for some ⇡ 2[T ] with ⇢ ⇡ . Since ⇢ was chosen of minimal length, no a⌧ with ⌧ shorter can be in S. Moreover, no a⌧ with |⌧ | |⇢ | and ⌧ 6 ⇡ can be in S, as otherwise S would not be con ict-free. Thus, S = S⇡|⇢ |.
(( ): Any element which attacks a⇡ n is itself attacked by either a⇡ n+1 or a⇡ n+2 , so S⇡n ✓ fFT (S).
Lemma 4.2. An extension S of F T is stable i S is exactly S⇡0 for some ⇡ 2[T ]. Proof. ()): Suppose that S 2stb(F T ). Then, since S is admissible, we know S = S⇡n for some ⇡ 2[T ] and n 2!. Since b is the only the argument that attacks a and b 2/S, it must be the case that a 2S. Thus, n = 0.
(( ): Observe that S⇡0 is con ict-free and any other argument of F T is contained in (S⇡0)+. Thus, S⇡0 is a stable extension of F T .
Lemma 4.3. A non-empty extension S of F T is complete i S is S⇡0 for some ⇡ 2[T ]. Proof. ()): Suppose that S 6= ; belongs to co(F T ). Since complete extensions are admissible, we see that S = S⇡n, for some X 2[T ] and n 2!. But observe that if n > 0, then S would not be complete: indeed, a with = ⇡ n 1 would be defended by S but not in S. Thus, n must be equal to 0.
(( ): This follows since S⇡0 is stable and all stable extensions are complete.
We are now in a position to obtain hardness results for the computational problems described in De nition 3.3.
Theorem 4.4. The following hold: 1. for 2. for 3. for 2 {ad, stb, co, infad, infstb, infco}, NE1 is ⌃ 11-hard; 2 {stb, infad, infstb, infco}, Exist1 is ⌃ 11-hard; 2 {ad, stb, co, infad, infstb, infco}, Cred1 is ⌃ 11-hard.
Proof. 1. Let X 2⌃ 11 and let (TnX )n2 ! be a tree-sequence for X, as given by Theorem 3.7. To show ⌃ 11-hardness, we need to produce a computable function f so that n 2X if and only if f (n) 2NE1 . We let f (n) be a computable index for F TnX . Then Lemmas 4.1, 4.2, and 4.3 prove that n 2X if and only if TnX is ill-founded if and only if F TnX has a non-empty extension for each 2 {ad, stb, co, infad, infstb, infco}.
2. For each of these , the empty set is not a extension, so Exist1 = NE1 , which we showed above is ⌃ 11-hard.
3. In the proof of 1. above, we reduced a given ⌃ 11 set X to NE1 by sending n to F TnX . Note that F TnX has a non-empty extension if and only a is in some extension. Thus sending n to the he, a i where e is a computable index for F TnX shows that Cred1 is ⌃ 11-hard. Theorem 4.5. For
2 {ad, stb, co, infad, infstb, infco}, Uni1 is ⇧ 11-hard.
Proof. We rst consider 2 {ad, co}. Let X 2⇧ 11 and let (Tn!!rrXX. )Nno2t!e btheaat t;reise-asneqaudemnicsesibfoler its complement. For n 2!, consider the sequence of AFs F Tn extension in any AF and since every argument in F Tn!rX is attacked, ; is also a complete extension. Thus, F Tn!rX has a unique extension if and only if Tn!rX is well founded if and only if n 2X, which shows that Uni1ad and Uni1co are ⇧ 11-hard.
For the other , ; is not a extension. We use Theorem 3.10 to show ⇧ 11-hardness. Let X be any ⇧ 11 set. Then we get from Remark 3.11 a sequence of trees Tn0 so that 01 2[Tn0] for each n, and {n : Tn0 has only one path} is ⇧ 11-hard. It follows from Lemmas 4.1, 4.2, and 4.3 that this is if and only if F Tn0 has a unique extension, which shows that ⇧ 11-hardness of Uni1 .
F T , Skept1infad = ; .
Theorem 4.7. Skept1infad is ⇧ 11-hard.
Theorem 4.6. For any
2 {stb, infstb, infco}, Skept1 is ⇧ 11-hard.
Proof. Let X be a ⇧ 11 set. Then we get from Remark 3.11 a sequence of trees Tn0 so that 01 2[Tn0] for each n, and {n : Tn0 has only one path} is ⇧ 11-hard. Then, note that he, a0i 2Skept1 where e is a computale index for Tn0 if and only if Tn0 only has paths ⇡ with ⇡ (0) = 0 if and only if Tn0 has only one path (see the de nition of Tn0 in Remark 3.11) if and only if n 2X. This shows the ⇧ 11-hardness of Skept1 .
We note that the above argument does not work for infad since, even if ⇡ is the only path through a tree T , each S⇡n is an in nite admissible extension in F T and Tn S⇡n = ; , so in any Proof. Let X be a ⇧ 11 set. We get from Remark 3.11 a sequence of trees Tn0 so that each has one path 01 2 Tn0 and has another path extending 1 if and only if n 2/X.
For each n 2!, we construct an AF Gn = (AGn , RGn ) slightly larger than F Tn0 . In particular AGn = AFTn0 [ { x0, y0, x1, y1}. We let (w, z) 2RGn if • w, z 2AFTn0 and (x, y) 2RFTn0 • w = yi and z = yi • w = xi and z = x1 i • w = xi and z = yi • w = yi and z = a where (0) = i • w = a with (0) = i and z = y1 i Lemma 4.8. An in nite S ✓ AGn is an admissible extension if and only if it equals a set S⇡k [ { x⇡ (0)} for some ⇡ 2[Tn0] and k 2!.
Proof. Let U be an in nite admissible extension. Note rst that arguments y0, y1 and b cannot be in U since they are self-defeating. Then, since U is in nite, U must contain elements a for Bu2tthTne0.nBsyintcheeesaacmheelaermguemnteonft Sa sn⇡ iins Laettmacmkaed4.b1y,wy⇡e(g0)e,twtheamtUus\t hAavFeTnx0⇡ =(0)S2⇡nfUortsoodmeefe⇡ nd them. 2[Tn0].
This excludes x1 ⇡ (0) from U since U is con ict-free.
It is straightforward to check that each of these are in fact admissible extensions.
Finally, note that x0 is in every in nite admissible extension of Gn if and only if there is no ⇡ 2[Tn0] which extends 1 if and only if n 2X, showing that Skept1infad is ⇧ 11-hard. Theorem 4.9. For 2 {ad, stb, co, infad, infstb, infco} and for any computable tree T , there exists a computable AF Fe so that Spec¬; (Fe) = Spec(T ).
Proof. Observe that for the AF Fe = F T , it follows from Lemmas 4.1, 4.2, and 4.3 that the non-empty extensions are all in nite and are in the same Turing degrees as the paths through T .
In this paper, we initiated a systematic exploration of the complexity issues inherent to in nite argumentation frameworks. To pursue this direction, we employed computability-theoretic techniques which are ideally suited for assessing the complexity of in nite mathematical objects. Our focus was on the credulous and skeptical acceptance of arguments, as well as the existence and uniqueness of extensions, for admissible, complete, and stable semantics. The computational problems we examined were found to be maximally complex, properly belonging to the complexity classes of ⌃ 11 and ⇧ 11 sets. We also introduced and explored new semantics that are meaningful exclusively in the in nite setting, concerning the existence of in nite extensions that satisfy a given semantics .
It is natural to conceive of an argumentative scenario with arguments being added as time proceeds, such as the ongoing accumulation of scienti c studies. Then, in nite frameworks naturally emerge as the union of the frameworks observed at each nite time. A key question, then, is how the acceptance of arguments within the in nite framework F can be related to the acceptance within the nite frameworks (Ft) which have appeared by time t. Our results show that, for complexity reasons alone, credulous and skeptical acceptance of arguments in F cannot be understood in terms of any kind of limiting procedure applied to the same problems in Ft.
A plethora of intriguing questions regarding the complexity of in nite AFs remains open. In forthcoming extensions of this work, we shall ll the gaps that we left behind (such as the entries marked with a dagger in Table 2). Next, we will show that the techniques introduced here enable the construction of a single argumentation framework witnessing our hardness results, thereby proving that solving these problems is not only challenging for the entire class of argumentation frameworks but also remains di cult for an individual, speci c framework.
Finally, future research will extend our analysis to analogous problems associated with other key semantics for AFs, including grounded, preferred, and ideal semantics. Given that the de nitions of these semantics are more intricate than those we examined here, we anticipate the need for additional techniques to thoroughly analyze them.
Andrews was partially supported by NSF grant DMS-2348792. San Mauro is a member of INDAM-GNSAGA. [1] P. Baroni, F. Cerutti, P. E. Dunne, M. Giacomin, Automata for in nite argumentation structures, Arti cial Intelligence 203 (2013) 104–150. [2] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Arti cial intelligence 77 (1995) 321– 357.