We consider infinite argumentation frameworks and computational problems relating to the admissible, stable, and complete semantics. We also consider the semantics demanding that extensions are infinite. We introduce computability theoretic machinery as a method of measuring the dificulty of these undecidable decision problems. For each of these semantics, we classify the complexity class of the problems of credulous and skeptical acceptance of arguments, and the existence and uniqueness of extensions. For all computational problems considered, we also build a single argumentation framework witnessing our hardness results: this means that solving these problems is not only hard for the class of all argumentation frameworks, but also is not easier for a single given argumentation framework. We also propose a way of using Turing degrees to classify, for a given infinite argumentation framework, the exact dificulty of computing an extension in a given semantics and show that these problems give rise to a rich class of complexities.
the union of the argumentation frameworks that we see
at each finite time. Thirdly, infinite AFs may arise in
Abstract argumentation theory is a fundamental research practical contexts, such as logic programming [
Firstly, infinite frameworks align naturally with ifnite AFs—are afected in the infinite realm (see, e.g.,
Dung’s seminal approach [
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.
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 6, 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 Table 2, and Theorems 3.15, 5.4.
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) ℱ 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., {}− ⊆ +).
35–47 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 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 ℱ = (ℱ , ℱ ) be an AF. Denote by cf(ℱ ) the collection of extensions of ℱ which are conflict-free (i.e., ∈ cf(ℱ ) if ↣̸ , for all , ∈ ). Then, for ∈ cf(ℱ ), • ∈ ad(ℱ ) if is self-defending (i.e., ⊆
ℱ ()); • ∈ co(ℱ ) if is a fixed point of (i.e., =
ℱ ()); • ∈ stb(ℱ ), if 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 [3, 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[
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 [
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 ≺ . a set ⊆ it will be convenient to encode pairs of numbers into single numbers. The pairing function does this. Fix : common habit of denoting (, ) by ⟨, ⟩. × → to be a computable bijection. We adopt the
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
< closed under prefixes. We picture trees growing upwards, with ⌢ to the left of ⌢, when
In order to formulate our problems as subsets of , infinitely many computable indices.). 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 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., = { } ∪ {⌢ : | | ≤
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. partial computable functions from to {0, 1}.
Notation. Let (Φ)∈ be a uniform enumeration of all Definition 3.1.
A number is a computable index for an AF ℱ = (ℱ , ℱ ) with ℱ = { : ∈ } so that Φ(⟨, ⟩) = {︃1 0 if ↣ 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
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∞ := { : (∃! ⊆ ℱ )( ∈ (ℱ))}.
For items 1. and 2. above, it’s also natural to consider their restrictions to a specific computable AF ℱ. That is, we define
Cred∞(ℱ) = { : ⟨, ⟩ ∈ Cred∞} Skept∞(ℱ) = { : ⟨, ⟩ ∈ Skept∞}. over subsets of followed by number quantifiers and the ifrst order functions and relations (+, · , <, 0, 1, ∈); for more details, see [19, §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∞ := {⟨, ⟩ ∈ : (∃ ∈ (ℱ)( ∈ ))} uses a single existential quantifier over sets . This is similarly true for the definitions of Exist∞ and NE∞ in Definition 3.3. Thus, it sufices to see that the condition ∈ (ℱ) can be deifned with only quantification over arguments, which are in bijection with , not needing quantification over sets of arguments.
Note that the definition of + and − use only quantiifers 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 quantiifers over numbers.
We note that in the finite setting, Cred (ℱ ) or Skept (ℱ ) for a finite AF ℱ , is simply a finite subset Proposition 3.5. Skept∞ is Π11, whenever is in soeflf.Iℱn,csoonsittradsote,sinntohte einnfinciotdeesemttuincgh, cComrepdl∞ex(iℱty)inanidt- {{aadd,, sctob},,cUo,niin∞faids, Πin11f.stb, infco}. Furthermore, for ∈ Skept∞(ℱ) are infinite subsets of , and it makes sense to ask about whether this set is decidable; and if not, to Proof. The definition of Skept∞ in Definition 3.3 uses a understand its complexity. In these definitions, we use single universal set-quantifier followed by only number the number in place of so that these sets are subsets quantifiers in the definition of (ℱ). of , thus amenable to computability-theoretic analyses, For ∈ {ad, co}, ∈ Uni∞ if and only if there are yet when working with a given AF ℱ , we often write the not two diferent extensions (as there is always at least argument in place of the number . one extension). This is defined by the negation of the
We also introduce new semantics which make sense following formula: only in the infinite setting. This is motivated by the idea (∃1∃2)(∃ ∈ 1∖2 ∧ 1 ∈ (ℱ) ∧ 2 ∈ (ℱ)). 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.
The complexity classes that most naturally match the problems of Definition 3.3 are those of the Σ11 and Π11 sets.
The Σ11 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
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 Σ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 DPcomplete. 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 below in Corollaries 6.5,6.10, and 6.14.
Theorem 3.7 (Kleene [
We note that knowing that a problem is Σ11 does not Remark 3.11. The hardness in Theorem 3.10 is quite necessarily mean the problem is complicated. This only easy. We can reduce the question of whether a tree is gives an upper-bound for its complexity. Sometimes, well-founded to whether a tree ′ has two paths, where a simpler definition is achievable. As an example, we ′ always has at least one path, by simply giving ′ one consider Credcf := {⟨, ⟩ : (∃ ∈ cf(ℱ))( ∈ )}. more path than (e.g. ′ = {1⌢ : ∈ } ∪ { : Though the given definition is Σ11, to know if an argu- (∀ < | |) () = 0}). The fact that UB is itself Π11 is ment belongs to a conflict-free extension of ℱ, it the subtle part of this example. sufices 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 ofers a natural way of representing Σ11 sets:
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 , 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.
We call ( )∈ a tree-sequence for . As a corollary Table 2 collects our results regarding complexities of of Kleene’s theorem, one obtains that the problem of the computational problems examined for computable deciding which computable trees in < are ill-founded argumentation frameworks. (or well-founded) is as hard as any other Σ11 (resp., Π1)
1 problem. Remark 3.12. As noted before, the Σ11 sets are natural
Theorem 3.7 gives a reason to consider the Σ11 sets as analogs in the infinitary setting of the NP sets, and the the natural infinite analogs of the NP problems. Namely, Π11 sets are the natural analogs of the coNP sets. With given an ill-founded computable tree and a sequence the exception of Skeptc∞o and Unis∞tb , Table 2 follows this which is a path through , it is relatively simple to check translation from Table 1 for the first three rows. These that ∈ [ ] (it requires checking infinitely many simple two results mark surprising diferences in the infinite facts: ↾ ∈ , for each ), but finding a sequence ∈ setting. [ ]—or even knowing whether there exists a sequence ∈ [ ]—is a far harder problem.
The trivial entries are due to the fact that ∅ is always an admissible extension and the grounded extension is always a complete extension.
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 ⊆ is Γ-hard, if for every ∈ Γ there is a computable function : → so that ∈ Definition 3.13. For each ∈ and semantics , let if and only if () ∈ . If is Γ-hard and belongs to Γ, Spec¬∅(ℱ) be the set of Turing degrees of non-empty sets then it is Γ-complete. ⊆ so that { : ∈ } is a extension in ℱ.
The following example is far less obvious, but will be useful below to examine Uni∞.
Proposition 3.9. It follows from Theorem 3.7 that the The notion Spec¬∅(ℱ) exactly captures the dificulty 1 set of indices for ill-founded computable trees is a Σ1- of computing a non-empty extension in ℱ. We will complete set. Similarly, the set of indices for well-founded be relating the problem of computing a extension in computable trees is a Π11-complete set. ℱ to the problem of finding a path through a particular tree. So, we define the analogous notion of the spectrum of a tree.
Theorem 3.10 ([21, Theorem 18.11]). The set UB of in
1 dices for computable trees with exactly one path is a Π1complete set.
Definition 3.14. Given any computable tree , we let Spec( ) be set of Turing degrees of paths ∈ [ ].
Our main result in this direction is the following:
We propose a way to more fully understand the complexity of the problem of finding a extension in a given AF ℱ . stb co infad infstb infco
Cred∞ 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 Π11-hardness for Skeptc∞o 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. stick to measure complexity of undecidable problems. in the hyperarithmetical hierarchy on how complicated Spec¬∅(ℱ) = Spec( ).
Theorem 3.15. For
∈ {ad, stb, co, infad, infstb, infco} and for any computable tree , there exists a computable
∈ {ad, stb, infad, infstb}, the converse holds: i.e., for every there is a computable tree so that
We will prove each part of the above theorem in Sections 4 (Theorem 4.5) and 6 (Corollaries 6.3,6.4,6.8,6.9).
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 yard
1 A set is hyperarithmetical if and only if it is both Σ1 and Π11. The hyperarithmetical degrees are particularly useful as a yardstick of complexity because a set is hyperarithmetical if and only if it is computed from a set which can be reached by (transfinitely) iterating the halting jump operator. Thus, the number of iterations of the halting jump needed to compute yields a useful yardstick for the complexity of . For more information about the hyperarithmetical hierarchy, see [19, §16.8].
Proposition 3.16. There is a computable argumentation framework ℱ 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 [19, 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
For all ∈ , 1. ↣ 2. ↣ 3. ↣ 4. ↣ ; ; continuum many extensions. On the other hand, if a computable argumentation framework has only countably many extensions, the picture is quite diferent.
The following theorem is Corollary 6.15 below.
Theorem 3.17. Let ∈ {ad, stb, co, infad, infstb, infco} and suppose that ℱ is a computable argumentation framework with only countably many non-empty extensions.
Then, there is a hyperarithmetical non-empty extension of ℱ.
On the other hand, we can show that there is no bound this extension might be.
Theorem 3.18. Let
all and only the following edges: Given a tree ⊆ <, we will define an argumentation framework ℱ = ( , ). The set of arguments of ℱ is computable and consists of { :
∈ }∪{ : ∈ } ∪ {}. The attack relation of ℱ contains , if | | = | | + 1; , if | | = | | + 1 and ̸⪯ ; resulting AF. When applied to trees of infinite height, [ ] will be encoded into the stable, complete, and admissible extensions of ℱ . For the example shown in the figure, the only admissible extension of ℱ is the empty one, since [ ] = ∅. { , 0, 1, 10, 11}, the right-side is the stable for any
∈ [ ], so we need only show that any non-empty admissible extension is exactly some . Sup- ∈ {ad, stb, co, infad, infstb, infco}. ment must be an with | | = | | + 1. But it must have ≺ as otherwise would attack . It follows that for ℱ shows that Cred∞ is Σ11-hard. Thus sending to ⟨, ⟩ where is a computable index 10 0 11 1 11 1 1. for
∈ {ad, stb, co, infad, infstb, infco}, NE∞ is Σ11-hard; 2. for
hard; 3. for is Σ11-hard.
1 ∈ {stb, infad, infstb, infco}, Exist∞ is Σ1∈ {ad, stb, co, infad, infstb, infco}, Cred∞ Proof. 1. Let ∈ Σ11 and let ( )∈ be a tree
1 sequence for , as given by Theorem 3.7. To show Σ1hardness, we need to produce a computable function so that ∈ if and only if () ∈ NE∞. We let
() be a computable index for ℱ . Then Lemma 4.1 shows that ∈ if and only if is ill-founded if and only if ℱ has a non-empty extension for each
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
to NE∞ by sending to ℱ . Note that ℱ has a nonempty extension if and only if is in some extension.
Uni∞ is Π11-hard.
Theorem 4.3. For ∈ {ad, stb, co, infad, infstb, infco}, Proof.
We first consider let (
∖ )∈ be a tree-sequence for its complement.
Consider the sequence of AFs (ℱ
)∈. Note that ∖ ∈ {ad, co}. Let ∈ Π11 and 5. ↣ 6. ↣
.
for every ∈ ; must be some so that ⌢ ∈ : this is because some element of must defend from and such an ele∈ . Next, observe that if ∈ , then there
∈ contains for some cannot properly contain , so = .
∈ [ ]. Since is stable,
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: 10 0
35–47 Skeptc∞o is Π11-hard, and we will also consider the complexity of Skeptc∞o (ℱ) for a single computable AF ℱ.
In the previous section, we built AFs ℱ specifically to code a single Σ11-question into a single question about Creda∞d (ℱ ) codes multiple Σ11 questions. extensions in ℱ , e.g., is ill-founded if and only if
∈ Creda∞d (ℱ ). We will use the following notion of a disjoint union of AFs to build a single AF ℱ so that Definition 5.1. If (ℱ )∈ is a countable sequence of argumentation frameworks where each ℱ then we define the (ℱ )∈ as follows: ℋ disjoint union ℋ of the sequence = (ℋ, ℋ), where ℋ
= = (, ), ∧ (, ) ∈ ∈ {stb, infstb, infco, infad}, {⟨, ⟩ : ∈ } and (⟨, ⟩, ⟨, ⟩) ∈ ℋ ⇔ =
∈ [′] for each , Lemma 5.2. Let ℋ be the disjoint union of a sequence of ∅ is an admissible extension in any AF and since every argument in ℱ extension. Thus, ℱ ∖ ∖ is attacked, ∅ is also a complete
has a unique extension if the Π11-hardness of Uni∞. which shows that Unia∞d and Unic∞o are Π11-hard. and only if
∖ is well founded if and only if ∈ ,
For the other , ∅ is not a extension. We use Theorem 3.10 to show Π1-hardness. Let be any Π11 set. Then
1 we get from Remark 3.11 a sequence of trees ′ so that 0∞ ∈ [′] for each , and { : ′ has only one path} is Π11-hard. It follows from Lemma 4.1 that this holds if and only if ℱ ′ has a unique extension, which shows Theorem 4.4. For any Skept∞ is Π11-hard.
Proof. Let be a Π11 set. Then we get from Remark 3.11 a sequence of trees ′ so that 0∞ and { : ′ has only one path} is Π11-hard. Then note that ⟨, 0⟩ ∈ Skept∞ where is a computable index for := ℱ′ if and only if ′ only has paths (0) = 0 if and only if ′ has only one path (see the
with This shows the Π11-hardness of Skept∞.
Theorem 4.5. For and for any computable tree , there exists a computable 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 .
Skept∞(ℱ)
5. Complexity of Cred∞(ℱ) and
problem is trivial.
In this section, we examine the complexity of the computable argumentation framework problems Cred∞(ℱ) and Skept∞(ℱ) for a single
ℱ. Note that Cred∞(ℱ) is no more complicated than the full
Cred∞, so Cred∞(ℱ) is Σ11 for for
1 {ad, stb, co, infad, infstb, infco}, and Skept∞(ℱ) is Π1 ∈ {stb, co, infad, infstb, infco}. Recall that Skepta∞d
∈ Here we show that even restricting to a single com
1 putable argumentation framework, these sets can be Σ1complete or Π11-complete. We do omit discussion of Skeptc∞o (ℱ), just as we omitted discussion of the hardness for Skeptc∞o above. This is because Skeptc∞o (ℱ) is exactly the grounded extension of ℱ . 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 definition of ′ in Remark 3.11) if and only if ∈ . Theorem 5.3. There is a computable argumentation
We omit the proof of the following easy lemma.
AFs (ℱ )∈ and ∈ {ad, stb, co}. A set ⊆ : ⟨, ⟩ ∈ } is a extension in ℱ . extension of ℋ if and only if for each , := { ∈
ℋ is a Credc∞o (ℱ) = Credi∞nfco(ℱ) is Σ11-complete. framework ℱ so that Creda∞d (ℱ) = Credi∞nfad(ℱ) = Proof. Let be a Σ11-complete set, and let ( )∈ be a tree-sequence for . We consider the argumentation framework ℋ
quence (ℱ )∈ of argumentation frameworks. Note
which is the disjoint union of the sethat since the sequence of trees sequence of computable trees, ℋ sented argumentation framework.
is a computable is a computably premissible extension in ℋ
Note that an argument ⟨ , ⟩ is a member of an ad
if and only if is a member of an admissible extension in ℱ by Lemma 5.2 and the fact that the empty set is an admissible extension in all of the ℱ . Similarly, ⟨ , ⟩ is a member of a complete extension in ℋ if and only if is a member
of a complete extension in ℱ . By Lemma 4.1, each of these conditions is equivalent to being on a path in [ ], thus Creda∞d (ℱ) = Credc∞o (ℱ). Since all of the non-empty admissible extensions in ℱ are infinite, these coincide with Credi∞nfad(ℱ) = Credi∞nfco(ℱ).
We now give a reduction of to Creda∞d (ℋ need to give a computable function so that ∈ if and
). We only if () ∈ Creda∞d (ℋ Then ⟨ , ⟩ ∈ Creda∞d (ℋ ). We define () = ⟨ , ⟩.
) if and only if there is a path of Creda∞d (ℋ
). in [ ] if and only if ∈ , showing the Σ11-hardness
With a more cumbersome construction, we now show that we can find a single computable argumentation framework that simultaneously witnesses the hardness analyze in this paper. for each of the Cred∞(ℱ) and Skept∞(ℱ) which we Theorem 5.4. There is a single computable argu
1 mentation framework ℱ so that Cred∞(ℱ) is Σ1complete for each and
Skept∞(ℱ) is {stb, infad, infco, infstb}.
Π11-complete for each ∈ {ad, co, stb, infad, infco, infstb} 6. Trees coding extensions in (ℱ ) hold: in Theorem 4.4. (ℋ, ℋ) with ℋ
We construct a new AF ℋ = ⋃︀
∈{⟨, ⟩ : ∈ } and quence of argumentation frameworks constructed Proof. Let be a Π11-complete set and recall the se- Spec¬∅ for In this section, we give upper bounds to the complexity of 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 ∈ {ad, stb, infad, infstb} as well as giving (⟨, ⟩, ⟨, ′⟩) ∈ ℋ if and only if one of the following (ℱ ) into the set of paths through a tree. Lemma 5.6. If any element ⟨ , ⟩ for some , is in , ing on level 2 serves to code whether or not ∈ . • = ′ and (, ) ∈ • ̸= ′ and = , = }. ′ and = ⋃︀ Lemma 5.5. A subset of ℋ is a non-empty admissible extension if and only if is a stable extension if and only if there is a sequence ( )∈ so each is a path through
∈ where each is {⟨ , ⟩ : ≺ as these are self-defeating.
Proof. Suppose that is a non-empty admissible extension. Observe that no element ⟨ , ⟩ or ⟨, ⟩ can be in then ∩ {⟨ , ⟩ : ∈ <
} = {⟨, ⟩ : ∈ } ⟨ , ⟩ ∈ , then {⟨ , ⟩ : ∈ } ⊆ . for some ∈ [′], . Further, if there exists so that ⟨ , ⟩ ∈ .
Proof. As in the argument in Lemma 4.1, ∩ {⟨ , ′⟩ : ∈ <
} being non-empty implies that it equals {⟨, ′⟩ : ∈ } for some . If ⟨ , ⟩ then for any , the attack from ⟨, ⟩ must be defended, so
Thus if is non-empty and admissible, then there ⋃︀
∈ ⊆ coincide. is some sequence ( )∈ so that
∈ [′] and . It is straightforward to check that this set is in fact stable, so cannot contain a proper superset.
Thus stable, admissible, and being a set as described all of Creda∞d (ℋ).
Since every non-empty admissible set is infinite and stable, Creda∞d (ℋ) =
Creds∞tb (ℋ) =
Credc∞o (ℋ) = Credi∞nfad(ℋ) = Credi∞nfstb(ℋ) = Credi∞nfco(ℋ). Further, note that ⟨1, ⟩ ∈ Creda∞d (ℋ) if and only if there is a ∈ [′] with (0) = 1 if and only if ′ has more than one path if and only if ∈/ , showing the Σ11-hardness
Fix non-empty admissible extension is infinite and stable, and each extension is non-empty and admissible, we
∈ {stb, infad, infstb, infco}. Then since every see that Skept∞(ℋ) = Skepts∞tb (ℋ).
Given a computable argumentation framework ℱ 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 , we . 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 branchBranching 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 6.1. Theorem 6.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.
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 6.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
Theorem 6.7. Let ℱ be a (computable) argumentation framework. Then the stable extensions of ℱ are in (computable) bijection with the paths in ℱ .
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.
Proof. Given a stable extension of ℱ , we define the corresponding path in ℱ as follows. For each , let () be 0 if ∈ and let () be + 1 where is least so that ∈ and ↣ otherwise. It is straightforward to check that ∈ [ ℱ ].
Given a path through ℱ , first note that whenever Corollary 6.3. For every computable AF ℱ, there exists there is some ≺ so that ∈ In , then () = 0. a computable tree so that Speca¬d∅(ℱ) = Spec( ). This is because whenever ⪯ , then In ⊆ In . Then since = ↾ max(| |,+1) is on ℱ , we cannot have Proof. It follows immediately from Theorem 6.2 that () ̸= 0 since ∈ In and therefore cannot be in Speca¬d∅(ℱ) = Spec( ℱ ). Out . It follows that ⋃︀ ≺ In = { : () = 0}. Let = { : () = 0}.
Corollary 6.4. For every computable AF ℱ, there exists Note that is conflict-free, since if , ∈ , then a computable tree ̂︀ so that Speci¬nf∅ad(ℱ) = Spec(̂︀ ). ↣̸ 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 6.8. For any computable AF ℱ there exists a computable tree so that Specs¬tb∅(ℱ) = Spec( ).
Proof. This follows directly from Theorem 6.7 along with the fact that ∅ is never a stable extension.
Corollary 6.9. For any computable AF ℱ there exists a computable tree so that Speci¬nf∅stb(ℱ) = Spec( ).
1 Corollary 6.5. Unii∞nfad is Π1.
Proof. is in Uniinfad if and only if the tree ̂︀ in Corollary
1 6.4 has a unique path. By Theorem 3.10, this is a Π1 condition. By Theorem 3.10, these are both Π11 conditions. we have ∈ Uniinfstb if and only if ̂︀ ℱ has a unique path. from as described at the beginning of this section. It Proof. We add layers of branching to the tree as in Corollary 6.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 ℱ .
1 Corollary 6.10. Unis∞tb and Unii∞nfstb are Π1.
Proof. As the paths through ℱ are in bijection with the stable extensions, ∈ Unis∞tb if and only if ℱ has a are in bijection with the infinite stable extensions in unique path. As the paths through ̂︀ ℱ (see Corollary 6.9)
ℱ,
and + as follows: also their attacked sets +.
Given an argumentation framework ℱ construct a tree ℱ so that paths through ℱ code complete extensions. In order to ensure that ℱ () ⊆ will need the paths in ℱ to not only code sets but , we , we can similarly Given an extension , we will let ∈ ℱ encode + 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., ℱ () ⊆ verifies that the elements which says are in + are in , while (2 + 1) simply fact in +.
Formally, we define ℱ as follows: Definition 6.11. subsets of arguments in ℱ :
Any given string ∈ < defines four • In = { : (2) = 0
} ∪ { : (∃)( (2 + 1) = + 1
} 1) > + 1 ∧ ↣
)} • Out = { : (2) ̸= 0 } ∪ { : (∃) (2 + (2 + 1) = 0
} )} ∪ { : (2 + 1) ̸= 0 } • InSplus
= { : (∃)( (2) > + 1 ∧ ↣ • OutSplus = { : (∃) (2) = + 1 } ∪ { : We define ℱ as the set of so that 1. In is conflict-free; 2. In ∩ Out = ∅; 3. InSplus ∩ OutSplus = ∅; 4. If (2) = + 1, then ↣ ; then ↣̸
; then ↣̸ ℱ ()). 5. If (2 + 1) = + 1, then ↣ ; 6. For , < | |, if ∈ OutSplus and ∈ In 7. For , < | |, if ∈ OutSplus and ∈ In , (i.e., does not contradict ⊆ jection with the set of paths [ ℱ ].
Theorem 6.12. The complete extensions of ℱ are in biProof. Let be any complete extension. We can define = ⋃︀
≺ InSplus . is straightforward to verify that each condition (1-7) of Definition 6.11 is satisfied by ↾ for each .
Given a path ∈ [ ℱ ], we can define sets = { : (2) = 0} and = { : (2 + 1) ̸= 0}. We note that when ⪯ , In ⊆ the previous theorems, that = ⋃︀
In . It follows from this fact, as in ≺ In . Similarly,
Next we see that = +. If ∈ , then (2+1) ̸= 0 and by condition 5, we have (2+1)− 1 attacks . But ⊆ then (2+1)− 1 ∈ In ↾ 2+2 , so (2+1)− 1 ∈ . Thus +. On the other hand if ∈/ , then condition 6 for all of length > 2 + 1 ensures that there is no
Finally, we verify that is complete. is clearly conlfict free by Condition 1. Condition 7 ensures that any ∈ is also in ℱ (), since if ∈/ , then ↣̸ .
To see that ℱ () ⊆
, note that any ∈/ has condition 4. Thus ∈/ ℱ (). () ̸= 0 and ()− 1 ∈/ + and ()− 1 ↣ by Remark 6.13. The map from paths plete extensions ⊆
ℱ is computable, but to compute ∈ ℱ we need both and +. Thus, we are able to say that for any computable AF ℱ, the set of Turing degrees of pairs (, +) where is a complete extension is always Spec( ) for a computable tree , but note that and + are not generally of the same Turing degree. Thus, we are currently unable to fully characterize ∈ [ ℱ ] to comSpecc¬o∅ or Speci¬nf∅co. 1 Corollary 6.14. Unii∞nfco is Π1. that this is a Π11 condition.
Proof. We can alter the tree ℱ as in Corollary 6.4 to get a new tree ̂︀ so that the paths through ̂︀ are in bijection with the infinite complete extensions. Then ∈ Unii∞nfco if and only if ̂︀ has a unique path. Theorem 3.10 shows Corollary 6.15. Fix ∈ {ad, stb, co, infad, infstb, infco} and suppose that ℱ has only countably many non-empty extensions. Then there is a hyperarithmetical set so that { : ∈ } is a extension of ℱ. 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 [22, Theorem 3.9], has a hyperarithmetical path, which corresponds to a hyperarithmetical so that { : ∈ } is a extension of ℱ.
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 Σ11 and Π11 sets. Furthermore, we showed 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 dificult for an individual, specific framework.
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 finitely many attacks only [
Andrews was partially supported by NSF grant DMS2348792. San Mauro is a member of INDAM-GNSAGA. 35–47 pear semantics, Artificial Intelligence 173 (2009) 1559– 1591. [13] W. Dvořák, S. Woltran, Complexity of semi-stable and stage semantics in argumentation frameworks, Information Processing Letters 110 (2010) 425–430. [14] V. Brattka, P. Hertling, Handbook of computability and complexity in analysis, Springer, 2021. [15] K. V. Velupillai, Computable foundations for eco