avenue in finite AFs has been determining the algorithmic complexity of tasks associated with finding
coherent collections of arguments (up to suitable collection of semantics), with numerous complexity
theoretic results highlighting their inherent computational intractability (see, e.g., [
This paper addresses this gap by initiating a systematic study of the complexity of computational problems in infinite AFs. For this endeavor, we bring into the subject of argumentation theory the machinery of computability theory, which may be regarded as an infinitary companion of computational complexity theory and abounds with concepts and hierarchies for measuring the complexity of computing and defining countably infinite objects, providing the appropriate machinery for this endeavor.
The application of computability theoretic tools outside of mathematical logic is a well-established
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 benefits of viewing infinite AFs through computability theoretic lenses. 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.
Organization of the paper Section 2 briefly 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 define the concept of computable AFs and the computational issues that emerges from it. In Section 4, we determine the lower bounds of the complexity for our computational problems: a critical technique for achieving hardness results involves suitably encoding trees into AFs. Finally, in Section 5, we show that our techniques introduced enable the construction of a single argumentation framework witnessing our hardness results. Our main results are collected in Tables 2 and 3.
To keep our paper self-contained, we now briefly 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) ∈ RF . 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 : (∃y ∈ S)(y ↣ S− = {x : (∃y ∈ S)(x ↣ 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}.
A semantics σ assigns to every AF F a set of extensions σ (F ) which are deemed as acceptable. A huge number of semantics, fueled by diferent motivations, have been proposed and analyzed. Here, we focus on three prominent choices, whose computational aspects are well-understood in the finite setting: admissible, complete, and stable semantics (abbreviated by ad, stb, co, respectively).
Let F = (AF , RF ) be an AF. Denote by cf(F ) the collection of extensions of F which are conflict-free (i.e., S ∈ cf(F ) if a ↣̸ b, for all a, b ∈ S). Then, for S ∈ cf(F ), • S ∈ ad(F ) if S is self-defending (i.e., S ⊆ fF (S)); • S ∈ co(F ) if S is a fixed point of fF (i.e., S = fF (S)); • S ∈ stb(F ), if S attacks all arguments outside of it (i.e., S+ = AF ∖ S).
In discussing the complete extensions, we will also briefly mention the grounded extension, which is the unique smallest fixed point of fF ; in any AF, the grounded extension always exists [3, Theorem 3].
For a given semantics σ , the following are some 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 ∈ S for some S ∈ σ (F ); • Skeptσ (for skeptical acceptance) is the decision problem whose accepting instances are the pairs (F , a) so that a ∈ S for all S ∈ σ (F ); • Existσ is the decision problem whose accepting instances are the AFs F so that σ (F ) ̸= ∅; • NEσ is the decision problem whose instances are the AFs F so that σ (F ) ∖ {∅} ̸= ∅; • 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[
σ ad stb co
NP-c NP-c NP-c Skeptσ trivial coNP-c P-c
trivial NP-c trivial
NEσ NP-c NP-c NP-c
Uniσ
coNP-c
DP-c
coNP-c
3. Computational problems for AFs through the lens of computability
theory
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 the textbooks [
We use standard notation and terminology about strings: The set of all finite 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 prefix of τ and we write σ ⪯ τ . Similarly, if π ∈ ωω 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 ⟨x, y⟩.
The encodings discussed in Section 4 heavily rely on the dificulty of calculating paths through trees. As is common in computability theory, we say that a tree is a set T ⊆ ω<ω closed under prefixes. We picture trees growing upwards, with σ ⌢i to the left of σ ⌢j, whenever i < j. A path π ∈ ωω through a tree T ⊆ ω<ω is an infinite sequence so that π ↾ n ∈ 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 infinite. Indeed, if one were to allow paths to be finite, then these notions trivialize, since one could computably find a path through any given computable tree. For example, the set of strings
T := {λ } ∪ {,σ σ
⌢1 : (∀n < |σ |)(σ (n) = 0)} is an ill-founded tree with [T ] = {0∞}. If T contains strings of arbitrary length, then T has infinite height. Note that there are trees of infinite height which are well-founded, e.g., T = {λ } ∪ {n⌢σ : |σ | ≤ n}. 3.2. Computable argumentation frameworks A basic problem that one encounters when attempting to calibrate the algorithmic complexity of infinite AFs is that of describing infinite objects in a finitary way. Computability theory ofers 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 finitely many steps, decide whether a given pair of arguments belongs to the attack relation. Notation. Let (Φe)e∈ω be a uniform enumeration of all partial computable functions from ω to {0, 1}.
A number e is a computable index for an AF F = (AF , RF ) with AF = {an : n ∈ ω} Definition 3.1. so that Φe(⟨n, m⟩) = (1 0 if an ↣ otherwise.
am An AF F is computable, if it has a computable index e ∈ ω.
We use the notation Fe to refer to the AF with computable index e (note that every computable AF possesses infinitely many computable indices.).
Remark 3.2. The collection of computable indices for AFs just defined 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 Definition 3.1.
The benefit 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 reflects 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 classified by computability theoretic means: Definition 3.3. For a semantics σ : 1. Credσ∞ := {⟨e, n⟩ : (∃S ∈ σ (Fe))(an ∈ S)}; 2. Skeptσ∞ := {⟨e, n⟩ : (∀S ∈ σ (Fe))(an ∈ S)}; 3. Existσ∞ := {e : (∃S ⊆
AFe ))(S ∈ σ (Fe))}; 4. NEσ∞ := {e : (∃S ∈ σ (Fe))(S ̸= ∅)}; 5. Uniσ∞ := {e : (∃!S ⊆
AFe )(S ∈ σ (Fe))}.
For items 1. and 2. above, it’s also natural to consider their restrictions to a specific computable AF Fe. That is, we define
Credσ∞(Fe) = {n : ⟨e, an⟩ ∈ Credσ∞}
Skeptσ∞(Fe) = {n : ⟨e, an⟩ ∈ Skeptσ∞}.
We note that in the finite setting, Credσ (F ) or Skeptσ (F ) for a finite AF F , is simply a finite subset of AF , so it does not encode much complexity in itself. In constrast, in the infinite setting, Credσ∞(Fe) and Skeptσ∞(Fe) are infinite subsets of ω, and it makes sense to ask about whether this set is decidable; and if not, to understand its complexity. In these definitions, we use the number n in place of an so that these sets are subsets of ω, thus amenable to computability-theoretic analyses, yet when working with a given AF F , we often write the argument an in place of the number n.
We also introduce new semantics which make sense only in the infinite setting. This is motivated by the idea that, given an infinite AF, we might hope for our accepted sets to give us infinitely much information.
1. S ∈ infad(F ) if and only if S ∈ ad(F ) and S is infinite; 2. S ∈ infco(F ) if and only if S ∈ co(F ) and S is infinite; 3. S ∈ infstb(F ) if and only if S ∈ stb(F ) and S is infinite.
The complexity classes that most naturally match the problems of Definition 3.3 are those of the Σ1 1 and Π1 sets. The Σ11 sets are formally defined as those subsets of ω that are definable in the language of 1 second-order arithmetic using a single second-order existential quantifier ranging over subsets of ω followed by number quantifiers and the first order functions and relations (+, · , <, 0, 1, ∈); for more details, see [18, §16]. Π11 sets are the complements of Σ11 sets.
Proposition 3.4. Credσ∞, Existσ∞, and NEσ∞ are Σ11, for σ ∈ {ad, stb, co, infad, infstb, infco}. Proof. We first consider σ ∈ {ad, stb, co}. To define Credσ∞, we see from Definition 3.3: Credσ∞ := {⟨e, n⟩ ∈ ω : (∃S ∈ σ (Fe)(an ∈ S))} uses a single existential quantifier over sets S. This is similarly true for the definitions of Existσ∞ and NEσ∞ in Definition 3.3. Thus, it sufices to see that the condition S ∈ σ (Fe) can be defined with only quantification over arguments, which are in bijection with ω, not needing quantification over sets of arguments.
Note that the definition of S+ and S− use only quantifiers over arguments. Thus the definition of fF (S) given by a ∈ fF (S) if and only if {a}− ⊆ S+ uses only quantifiers over arguments. Finally, S ∈ ad(F ), S ∈ stb(F ), S ∈ co(F ) are all defined from fF (S) and S+ using only quantifiers over arguments.
In the case of σ ∈ {infad, infstb, infco}, we need to also observe that S being infinite is defined via ∀n∃m(am ∈ S ∧ m > n), which uses only quantifiers over numbers.
Proposition 3.5. Skeptσ∞ is Π11, whenever σ is in {ad, stb, co, infad, infstb, infco}. Furthermore, for σ ∈ {ad, co}, Uniσ∞ is Π11. Proof. The definition of Skeptσ∞ in Definition 3.3 uses a single universal set-quantifier followed by only number quantifiers in the definition of σ (Fe).
For σ ∈ {ad, co}, e ∈ Uniσ∞ if and only if there are not two diferent σ extensions (as there is always at least one σ extension). This is defined by the negation of the following formula:
(∃S1∃S2)(∃x ∈ S1 ∖ S2 ∧ S1 ∈ σ (Fe) ∧ S2 ∈ σ (Fe)).
Note that ∃S1∃S2 can be replaced by a single existential quantifier by encoding the pair (S1, S2) as a single set {⟨1, x⟩ : x ∈ S1} ∪ {⟨2, y⟩ : y ∈ S2}. This shows that Uniσ∞ is the complement of a Σ11 set, thus is Π1.
1 Remark 3.6. The above argument does not sufice to show that Unis∞tb is also Π11, since some AFs have no stable extension. The most obvious definition says there exists one stable extension and there does not exist two, which gives a definition which is a conjunction of a Σ11 and a Π11 condition, i.e., a so-called d-Σ11 definition. This is analogous to the fact that in the finite case Unistb is DP-complete. Similarly, the argument above does not show that Uniσ∞ is Π11 for σ ∈ {infad, infstb, infco}. Yet, it is true that Uniσ∞ is Π11 for σ ∈ {stb, infad, infstb, infco}, as we show in [1, Section 6].
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 definition is achievable. As an example, we consider Credcf := {⟨e, n⟩ : (∃S ∈ cf(Fe))(an ∈ S)}. Though the given definition is Σ11, to know if an argument an belongs to a conflict-free extension of Fe, it sufices to check whether an is non-self-defeating, i.e., an ̸↣ an, which is equivalent to checking the computable fact that Φe(⟨n, n⟩) = 0. In contrast, we will show that for the computational problems associated to the admissible, stable, and complete semantics, the use of the quantifier ranging over all sets cannot be avoided.
We will heavily rely on the following fundamental theorem by Kleene which ofers a natural way of
representing Σ11 sets:
Theorem 3.7 (Kleene [
We call (TnX )n∈ω 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 infinite analogs of the NP problems. Namely, given an ill-founded computable tree T and a sequence π which is a path through T , it is relatively simple to check that π ∈ [T ] (it requires checking infinitely many simple facts: π ↾ n ∈ T , for each n), but finding a sequence π ∈ [T ]—or even knowing whether there exists a sequence π ∈ [T ]—is a far harder problem.
Our main goal is to exactly characterize the complexity of the computational problems described in Definition 3.3. To do so, we need to show that they are complete for their respective complexity classes. The following definition formalizes this notion.
Definition 3.8. Let Γ be a complexity class (e.g., Γ ∈ {Σ11, Π11}). A set V ⊆ ω is Γ-hard, if for every X ∈ Γ there is a computable function f : ω → ω so that x ∈ X if and only if f (x) ∈ V . 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 example is far less obvious, but will be useful below to examine Uniσ∞. Theorem 3.10 ([20, 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 ′ has two paths, where T ′ always has at least one path, by simply giving T ′ one more path than T (e.g. T ′ = {1⌢σ : σ ∈ T } ∪ {σ : (∀n < |σ |)σ (n) = 0}). The fact that UB is itself Π11 is the subtle part of this example.
Theorem 3.7 along with Definition 3.8 suggest a natural approach for gauging the complexity of the computational problems of Definition 3.3. Namely, given another Σ11 (or Π11) set X , we translate the question asking whether n ∈ X to the question of if the tree TnX is ill-founded (resp., well-founded), and then we need to computably find 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 infinitary setting of the NP sets, and the Π11 sets are the natural analogs of the coNP sets. With the exception of Skeptc∞o and Unis∞tb, Table 2 follows this translation from Table 1 for the first three rows. These two results mark surprising diferences in the infinite setting.
The trivial entries are due to the fact that ∅ is always an admissible extension and the grounded extension is always a complete extension. 3.3. Spectra of σ extensions We propose a way to more fully understand the complexity of the problem of finding a σ extension in a given AF F .
Definition 3.13. For each e ∈ ω and semantics σ , let Specσ¬∅(Fe) be the set of Turing degrees of non-empty sets X ⊆ ω so that {an : n ∈ X } is a σ extension in Fe.
The notion Specσ¬∅(Fe) exactly captures the dificulty of computing a non-empty σ extension in Fe. We will be relating the problem of computing a σ extension in Fe to the problem of finding a path through a particular tree. So, we define the analogous notion of the spectrum of a tree. Definition 3.14.
Given any computable tree T , we let Spec(T ) be set of Turing degrees of paths X ∈ [T ].
Theorem 3.15. For σ ∈ {ad, stb, co, infad, infstb, infco} and for any computable tree T , there exists a computable AF Fe so that Specσ¬∅(Fe) = Spec(T ). In [1, Theorem 3.15], we prove the converse for σ ∈ {ad, stb, infad, infstb}: 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.
We now discuss a few of its implications for the problem of computing σ extensions of computable AFs. The hyperarithmetical sets are often used as a yardstick to measure complexity of undecidable problems. 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 (transfinitely) 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 [18, §16.8]. Proposition 3.16. There is a computable argumentation framework Fe which has continuum many non-empty σ extensions, yet no hyperarithmetical non-empty σ extension, whenever σ is in {ad, stb, co, infad, infstb, infco}.
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. For example, there are two σ extensions, each undecidable, so that the only sets they both compute are the computable sets. Thus, though there is no hyperarithmetical solution, there is also no undecidable information coded into every solution. This is always the case if an infinite AF has continuum many σ extensions. On the other hand, if a computable argumentation framework has only countably many σ extensions, the picture is quite diferent.
Theorem 3.17 ([
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 σ ∈ {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)]. 4. Encoding a tree into an argumentation framework Given a tree T ⊆ ω<ω, we will define an argumentation framework F T = (AT , RT ). The set of arguments AT of F T is computable and consists of {aσ : σ ∈ T } ∪ {bσ : σ ∈ T } ∪ {c}. The attack relation RT of F T contains all and only the following edges: For all σ ∈ T , 1. bσ ↣ 2. bσ ↣ 3. aσ ↣ 4. aσ ↣ 5. c ↣ 6. aλ ↣ bσ ; aσ ; aτ for every τ ∈ T ; a10 a0
Figure 1 gives an example of our encoding for a finite tree. We next consider which extensions in F T are admissible, stable, or complete.
Notation. For π ∈ [T ], let Sπ be the set {aσ : σ ≺ π }.
Lemma 4.1. A non-empty extension S of F T is stable if S is complete if S is admissible if S is exactly Sπ for some π ∈ [T ].
Proof. Stable always implies complete, which always implies admissible. It is straightforward to check that Sπ is stable for any π ∈ [T ], so we need only show that any non-empty admissible extension is exactly some Sπ . Suppose that S is admissible. Observe that c and bσ cannot be in S since these are self-defeating. So some aσ ∈ S since S is non-empty. Note that since c ↣ aσ , we must have aλ ∈ S. Next, observe that if aτ ∈ S, then there must be some i so that aτ ⌢i ∈ S: 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τ . It follows that S contains Sπ for some π ∈ [T ]. Since Sπ is stable, S cannot properly contain Sπ , so S = Sπ .
We are now in a position to obtain hardness results for the computational problems described in Definition 3.3.
Theorem 4.2. The following hold: 3. for σ ∈ {ad, stb, co, infad, infstb, infco}, Credσ∞ is Σ11-hard.
Proof. 1. Let X ∈ Σ1 and let (TnX )n∈ω be a tree-sequence for X, as given by Theorem 3.7. To show Σ11 1 hardness, we need to produce a computable function f so that n ∈ X if and only if f (n) ∈ NEσ∞. We let f (n) be a computable index for F TnX . Then Lemma 4.1 shows that n ∈ X if and only if TnX is ill-founded if and only if F TnX has a non-empty σ extension for each σ ∈ {ad, stb, co, infad, infstb, infco}.
2. For each of these σ , the empty set is not a σ extension, so Existσ∞ = NEσ∞, which we showed above is Σ11-hard.
3. In the proof of 1. above, we reduced a given Σ11 set X to NEσ∞ by sending n to F TnX . Note that F TnX has a non-empty σ extension if and only if aλ is in some σ extension. Thus sending n to ⟨e, aλ ⟩ where e is a computable index for F TnX shows that Credσ∞ is Σ11-hard.
Theorem 4.3. For σ ∈ {ad, stb, co, infad, infstb, infco}, Uniσ∞ is Π11-hard. cPoromopf.leWmeenfirts.tCcoonnssiiddeerrth eσ se∈qu{eandc,ecoo}f.AFLset(FXTnω∈∖XΠ)11n∈aωn.dNloette(tThnaωt∖∅Xi)sna∈nω abdemaisstribelee-seexqteunesniocen finoranitys AF and since every argument in F Tnω∖X is attacked, ∅ is also a complete extension. Thus, F Tnω∖X has a unique σ extension if and only if Tnω∖X is well founded if and only if n ∈ X, which shows that Unia∞d and Unic∞o 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 Tn′ so that 0∞ ∈ [Tn′] for each n, and {n : Tn′ has only one path} is Π11-hard. It follows from Lemma 4.1 that this holds if and only if F Tn′ has a unique σ extension, which shows the Π11-hardness of Uniσ∞.
Theorem 4.4. For any σ ∈ {stb, infstb, infco, infad}, Skeptσ∞ is Π11-hard.
Proof. Let X be a Π11 set. Then we get from Remark 3.11 a sequence of trees Tn′ so that 0∞ ∈ [Tn′] for each n, and {n : Tn′ has only one path} is Π11-hard. Then note that ⟨e, a0⟩ ∈ Skeptσ∞ where e is a computable index for Gn := FTn′ if and only if Tn′ only has paths π with π (0) = 0 if and only if Tn′ has only one path (see the definition of Tn′ in Remark 3.11) if and only if n ∈ X. This shows the Π11-hardness of Skeptσ∞.
Theorem 4.5. For σ ∈ {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 Lemma 4.1 that the non-empty σ extensions are all infinite and are in the same Turing degrees as the paths through T . 5. Complexity of Credσ∞(Fe) and Skeptσ∞(Fe) In this section, we examine the complexity of the problems Credσ∞(Fe) and Skeptσ∞(Fe) for a single computable argumentation framework Fe. Note that Credσ∞(Fe) is no more complicated than the full problem Credσ∞, so Credσ∞(Fe) is Σ11 for σ ∈ {ad, stb, co, infad, infstb, infco}, and Skeptσ∞(Fe) is Π11 for σ ∈ {stb, co, infad, infstb, infco}. Recall that Skepta∞d is trivial.
Here we show that even restricting to a single computable argumentation framework, these sets can be Σ11-complete or Π11-complete. We do omit discussion of Skeptc∞o (Fe), just as we omitted discussion of the hardness for Skeptc∞o above. This is because Skeptc∞o (Fe) is exactly the grounded extension of F . In future work giving a systematic analysis of the complexity of the grounded semantics in infinite argumentation frameworks, we will examine the remaining entry in Table 2, namely that Skeptc∞o is Π11-hard, and we will also consider the complexity of Skeptc∞o (Fe) for a single computable AF Fe.
In the previous section, we built AFs F T specifically to code a single Σ11-question into a single question about extensions in F T , e.g., T is ill-founded if and only if aλ ∈ Creda∞d (F T ). We will use the following notion of a disjoint union of AFs to build a single AF F so that Creda∞d (F ) codes multiple Σ1 1 questions.
Definition 5.1. If (F k)k∈ω is a countable sequence of argumentation frameworks where each F k = (Ak, Rk), then we define the disjoint union H of the sequence (F k)k∈ω as follows: H = (AH, RH), where AH = {⟨a, k⟩ : a ∈ Ak} and (⟨a, j⟩, ⟨b, k⟩) ∈ RH ⇔ j = k ∧ (a, b) ∈ Rk
Credc∞o (Fe) = Credi∞nfco(Fe) is Σ11-complete.
Lemma 5.2. Let H be the disjoint union of a sequence of AFs (F k)k∈ω and σ ∈ {ad, stb, co}. A set Y ⊆ AH is a σ extension of H if and only if for each n, Yn := {c ∈ An : ⟨c, n⟩ ∈ Y } is a σ extension in F n.
Theorem 5.3. There is a computable argumentation framework Fe so that Creda∞d (Fe) = Credi∞nfad(Fe) = Proof. Let X be a Σ11-complete set, and let (TnX )n∈ω be a tree-sequence for X. We consider the argumentation framework HX which is the disjoint union of the sequence (F TkX )k∈ω of argumentation frameworks. Note that since the sequence of trees TkX is a computable sequence of computable trees, HX is a computably presented argumentation framework.
Note that an argument ⟨aσ , k⟩ is a member of an admissible extension in HX if and only if aσ is a member of an admissible extension in F TkX by Lemma 5.2 and the fact that the empty set is an admissible extension in all of the F TnX . Similarly, ⟨aσ , k⟩ is a member of a complete extension in HX if and only if aσ is a member of a complete extension in F TkX . By Lemma 4.1, each of these conditions is equivalent to σ being on a path in [TkX ], thus Creda∞d (Fe) = Credc∞o (Fe). Since all of the non-empty admissible extensions in F TkX are infinite, these coincide with Cred i∞nfad(Fe) = Credi∞nfco(Fe).
We now give a reduction of X to Creda∞d (HX ). We need to give a computable function f so that n ∈ X if and only if f (n) ∈ Creda∞d (HX ). We define f (n) = ⟨aλ , n⟩. Then ⟨aλ , n⟩ ∈ Creda∞d (HX ) if and only if there is a path in [TnX ] if and only if n ∈ X, showing the Σ11-hardness of Creda∞d (HX ).
With a more cumbersome construction, given in [
Theorem 5.4 ([
In this paper, we initiated a systematic exploration of the complexity issues inherent to infinite
argumentation frameworks. To pursue this direction, we employed computability theoretic techniques
which are ideally suited for assessing the complexity of infinite 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. We introduced and explored new semantics
that are meaningful exclusively in the infinite setting, concerning the existence of infinite extensions
that satisfy a given semantics σ . The computational problems we examined (here and in [
A plethora of intriguing questions regarding the complexity of infinite AFs remains open. First, we
shall fill the gaps that we left behind (such as proving the Π11-hardness for Skeptc∞o ). Next, we aim at
investigating whether the computational problems considered in this paper become more tractable if we
restrict to special classes of AFs, such as the finitary ones (i.e., those in which each argument receives
ifnitely many attacks only [
Andrews was partially supported by NSF grant DMS-2348792. San Mauro is a member of INDAMGNSAGA.