Introduction

Abstract argumentation theory is a fundamental research area in AI, providing a powerful paradigm for reasoning about knowledge representation and multi-agent systems. Historically, the focus has predominantly been on finite argumentation frameworks (AFs), leaving the infinite case relatively unexplored. As noted in [1], this oversight poses significant theoretical, conceptual, and practical limitations.

Firstly, infinite frameworks align naturally with Dung's seminal approach [2], whose results do not presuppose finiteness. Secondly, representing argumentation scenarios in an infinite manner captures the inherently nonmonotonic nature of argumentation, where arguments can always be challenged by the emergence of new information, making any fixed limit on the space of arguments somewhat artificial. Moreover, if one conceives an argumentative scenario with arguments being added as time proceeds, e.g., the collection of scientific studies, then infinite frameworks naturally emerge as the union of the argumentation frameworks that we see at each finite time. Thirdly, infinite AFs may arise in practical contexts, such as logic programming [3] and the logical analysis of multi-agent or distributed systems [4] (the substantial introduction of [1] provides other concrete examples of applications of infinite AFs, e.g., to multiagent negotiations).

Fortunately, recent years have seen a growing interest in infinite AFs, with special focus on how the existence and interplay of various semantics-well-understood for finite AFs-are affected in the infinite realm (see, e.g., [5,6,7,8,9]). This increasing recognition underscores the importance of infinite AFs for a broad understanding of argumentation theory.

However, the literature still lacks a comprehensive framework for systematically exploring all logical aspects of infinite AFs, particularly regarding their core computational issues. A significant research 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., [10,11,12]). To our knowledge, no analogous study has been conducted for infinite AFs.

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 out-side 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., [13,14,15]).

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. Finally, in Sections 4 through 5, we determine the lower and upper bounds of the complexity for our computational problems: a critical technique for achieving hardness results involves suitably encoding trees into AFs. Our main results are collected in Tables 2 and 3.

Argumentation theoretic background

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 [16,17] offer an overview of these topics).

An argumentation framework (AF) ℱ is a pair (𝐴ℱ , 𝑅ℱ ) consisting of a set 𝐴ℱ of arguments and an attack relation 𝑅ℱ ⊆ 𝐴ℱ × 𝐴ℱ . If some argument 𝑎 attacks some argument 𝑏, we may write 𝑎 ↣ 𝑏 instead of (𝑎, 𝑏) ∈ 𝑅ℱ . Collections of arguments 𝑆 ⊆ 𝐴ℱ are called extensions. For an extension 𝑆, the symbols 𝑆 + and 𝑆 − denote, respectively, the arguments that 𝑆 attacks and the arguments that attack 𝑆:

𝑆 + = {𝑥 : (∃𝑦 ∈ 𝑆)(𝑦 ↣ 𝑥)}; 𝑆 − = {𝑥 : (∃𝑦 ∈ 𝑆)(𝑥 ↣ 𝑦)}.

𝑆 defends an argument 𝑎, if any argument that attacks 𝑎 is attacked by some argument in 𝑆 (i.e., {𝑎} − ⊆ 𝑆 + ). The characteristic function of ℱ is the following mapping 𝑓ℱ which sends subsets of 𝐴ℱ to subsets of 𝐴ℱ : 𝑓ℱ (𝑆) := {𝑥 : 𝑥 is defended by 𝑆}.

All AFs investigated in this paper are infinite.

A semantics 𝜎 assigns to every AF ℱ a set of extensions 𝜎(ℱ) which are deemed as acceptable. A huge number of semantics, fueled by different 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 ℱ = (𝐴ℱ , 𝑅ℱ ) be an AF. Denote by cf(ℱ) the collection of extensions of ℱ which are conflict-free (i.e., 𝑆 ∈ cf(ℱ) iff 𝑎 ̸ ↣ 𝑏, for all 𝑎, 𝑏 ∈ 𝑆). Then, for 𝑆 ∈ cf(ℱ),

• 𝑆 ∈ ad(ℱ) iff 𝑆 is self-defending (i.e., 𝑆 ⊆ 𝑓ℱ (𝑆)); • 𝑆 ∈ co(ℱ) iff 𝑆 is a fixed point of 𝑓𝐹 (i.e., 𝑆 = 𝑓ℱ (𝑆)); • 𝑆 ∈ stb(ℱ), iff 𝑆 attacks all arguments outside

of it (i.e., 𝑆 + = 𝐴ℱ ∖ 𝑆).

In discussing the complete extensions, we will also briefly mention the grounded extension, which is the unique smallest fixed point of 𝑓𝐹 ; in any AF, the grounded extension always exists [2, Theorem 3].

For a given semantics 𝜎, the following are some wellknown computational problems related to 𝜎:

• Cred𝜎 (for credulous acceptance) is the decision problem whose accepting instances are the pairs (ℱ, 𝑎) so that 𝑎 ∈ 𝑆 for some 𝑆 ∈ 𝜎(ℱ); • Skept 𝜎 (for skeptical acceptance) is the decision problem whose accepting instances are the pairs (ℱ, 𝑎) so that 𝑎 ∈ 𝑆 for all 𝑆 ∈ 𝜎(ℱ); • Exist𝜎 is the decision problem whose accepting instances are the AFs ℱ so that 𝜎(ℱ) ̸ = ∅; • NE𝜎 is the decision problem whose instances are the AFs ℱ so that 𝜎(ℱ) ∖ {∅} ̸ = ∅; • Uni𝜎 is the decision problem whose accepting instances are the AFs ℱ so that |𝜎(ℱ)| = 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 [17]. Table 1 collects known complexity results for the admissible, stable, and complete semantics. This analysis refers only to finite AFs. In the next section, we introduce our computability theoretic perspective that allows us to tackle complexity issues concerning infinite AFs. Table 1 Computational problems for finite AFs. 𝒞-c denotes completeness for the class 𝒞.

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 [18]. We begin by establishing standard notation and terminology for some combinatorial notions that appear frequently in our proofs.

Sequences, strings, and trees

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 infinite sequences of numbers (where the 𝑖+1th bit of 𝜋 ∈ 𝜔 𝜔 will be the output of the function 𝜋 on input 𝑖). We denote by 0 ∞ the infinite sequence consisting of only 0's (or, equivalently, the constant function to 0). The restriction of an infinite sequence 𝜋 ∈ 𝜔 𝜔 to its first 𝑛 bits is denoted by 𝜋 ↾𝑛.

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 𝜎 = 𝜋 ↾𝑛 for some 𝑛, 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 𝑝 : 𝜔 × 𝜔 → 𝜔 to be a computable bijection. We adopt the common habit of denoting 𝑝(𝑥, 𝑦) by ⟨𝑥, 𝑦⟩.

The encodings discussed in Section 4 heavily rely on the difficulty of calculating paths through trees. As is common in computability theory, we say that a tree is a set 𝒯 ⊆ 𝜔 <𝜔 closed under prefixes. We picture trees growing upwards, with 𝜎 ⌢ 𝑖 to the left of 𝜎 ⌢ 𝑗, when-ever 𝑖 < 𝑗. A path 𝜋 ∈ 𝜔 𝜔 through a tree 𝒯 ⊆ 𝜔 <𝜔 is an infinite sequence so that 𝜋 ↾𝑛 ∈ 𝒯 , for all numbers 𝑛. The set of paths through a tree 𝒯 is denoted by [𝒯 ]. 𝒯 is well-founded if [𝒯 ] = ∅ and otherwise is illfounded. 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

𝒯 := {𝜆} ∪ {𝜎, 𝜎 ⌢ 1 : (∀𝑛 < |𝜎|)(𝜎(𝑛) = 0)} is an ill-founded tree with [𝒯 ] = {0 ∞ }.

If 𝒯 contains strings of arbitrary length, then 𝒯 has infinite height. Note that there are trees of infinite height which are well-founded, e.g., 𝒯 = {𝜆} ∪ {𝑛 ⌢ 𝜎 : |𝜎| ≤ 𝑛}.

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 offers 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 (Φ𝑒)𝑒∈𝜔 be a uniform enumeration of all partial computable functions from 𝜔 to {0, 1}.

Definition 3.1.

A number 𝑒 is a computable index for an AF ℱ = (𝐴ℱ , 𝑅ℱ ) with 𝐴ℱ = {𝑎𝑛 : 𝑛 ∈ 𝜔} so that

Φ𝑒(⟨𝑛, 𝑚⟩) = {︃ 1 if 𝑎𝑛 ↣ 𝑎𝑚 0 otherwise. An AF ℱ is computable, if it has a computable index 𝑒 ∈ 𝜔.

We use the notation ℱ𝑒 to refer to the AF with computable index 𝑒 (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 𝑒 for a non-total computable function Φ𝑒 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 ∞ 𝜎 := {⟨𝑒, 𝑛⟩ : (∃𝑆 ∈ 𝜎(ℱ𝑒))(𝑎𝑛 ∈ 𝑆)}; 2. Skept ∞ 𝜎 := {⟨𝑒, 𝑛⟩ : (∀𝑆 ∈ 𝜎(ℱ𝑒))(𝑎𝑛 ∈ 𝑆)}; 3. Exist ∞ 𝜎 := {𝑒 : (∃𝑆 ⊆ 𝐴ℱ 𝑒 ))(𝑆 ∈ 𝜎(ℱ𝑒))}; 4. NE ∞ 𝜎 := {𝑒 : (∃𝑆 ∈ 𝜎(ℱ𝑒))(𝑆 ̸ = ∅)}; 5. Uni ∞ 𝜎 := {𝑒 : (∃!𝑆 ⊆ 𝐴ℱ 𝑒 )(𝑆 ∈ 𝜎(ℱ𝑒))}.

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. 𝑆 ∈ infad(ℱ) if and only if 𝑆 ∈ ad(ℱ) and 𝑆 is infinite; 2. 𝑆 ∈ infco(ℱ) if and only if 𝑆 ∈ co(ℱ) and 𝑆 is infinite; 3. 𝑆 ∈ infstb(ℱ) if and only if 𝑆 ∈ stb(ℱ) and 𝑆 is infinite.

As an illustration of why we might want to accept only infinite extensions, we consider that a given infinite AF may contain a single argument 𝑏 so that 𝑏 attacks every other argument, and every other argument attacks 𝑏. We imagine that 𝑏 is a statement of extreme solipsism denying the truth of any other statement. While {𝑏} is a stable extension, it represents a negligible fraction of arguments, and we may prefer not to accept it. In an infinite AF, any finite set is as negligible as {𝑏}, so we may prefer to accept only infinite extensions.

The complexity classes that most naturally match the problems of Definition 3.3 are those of the Σ 1 1 and Π 1 1 sets. The Σ 1 1 sets are formally defined as those subsets of 𝜔 that are definable in the language of 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] Note that the definition of 𝑆 + and 𝑆 − use only quantifiers over arguments. Thus the definition of 𝑓ℱ (𝑆) given by 𝑎 ∈ 𝑓ℱ (𝑆) if and only if {𝑎} − ⊆ 𝑆 + uses only quantifiers over arguments. Finally, 𝑆 ∈ ad(ℱ), 𝑆 ∈ stb(ℱ), 𝑆 ∈ co(ℱ) are all defined from 𝑓ℱ (𝑆) and 𝑆 + using only quantifiers over arguments.

In the case of 𝜎 ∈ {infad, infstb, infco}, we need to also observe that 𝑆 being infinite is defined via ∀𝑛∃𝑚(𝑎𝑚 ∈ 𝑆 ∧ 𝑚 > 𝑛), which uses only quantifiers over numbers.

Proposition 3.5. Skept ∞ 𝜎 is Π 1 1 , whenever 𝜎 is in {ad, stb, co, infad, infstb, infco}. Furthermore, for 𝜎 ∈ {ad, co}, Uni ∞ 𝜎 is Π 1 1 .

Proof. The definition of Skept ∞ 𝜎 in Definition 3.3 uses a single universal set-quantifier followed by only number quantifiers in the definition of 𝜎(ℱ𝑒).

For 𝜎 ∈ {ad, co}, 𝑒 ∈ Uni ∞ 𝜎 if and only if there are not two different 𝜎 extensions (as there is always at least one 𝜎 extension). This is defined by the negation of the following formula:

(∃𝑆1∃𝑆2)(∃𝑥 ∈ 𝑆1∖𝑆2 ∧ 𝑆1 ∈ 𝜎(ℱ𝑒) ∧ 𝑆2 ∈ 𝜎(ℱ𝑒)).

Note that ∃𝑆1∃𝑆2 can be replaced by a single existential quantifier by encoding the pair (𝑆1, 𝑆2) as a single set {⟨1, 𝑥⟩ : 𝑥 ∈ 𝑆1} ∪ {⟨2, 𝑦⟩ : 𝑦 ∈ 𝑆2}. This shows that Uni ∞ 𝜎 is the complement of a Σ 1 1 set, thus is Π 1 1 .

Remark 3.6. The above argument does not suffice to show that Uni ∞ stb is also Π 1 1 , 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 Σ 1 1 and a Π 1 1 condition, i.e., a so-called d-Σ 1 1 definition. This is analogous to the fact that in the finite case Uni stb is DPcomplete. Similarly, the argument above does not show that Uni

∞ 𝜎 is Π 1 1 for 𝜎 ∈ {infad, infstb, infco}. Yet, it is true that Uni ∞ 𝜎 is Π 1 1 for 𝜎 ∈ {stb, infad, infstb

, infco} as we show below in Corollaries 5.5,5.10, and 5.14.

We note that knowing that a problem is Σ 1 1 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 Cred cf := {⟨𝑒, 𝑛⟩ :

(∃𝑆 ∈ cf(ℱ𝑒))(𝑎𝑛 ∈ 𝑆)}.

Though the given definition is Σ 1 1 , to know if an argument 𝑎𝑛 belongs to a conflict-free extension of ℱ𝑒, it suffices to check whether 𝑎𝑛 is non-self-defeating, i.e., 𝑎𝑛 ̸ ↣ 𝑎𝑛, which is equivalent to checking the computable fact that Φ𝑒(⟨𝑛, 𝑛⟩) = 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 offers a natural way of representing Σ 1 1 sets:

Theorem 3.7 (Kleene [19]). A set 𝑋 ⊆ 𝜔 is Σ 1 1 if and only if there is a computable sequence of computable trees (𝒯 𝑋 𝑛 )𝑛∈𝜔 so that 𝑛 ∈ 𝑋 iff 𝒯 𝑋 𝑛 is ill-founded.

We call (𝒯 𝑋 𝑛 )𝑛∈𝜔 a tree-sequence for 𝑋. 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 Σ 1 1 (resp., Π 1 1 ) problem.

Theorem 3.7 gives a reason to consider the Σ 1 1 sets as the natural infinite analogs of the NP problems. Namely, given an ill-founded computable tree 𝒯 and a sequence 𝜋 which is a path through 𝒯 , it is relatively simple to check that 𝜋 ∈ [𝒯 ] (it requires checking infinitely many simple facts: 𝜋 ↾𝑛 ∈ 𝒯 , for each 𝑛), but finding a sequence 𝜋 ∈ [𝑇 ]-or even knowing whether there exists a sequence 𝜋 ∈ [𝑇 ]-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., Γ ∈ {Σ 1 1 , Π 1 1 }). A set 𝑉 ⊆ 𝜔 is Γ-hard, if for every 𝑋 ∈ Γ there is a computable function 𝑓 : 𝜔 → 𝜔 so that 𝑥 ∈ 𝑋 if and only if 𝑓 (𝑥) ∈ 𝑉 . If 𝑉 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 Σ 1 1complete set. Similarly, the set of indices for well-founded computable trees is a Π 1 1 -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 Π 1 1complete set.

Remark 3.11. The hardness in Theorem 3.10 is quite easy. We can reduce the question of whether a tree 𝒯 is well-founded to whether a tree 𝒯 ′ has two paths, where 𝒯 ′ always has at least one path, by simply giving 𝒯 ′ one more path than 𝒯 (e.g. 𝒯 ′ = {1 ⌢ 𝜎 : 𝜎 ∈ 𝒯 } ∪ {𝜎 : (∀𝑛 < |𝜎|)𝜎(𝑛) = 0}). The fact that UB is itself Π 1 1 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 Σ 1 1 (or Π 1 1 ) set 𝑋, we translate the question asking whether 𝑛 ∈ 𝑋 to the question of if the tree 𝒯 𝑋 𝑛 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 𝒯 𝑋 𝑛 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.

Table 2 collects our results regarding complexities of the computational problems examined for computable argumentation frameworks. Remark 3.12. As noted before, the Σ 1 1 sets are natural analogs in the infinitary setting of the NP sets, and the Π 1 1 sets are the natural analogs of the coNP sets. With the exception of Skept ∞ co and Uni ∞ stb , Table 2 follows this translation from Table 1 for the first three rows. These two results mark surprising differences 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.

Spectra of 𝜎 extensions

We propose a way to more fully understand the complexity of the problem of finding a 𝜎 extension in a given AF ℱ. Definition 3.13. For each 𝑒 ∈ 𝜔 and semantics 𝜎, let Spec ¬∅ 𝜎 (ℱ𝑒) be the set of Turing degrees of non-empty sets 𝑋 ⊆ 𝜔 so that {𝑎𝑛 : 𝑛 ∈ 𝑋} is a 𝜎 extension in ℱ𝑒.

The notion Spec ¬∅ 𝜎 (ℱ𝑒) exactly captures the difficulty of computing a non-empty 𝜎 extension in ℱ𝑒. We will be relating the problem of computing a 𝜎 extension in ℱ𝑒 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 𝒯 , we let Spec(𝒯 ) be set of Turing degrees of paths 𝑋 ∈ [𝒯 ].

Table 3 collects our results on spectra of extensions.

𝜎 Cred ∞ 𝜎 Skept ∞ 𝜎 Exists ∞ 𝜎 NE ∞ 𝜎 Uni ∞ 𝜎 ad Σ 1 1 -c 4.2,3.4 trivial trivial Σ 1 1 -c 4.2 3.4 Π 1 1 -c 4.3,3.5 stb Σ 1 1 -c 4.2,3.4 Π 1 1 -c 4.4,3.5 Σ 1 1 -c 4.2, 3.4 Σ 1 1 -c 4.2,3.4 Π 1 1 -c 4.3, 5.10 co Σ 1 1 -c 4.2, 3.4 Π 1 1 -c *, 3.5 trivial Σ 1 1 -c 4.2, 3.4 Π 1 1 -c 4.3,3.5 infad Σ 1 1 -c 4.2,3.4 Π 1 1 -c 4.4,3.5 Σ 1 1 -c 4.2, 3.4 Σ 1 1 -c 4.2, 3.4 Π 1 1 -c 4.3,5.5 infstb Σ 1 1 -c 4.2,3.4 Π 1 1 -c 4.4,3.5 Σ 1 1 -c 4.2, 3.4 Σ 1 1 -c 4.2, 3.4 Π 1 1 -c 4.3,5.10 infco Σ 1 1 -c 4.2,3.4 Π 1 1 -c 4.4,3.5 Σ 1 1 -c 4.2, 3.4 Σ 1 1 -c 4.2, 3.4 Π1

1 -c 4.3, 5.14 Table 2 Computational problems for computable AFs. 𝒞-c denotes completeness for the class 𝒞. The entry with an asterisk is not fully proved in this paper. Rather, the Π 1 1 -hardness for Skept ∞ co is deferred to future work focusing on the grounded semantics. It is included in the table here (though partially unproved) to give a more complete picture. The numbers in each cell of the table refer to the Theorem number providing the lower bound and upper bounds for the result in that cell.

𝜎

Table 3

For any computable tree 𝒯 , there is a computable argumentation framework ℱ𝑒 so that Spec(𝒯 ) = Spec ¬∅ 𝜎 (ℱ𝑒). When 𝜎 ∈ {ad, stb, infad, infstb}, the converse also holds. Namely, for every 𝑒, there is a computable tree so that Spec ¬∅ 𝜎 (ℱ𝑒) = Spec(𝒯 ). We do not know how to attain a corresponding upper bound for the complete or infinite complete cases.

Encoding a tree into an argumentation framework

Given a tree 𝒯 ⊆ 𝜔 <𝜔 , we will define an argumentation framework ℱ 𝒯 = (𝐴 𝒯 , 𝑅 𝒯 ). The set of arguments 𝐴 𝒯 of ℱ 𝒯 is computable and consists of {𝑎𝜎 : 𝜎 ∈ 𝒯 }∪{𝑏𝜎 : 𝜎 ∈ 𝒯 } ∪ {𝑐}. The attack relation 𝑅 𝒯 of ℱ 𝒯 contains all and only the following edges:

For all 𝜎 ∈ 𝒯 , 1. 𝑏𝜎 ↣ 𝑏𝜎;

2. 𝑏𝜎 ↣ 𝑎𝜎;

3. 𝑎𝜎 ↣ 𝑏𝜏 , if |𝜎| = |𝜏 | + 1; 4. 𝑎𝜎 ↣ 𝑎𝜏 , if |𝜎| = |𝜏 | + 1 and 𝜏 ̸ ⪯ 𝜎;

5. 𝑐 ↣ 𝑎𝜏 for every 𝜏 ∈ 𝒯 ;

6. 𝑎 𝜆 ↣ 𝑐. Figure 1 gives an example of our encoding for a finite tree. We next consider which extensions in ℱ 𝒯 are admissible, stable, or complete.

Notation. For 𝜋 ∈ [𝒯 ], let 𝑆𝜋 be the set {𝑎𝜎 : 𝜎 ≺ 𝜋}.

Lemma 4.1. A non-empty extension𝑆 of ℱ 𝒯 is stable iff 𝑆 is complete iff 𝑆 is admissible iff 𝑆 is exactly 𝑆𝜋 for some 𝜋 ∈ [𝒯 ].

Proof. Stable always implies complete, which always implies admissible. It is straightforward to check that 𝑆𝜋 is stable for any 𝜋 ∈ [𝒯 ], so we need only show that any non-empty admissible extension is exactly some 𝑆𝜋. Suppose that 𝑆 is admissible. Observe that 𝑐 and 𝑏𝜎 cannot be in 𝑆 since these are self-defeating. So some 𝑎𝜎 ∈ 𝑆 since 𝑆 is non-empty. Note that since 𝑐 ↣ 𝑎𝜎, we must have 𝑎 𝜆 ∈ 𝑆. Next, observe that if 𝑎𝜏 ∈ 𝑆, then there must be some 𝑖 so that 𝑎𝜏⌢𝑖 ∈ 𝑆: this is because some element of 𝑆 must defend 𝑎𝜏 from 𝑏𝜏 and such an element must be an 𝑎𝜎 with |𝜎| = |𝜏 | + 1. But it must have 𝜏 ≺ 𝜎 as otherwise 𝑎𝜎 would attack 𝑎𝜏 . It follows that 𝑆 contains 𝑆𝜋 for some 𝜋 ∈ [𝒯 ]. Since 𝑆𝜋 is stable, 𝑆 cannot properly contain 𝑆𝜋, so 𝑆 = 𝑆𝜋.

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:

1. for 𝜎 ∈ {ad, stb, co, infad, infstb, infco}, NE ∞ 𝜎 is Σ 1 1 -hard; 2. for 𝜎 ∈ {stb, infad, infstb, infco}, Exist ∞ 𝜎 is Σ 1 1 - hard; 3. for 𝜎 ∈ {ad, stb, co, infad, infstb, infco}, Cred ∞ 𝜎 is Σ 1 1 -hard.

Proof. 1. Let 𝑋 ∈ Σ 1 1 and let (𝒯 𝑋 𝑛 )𝑛∈𝜔 be a treesequence for 𝑋, as given by Theorem 3.7. To show Σ Theorem 4.5. For 𝜎 ∈ {ad, stb, co, infad, infstb, infco} and for any computable tree 𝒯 , there exists a computable AF ℱ𝑒 so that Spec ¬∅ 𝜎 (ℱ𝑒) = Spec(𝒯 ).

Proof. Observe that for the AF ℱ𝑒 = ℱ 𝒯 , 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 𝒯 .

Trees coding extensions in 𝜎(ℱ)

In this section, we give upper bounds to the complexity of Spec ¬∅ 𝜎 for 𝜎 ∈ {ad, stb, infad, infstb} as well as giving upper bounds for the complexity of Uni ∞ 𝜎 for any 𝜎 ∈ {stb, infad, infstb, infco}. We do this by describing how to computably encode the collection of extensions in 𝜎(ℱ) into the set of paths through a tree.

The admissible case

Given a computable argumentation framework ℱ, we will describe a computable tree 𝒯 ℱ so that the paths of 𝒯 ℱ encode the non-empty admissible extensions in ℱ. We begin with an intuitive description of how a path 𝜋 through the tree 𝒯 ℱ will encode an admissible extension 𝑆, and we give the formal definition of 𝒯 ℱ below.

Branching in 𝒯 ℱ will come in three flavors. The first branching is used to give the least element of the admissible extension 𝑆. This is to ensure that the extension is non-empty. If we wished to allow the empty extension, we could omit this branching. For any 𝑗 > 0, the branching on level 2𝑗 serves to code whether or not 𝑗 ∈ 𝑆. Branching on the odd levels serve to explain how 𝑆 satisfies the hypothesis of being an admissible extension. If 𝑎𝑖 ↣ 𝑎𝑗 is the 𝑛th element of some computable enumeration of all attacking pairs of arguments, then 𝜎(2𝑛 + 1) will be 0 if 𝑎𝑗 / ∈ 𝑆 and otherwise will be 𝑘 + 1 where 𝑘 is least so that 𝑎 𝑘 ∈ 𝑆 and 𝑎 𝑘 ↣ 𝑎𝑖.

Let ℱ = (𝐴ℱ , 𝑅ℱ ) be a computable AF. Let (𝑔𝑛)𝑛∈𝜔 be a computable sequence of all elements of 𝑅ℱ . If 𝑔𝑛 = (𝑎𝑖, 𝑎𝑗), we denote 𝑎𝑖 by 𝑔 − 𝑛 and 𝑎𝑗 by 𝑔 + 𝑛 . We now define the tree 𝒯 ℱ . Definition 5.1. Any given string 𝜎 ∈ 𝜔 <𝜔 defines two subsets of arguments in 𝐴ℱ :

• In𝜎 = {𝑎 𝜎(0) }∪{𝑎𝑗 : 𝑗 > 0∧𝜎(2𝑗) = 1}∪{𝑎 𝑘 : (∃𝑗)(𝜎(2𝑗 + 1) = 𝑘 + 1)} ∪ {𝑎𝑖 : (∃𝑗)(𝜎(2𝑗 + 1) > 0 ∧ 𝑔 + 𝑗 = 𝑎𝑖)}; • Out𝜎 = {𝑎𝑖 : 𝑖 < 𝜎(0)}∪{𝑎𝑗 : 𝑗 > 0∧𝜎(2𝑗) = 0}∪{𝑎𝑖 : (∃𝑗)(𝜎(2𝑗+1) = 0∧𝑔 + 𝑗 = 𝑎𝑖)}∪{𝑎𝑖 : (∃𝑗)(𝜎(2𝑗 + 1) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑔 − 𝑗 )}.

We define 𝒯 ℱ as the set of 𝜎 so that

• In𝜎 is conflict-free; • In𝜎 ∩ Out𝜎 = ∅ • If 0 < 2𝑗 < |𝜎|, then 𝜎(2𝑗) ∈ {0, 1}; • If 2𝑗 + 1 < |𝜎| and 𝜎(2𝑗 + 1) = 𝑘 + 1, then 𝑎 𝑘 ↣ 𝑔 − 𝑗 .

Theorem 5.2. Let ℱ be a (computable) argumentation framework. Then the non-empty admissible extensions of ℱ are in (computable) bijection with the paths in 𝒯 ℱ .

Proof. Given a non-empty admissible extension 𝑆 of ℱ, we define the corresponding path 𝜋 in 𝒯 ℱ as follows. Let 𝜋(0) be the least element of 𝑆. For 𝑗 > 0, let 𝜋(2𝑗) = 1 if 𝑎𝑗 ∈ 𝑆 and 𝜋(2𝑗) = 0 otherwise. Let 𝜋(2𝑛 + 1) be 0 if 𝑔 + 𝑛 / ∈ 𝑆 and be 𝑘 + 1 where 𝑘 is least so that 𝑎 𝑘 ∈ 𝑆 and

𝑎 𝑘 ↣ 𝑔 − 𝑛 otherwise. It is straightforward to check that 𝜋 ∈ [𝒯 ℱ ].

Given a path 𝜋 through 𝒯 ℱ , first note that whenever there is some 𝜎 ≺ 𝜋 so that 𝑎𝑛 ∈ In𝜎, then 𝜋(2𝑛) = 1. This is because whenever 𝜎 ⪯ 𝜏 , then In𝜎 ⊆ In𝜏 . Then since

𝜏 := 𝜋 ↾ max(|𝜎|,2𝑛+1) is in 𝒯 ℱ , we cannot have 𝜏 (2𝑛) = 0 since 𝑎𝑛 ∈ In𝜏 . Thus 𝜋(2𝑛) = 𝜏 (2𝑛) = 1. It follows that ⋃︀ 𝜎≺𝜋 In𝜎 = {𝑎𝑛 : 𝜋(2𝑛) = 1}. The same argument shows that ⋃︀ 𝜎≺𝜋 Out𝜎 = {𝑎𝑛 : 𝜋(2𝑛) = 0}. Let 𝑆 = {𝑎𝑛 : 𝜋(2𝑛) = 1}.

Note that 𝑆 is conflict-free, since if 𝑎𝑖, 𝑎𝑗 ∈ 𝑆 then there is some long enough 𝜎 ≺ 𝜋 so that 𝑎𝑖, 𝑎𝑗 ∈ In𝜎.

Since 𝜎 ∈ 𝒯 ℱ , it follows that In𝜎 is conflict-free, so 𝑎𝑖 ̸ ↣ 𝑎𝑗. Next, observe that 𝑆 defends itself. If 𝑎𝑖 ↣ 𝑎𝑗 and 𝑎𝑗 ∈ 𝑆, then there is some 𝑛 so that 𝑔𝑛 = (𝑎𝑖, 𝑎𝑗). Then consider 𝜎 = 𝜋 ↾𝑛+1. We must have 𝜎(𝑛) = 𝑘 + 1 for some 𝑘 with 𝑎 𝑘 ∈ 𝑆 and 𝑎 𝑘 ↣ 𝑎𝑖.

Finally, note that both the map from 𝜋 to 𝑆 and from 𝑆 to 𝜋 are computable if ℱ is computable and are inverses of each other.

Corollary 5.3. For every computable AF ℱ𝑒, there exists a computable tree 𝒯 so that Spec ¬∅ ad (ℱ𝑒) = Spec(𝒯 ).

Proof. It follows immediately from Theorem 5.2 that Spec ¬∅ ad (ℱ𝑒) = Spec(𝒯 ℱ𝑒 ).

Corollary 5.4. For every computable AF ℱ𝑒, there exists a computable tree ̂︀ 𝒯 so that Spec ¬∅ infad (ℱ𝑒) = Spec( ̂︀ 𝒯 ).

Proof. The tree needed here is a slight alteration of the tree 𝒯 ℱ . In 𝒯 ℱ , we made 𝜎(0) tell us the least 𝑘 so 𝑎 𝑘 ∈ 𝑆 so as to ensure that 𝑆 ̸ = ∅. We do the same on infinitely many layers, e.g., instead of having 𝜎(2𝑛) be 0 or 1 to tell us whether or not 𝑛 ∈ 𝑆, we have 𝜎(2𝑛) tell us the 𝑛th least number 𝑘 so that 𝑎 𝑘 ∈ 𝑆. With the tree altered like this, paths are in computable bijection with the infinite admissible extensions.

Corollary 5.5. Uni ∞ infad is Π 1 1 .

Proof. 𝑒 is in Uni infad if and only if the tree ̂︀ 𝒯 in Corollary 5.4 has a unique path. By Theorem 3.10, this is a Π 1 1 condition.

The stable case

Similarly, we can construct a tree encoding the stable extensions by making 𝜎(𝑛) = 0 if 𝑎𝑛 ∈ 𝑆 and otherwise making 𝜎(𝑛) be 𝑘 + 1 where 𝑘 is least so that 𝑎 𝑘 ∈ 𝑆 and 𝑎 𝑘 ↣ 𝑎𝑛. Definition 5.6. Any given string 𝜎 ∈ 𝜔 <𝜔 defines two subsets of arguments in 𝐴ℱ :

• In𝜎 = {𝑎𝑖 : 𝜎(𝑖) = 0} ∪ {𝑎 𝜎(𝑖)−1 : 𝑖 < |𝜎| ∧ 𝜎(𝑖) > 0}; • Out𝜎 = {𝑎𝑖 : 𝑖 < |𝜎| ∧ 𝜎(𝑖) > 0} ∪ {𝑎𝑖 : (∃𝑗)𝜎(𝑗) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑎𝑗)}.

We define 𝒯 ℱ as the set of 𝜎 so that Given a path 𝜋 through 𝒯 ℱ , first note that whenever there is some 𝜎 ≺ 𝜋 so that 𝑎𝑛 ∈ In𝜎, then 𝜋(𝑛) = 0. This is because whenever 𝜎 ⪯ 𝜏 , then In𝜎 ⊆ In𝜏 . Then since 𝜏 = 𝜋 ↾ max(|𝜎|,𝑛+1) is on 𝒯 ℱ , we cannot have 𝜏 (𝑛) ̸ = 0 since 𝑎𝑛 ∈ In𝜏 and therefore cannot be in Out𝜏 . It follows that

• In𝜎 is conflict-free; • In𝜎 ∩ Out𝜎 = ∅ • If 𝑗 < |𝜎|⋃︀ 𝜎≺𝜋 In𝜎 = {𝑎𝑛 : 𝜋(𝑛) = 0}. Let 𝑆 = {𝑎𝑛 : 𝜋(𝑛) = 0}.

Note that 𝑆 is conflict-free, since if 𝑎𝑖, 𝑎𝑗 ∈ 𝑆, then 𝑎𝑖 ̸ ↣ 𝑎𝑗 since 𝜎 = 𝜋 ↾ max(𝑖,𝑗)+1 is in 𝒯 ℱ , and thus In𝜎 is conflict-free. Next observe that for any 𝑛, either 𝑎𝑛 ∈ 𝑆 or there is some 𝑚 so that 𝑎𝑚 ∈ 𝑆 and 𝑎𝑚 ↣ 𝑎𝑛. In particular, if 𝜋(𝑛) = 0, then 𝑎𝑛 ∈ 𝑆 and otherwise 𝑎 𝜋(𝑛)−1 ∈ 𝑆 and 𝑎 𝜋(𝑛)−1 ↣ 𝑎𝑛.

Finally, note that both the map from 𝜎 to 𝑆 and from 𝑆 to 𝜎 are computable if ℱ is computable and are inverses of each other.

Corollary 5.8. For any computable AF ℱ𝑒 there exists a computable tree 𝒯 so that Spec ¬∅ stb (ℱ𝑒) = Spec(𝒯 ).

Proof. This follows directly from Theorem 5.7 along with the fact that ∅ is never a stable extension.

Corollary 5.9. For any computable AF ℱ𝑒 there exists a computable tree 𝒯 so that Spec ¬∅ infstb (ℱ𝑒) = Spec(𝒯 ).

Proof. We add layers of branching to the tree as in Corollary 5.4 so that, e.g., 𝜎(2𝑛) = 𝑚 means that 𝑚 is the 𝑛th least number so that 𝑎𝑛 ∈ 𝑆. This produces a tree ̂︂ 𝒯 ℱ so that the paths are in computable bijection with the infinite stable extensions of ℱ.

The complete case

Given an argumentation framework ℱ, we can similarly construct a tree 𝒯 ℱ so that paths through 𝒯 ℱ code complete extensions. In order to ensure that 𝑓ℱ (𝑆) ⊆ 𝑆, we will need the paths in 𝒯 ℱ to not only code sets 𝑆 but also their attacked sets 𝑆 + . Given an extension 𝑆, we will let 𝜋 ∈ 𝒯 ℱ encode 𝑆 and 𝑆 + as follows:

• 𝜋(2𝑛) = 0 if 𝑎𝑛 ∈ 𝑆 and otherwise 𝜋(2𝑛) = 𝑘 + 1 where 𝑘 is least so 𝑎 𝑘 / ∈ 𝑆 + and 𝑎 𝑘 ↣ 𝑎𝑛. • 𝜋(2𝑛 + 1) = 0 if 𝑎𝑛 / ∈ 𝑆 + and otherwise 𝜋(2𝑛 + 1) = 𝑘 + 1 where 𝑘 is least so 𝑎 𝑘 ∈ 𝑆 and 𝑎 𝑘 ↣ 𝑎𝑛.

Note that 𝜋(2𝑛) explains why 𝑎𝑛 is either in 𝑆 or it is not in 𝑓ℱ (𝑆), i.e., 𝑓ℱ (𝑆) ⊆ 𝑆, while 𝜋(2𝑛 + 1) simply verifies that the elements which 𝜋 says are in 𝑆 + are in fact in 𝑆 + .

Formally, we define 𝒯 ℱ as follows:

Definition 5.11. Any given string 𝜎 ∈ 𝜔 <𝜔 defines four subsets of arguments in 𝐴ℱ :

• In𝜎 = {𝑎𝑖 : 𝜎(2𝑖) = 0} ∪ {𝑎 𝑘 : (∃𝑗)(𝜎(2𝑗 + 1) = 𝑘 + 1} • Out𝜎 = {𝑎𝑖 : 𝜎(2𝑖) ̸ = 0} ∪ {𝑎𝑖 : (∃𝑗)𝜎(2𝑗 + 1) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑎𝑗)} • InSplus 𝜎 = {𝑎𝑖 : (∃𝑗)(𝜎(2𝑗) > 𝑖 + 1 ∧ 𝑎𝑖 ↣ 𝑎𝑗)} ∪ {𝑎𝑖 : 𝜎(2𝑖 + 1) ̸ = 0} • OutSplus 𝜎 = {𝑎𝑖 : (∃𝑗)𝜎(2𝑗) = 𝑖 + 1} ∪ {𝑎𝑖 : 𝜎(2𝑖 + 1) = 0}

We define 𝒯 ℱ as the set of 𝜎 so that Proof. If 𝜎 ∈ {ad, stb, infad, infstb}, let 𝒯 be a tree so that Spec ¬∅ 𝜎 (ℱ𝑒) = Spec(𝒯 ). If 𝜎 ∈ {𝑐𝑜, infco}, let 𝒯 be a tree so that the set of Turing degrees of pairs (𝑆, 𝑆+) of 𝜎 extensions is exactly Spec(𝒯 ). Then 𝒯 is a computable tree with countably many paths. By a classic result of Kreisel [21, Theorem 3.9], 𝒯 has a hyperarithmetical path, which corresponds to a hyperarithmetical 𝑆 so that {𝑎𝑛 : 𝑛 ∈ 𝑆} is a 𝜎 extension of ℱ𝑒.

Conclusion

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 were found to be maximally complex, properly belonging to the complexity classes of Σ 1 1 and Π 1 1 sets. 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 Π 1 1 -hardness for Skept ∞ co ). 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 finitely many attacks only [7]). 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 definitions of these semantics are more intricate than those we examined here, we anticipate the need for additional techniques to thoroughly analyze them.