Justification,stability and relevance in incomplete argumentation frameworks

Abstract

We explore the computational complexity of justification, stability and relevance in incomplete argumentation frameworks (IAFs). IAFs are abstract argumentation frameworks that encode qualitative uncertainty by distinguishing between certain and uncertain arguments and attacks. These IAFs can be completed by deciding for each uncertain argument or attack whether it is present or absent. Such a completion is an abstract argumentation framework, for which it can be decided which arguments are acceptable under a given semantics. The justification status of an argument in a completion then expresses whether the argument is accepted (in), not accepted because it is attacked by an accepted argument (out) or neither (undec). For a given IAF and certain argument, the justification status of that argument need not be the same in all completions. This is the issue of stability, where an argument is stable if its justification status is the same in all completions. For arguments that are not stable in an IAF, the relevance problem is of interest: which uncertain arguments or attacks should be investigated for the argument to become stable? In this paper, we define justification, stability and relevance for IAFs and provide a complexity analysis for these problems under grounded, complete, preferred and stable semantics.

1. Introduction

A central concept in computational argumentation is that of argumentation frameworks (AFs), in which arguments and the attack relation between them are represented as a directed graph where nodes correspond to arguments and edges display the attack relation [10]. One of the assumptions in such Dung-style argumentation frameworks is that all arguments and attacks are known. However, in practice, argumentation is a dynamic process in which not all arguments and attacks may be known in advance. For example, not all the evidence on which arguments are based might already have been observed, making the presence of a specific argument uncertain [16]. AFs are not able to represent qualitative uncertainty on the existence of specific arguments and attacks. For this reason, incomplete argumentation frameworks (IAFs) have been designed [3,4,7,15]. IAFs are an extension to AFs in which not only certain arguments are specified, but also arguments and attacks for which it is uncertain whether they are present. By deciding for every uncertain argument and attack whether it is present or absent, it is possible to “complete” an IAF, turning it into an AF. Thus, an IAF represents a set of possible AFs, its completions.

Since every completion of an IAF is an AF, standard Dung semantics can be applied to determine the extensions of any completion [10]. Based on these extensions, one can determine the justification status of every argument in every completion of the IAF. The justification status is defined in terms of labels like in (expressing that the argument is in some, or all, extensions and therefore should be accepted), out (expressing that the argument is attacked by an in argument and therefore should be rejected) and undec (for all other arguments, which are undecided) [6]. Note that the notion of justification status is only defined on the AFs that make up the completions of an IAF, but not on the IAF itself.

Now suppose that we are interested in the justification status of a particular argument, but are faced with an IAF containing uncertainties concerning the presence of (other) arguments and attacks. Then it would be interesting to know whether it is required to resolve these uncertainties. In a situation where the argument we are interested in has the same justification status in each completion of the IAF, there is no need for further investigation into the uncertain arguments and attacks. Then we say that the argument is stable with respect to the IAF and justification status. The detection of such stability has practical applications, for instance as a termination criterion for argumentative dialogue agents: in the agent architecture for inquiry proposed in [16,17], stability detection prevents the agent from asking unnecessary questions. In addition, [15] proposes an application of stability detection in negotiating agents, to recognise situations in which an agent should stop negotiating and accept its opponent’s offer.

In the case that the argument of interest is not stable in the given IAF, we know that the agent should collect more information. However, not all information that is currently unknown can influence the justification status of the argument of interest. A natural question would therefore be: which uncertainties should we resolve in order to reach a point where the argument is stable? In other words: which uncertain arguments or attacks are still relevant for the justification status? Adding relevance to an inquiry or negotiation process ensures that the questions that are asked contribute to reaching stability.

The problem of detecting stability has been studied for structured (ASPIC⁺) approaches to argumentation in [16,17,23]. The algorithms proposed in this line of research have been implemented in an inquiry system for the intake of online trade fraud that has been used by hundreds of users every day since its launch in September 2019 [16]. For abstract approaches to argumentation, the problem of detecting stability was introduced in [15] and the subsequent problem of detecting relevance in incomplete (abstract) argumentation frameworks was introduced in our earlier work in [18]. Given the high potential for applications of stability and relevance in inquiry and negotiation, it would be useful to have efficient algorithms for solving these problems in abstract approaches to argumentation as well. In this paper we take a first step in the development of such algorithms, by investigating in which complexity class the problems of detecting stability and relevance are situated: insights in the complexity of the problems establish the possible efficiency of any algorithm to solve them.

The contribution of this paper, which expands on [18], is the extensive study of the complexity of justification, stability and relevance in the context of IAFs. Specifically, we present precise complexity results for each of these three problems under grounded, complete, stable and preferred semantics.1

¹

In [18] we only discussed the complexity of relevance for in/out justification statuses under grounded semantics, whereas this paper is the first to also give complexity results for relevance for all justification statuses under all semantics (stable, complete, grounded, preferred).

Table 1 provides an overview of all these results. We further provide full proofs and illustrative examples for all the complexity results of justification, stability and relevance.

The paper is structured as follows. In Section 2, we provide the necessary preliminaries. In Section 3, we study the complexity of identifying the justification status of an argument. These results are used in Section 4 in our complexity analysis of the stability problem. We then introduce the relevance problem for IAFs in Section 5 and provide complexity results. Related work is discussed in Section 6; we conclude in Section 7.

Table 1

Overview of all complexity results related to this paper. We considered four different semantics: stable (st), complete (cp), grounded (gr) or preferred (pr). The semantics and acceptance strategies are defined formally in Section 2.1. If a reference is specified, this complexity result is trivial from an earlier result in the literature. New results are printed bold; we refer to the corresponding proposition by “P” and the proposition number

Semantics	Acceptance strategy	Label	justification	stability	relevance
st	credulous	in/out	NP-c [8,9]	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [3]	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P17
st	credulous	undec	Trivial (no) P4	Trivial (no) P10	Trivial (no) P18
st	sceptical	in/out	CoNP-c [9]	CoNP-c [3]	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P17
st	sceptical	undec	CoNP-c P5	CoNP-c P9	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P19
st	sceptical-existent	in/out	DP-c [12]	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [3]	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P20
st	sceptical-existent	undec	Trivial (no) P4	Trivial (no) P10	Trivial (no) P18
cp	credulous	in/out	NP-c [8,9]	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [3]	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P13
cp	credulous	undec	P-c P1	CoNP-c P6	NP-c P12
cp	sceptical	in/out	P-c [10]	CoNP-c [3]	NP-c P12
cp	sceptical	undec	CoNP-c P2	CoNP-c P7	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P15
gr	credulous	in/out	P-c [10]	CoNP-c [3]	NP-c P12
gr	credulous	undec	P-c P1	CoNP-c P6	NP-c P12
gr	sceptical	in/out	P-c [10]	CoNP-c [3]	NP-c P12
gr	sceptical	undec	P-c P1	CoNP-c P6	NP-c P12
pr	credulous	in/out	NP-c [8,9]	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [3]	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P13
pr	credulous	undec	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P3	${\mathbf{\Pi }}_{\mathbf{3}}^{\mathit{p}}$ -c P8	${\mathbf{\Sigma }}_{\mathbf{3}}^{\mathit{p}}$ -c P14
pr	sceptical	in/out	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [11]	${\mathrm{\Pi }}_2^{\mathit{p}}$ -c [3]	${\mathbf{\Sigma }}_{\mathbf{3}}^{\mathit{p}}$ -c P16
pr	sceptical	undec	CoNP-c P2	CoNP-c P7	${\mathbf{\Sigma }}_{\mathbf{2}}^{\mathit{p}}$ -c P15

2. Preliminaries

In this section, we recall the most important notions from abstract argumentation and the associated semantics [10], as well as incomplete argumentation frameworks and their completions [3,4,7,15]. We also provide a brief introduction to the polynomial hierarchy, which is required for our complexity study.

2.1. Argumentation frameworks and semantics

An argumentation framework (AF) $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ , as introduced in [10], consists of a finite set $\mathcal{A}$ of arguments and a binary attack relation $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ on them, where $\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\in \mathcal{R}$ indicates that argument A attacks argument B. In this paper, we evaluate arguments using the semantics of [10].

Definition 1 (Extension-based semantics).

Let $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an AF and $\mathit{S}\subseteq \mathcal{A}$ . Then:

S is conflict-free iff for each $\mathit{X}\mathrm{,}\mathit{Y}\in \mathit{S}:\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}\notin \mathcal{R}$ ;

$\mathit{X}\in \mathcal{A}$ is acceptable with respect to S iff for each $\mathit{Y}\in \mathcal{A}$ such that $\mathrm{(}\mathit{Y}\mathrm{,}\mathit{X}\mathrm{)}\in \mathcal{R}$ , there is a $\mathit{Z}\in \mathit{S}$ such that $\mathrm{(}\mathit{Z}\mathrm{,}\mathit{Y}\mathrm{)}\in \mathcal{R}$ ;

S is an admissible set iff S is conflict free and $\mathit{X}\in \mathit{S}$ implies that X is acceptable with respect to S;

S is a complete extension (cp) iff S is admissible and for each X: if $\mathit{X}\in \mathcal{A}$ is acceptable with respect to S then $\mathit{X}\in \mathit{S}$ ;

S is a preferred extension (pr) iff it is a set inclusion maximal admissible set;

S is the grounded extension (gr) iff it is the set inclusion minimal complete extension; and

S is a stable extension (st) iff it is complete and attacks all the arguments in $\mathcal{A}\setminus \mathit{S}$ .

Example 1.

Fig. 1 shows an example of an argumentation framework $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ where $\mathcal{A}=\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ and $\mathcal{R}=\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{D}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{D}\mathrm{,}\mathit{E}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{E}\mathrm{,}\mathit{D}\mathrm{)}\}$ . The grounded extension of AF is $\{\mathit{A}\}$ . This is also a complete extension. Additionally, there are two complete extensions that are also preferred and stable: $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ and $\{\mathit{A}\mathrm{,}\mathit{D}\}$ .

In order to decide if an argument should be accepted w.r.t. a given AF and semantics, one can choose between different strategies. We will refer to these as acceptability strategies, following [5, Definition 1]. Dependent on the strategy, the argument is accepted iff it occurs in one and/or all extensions.

Definition 2 (Acceptability strategies).

Let $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an argumentation framework and σ some semantics in $\{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and let A be some argument in $\mathcal{A}$ .

A is sceptically accepted w.r.t. σ semantics iff A belongs to each σ-extension of $\mathit{\text{AF}}$ ;

A is credulously accepted w.r.t. σ semantics iff A belongs to some σ-extension of $\mathit{\text{AF}}$ ; and

A is sceptically-existent accepted w.r.t. σ semantics iff $\mathit{\text{AF}}$ has at least one σ-extension and A belongs to each σ-extension of $\mathit{\text{AF}}$ .

We refer to sceptical, credulous and sceptical-existent as acceptability strategies.

Note that the sceptical-existent acceptability strategy only differs from the sceptical strategy for st semantics: for gr, cp and pr semantics, each AF has at least one extension, while it is possible for an AF to have no st extension.

Example 2.

In the AF illustrated in Fig. 1, only the argument A is sceptically accepted w.r.t. cp semantics. The arguments C, D and E are all credulously accepted. Argument B is not accepted for any acceptability strategy.

Fig. 1.

An example of an argumentation framework. Arguments are depicted as circles, whereas attacks are depicted as arrows.

2.2. Incomplete argumentation frameworks

Incomplete argumentation frameworks (IAFs) [3,4,15] are an extension to AFs, initially proposed as partial AFs in [7]. In an IAF, the set of arguments and attacks is split into two disjoint parts: a certain part ( $\mathcal{A}$ and $\mathcal{R}$ ) and an uncertain part ( ${\mathcal{A}}^{?}$ and ${\mathcal{R}}^{?}$ ). For the uncertain elements, it is not known whether they are part of the argumentation framework or not. They may be added in the future, for example because more information is acquired in an inquiry dialogue, or removed, for example because after investigation, this element turned out not to be present in the given setting.

Definition 3 (Incomplete argumentation framework).

An incomplete argumentation framework is a tuple $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , where $\mathcal{A}\cap {\mathcal{A}}^{?}=\varnothing$ , $\mathcal{R}\cap {\mathcal{R}}^{?}=\varnothing$ and:

$\mathcal{A}$ is the set of certain arguments;

${\mathcal{A}}^{?}$ is the set of uncertain arguments;

$\mathcal{R}\subseteq \mathrm{(}\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{)}\times \mathrm{(}\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{)}$ is the certain attack relation; and

${\mathcal{R}}^{?}\subseteq \mathrm{(}\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{)}\times \mathrm{(}\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{)}$ is the uncertain attack relation.

Example 3 (IAF).

Fig. 2 shows an example of an incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ where $\mathcal{A}=\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , ${\mathcal{A}}^{?}=\{\mathit{A}\mathrm{,}\mathit{D}\}$ , $\mathcal{R}=\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{D}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{D}\mathrm{,}\mathit{E}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{E}\mathrm{,}\mathit{D}\mathrm{)}\}$ and ${\mathcal{R}}^{?}=\{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}$ . Arguments A and D are currently absent but may be added in the future. The attack from A to B is certainly present if A is present. Similarly, the attacks $\mathrm{(}\mathit{D}\mathrm{,}\mathit{C}\mathrm{)}$ , $\mathrm{(}\mathit{D}\mathrm{,}\mathit{E}\mathrm{)}$ and $\mathrm{(}\mathit{E}\mathrm{,}\mathit{D}\mathrm{)}$ are certainly present if D is present. The attack from C to B, on the other hand, is uncertain: although the arguments B and C are certainly present, the attack itself is currently absent but may still be added.

Fig. 2.

An example of an incomplete argumentation framework. Certain arguments are depicted as circles with solid borders, whereas uncertain arguments are circles with dashed borders. Attacks are depicted as arrows, which have a solid line if they represent certain attacks and a dashed line if they represent uncertain attacks.

An incomplete argumentation framework can be completed by deciding for all uncertain arguments and attacks whether or not they are present, as defined below.

Definition 4 (Completions).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a completion is any AF $⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ that satisfies $\mathcal{A}\subseteq {\mathcal{A}}^{\prime }\subseteq \mathcal{A}\cup {\mathcal{A}}^{?}$ and $\mathcal{R}{|}_{{\mathcal{A}}^{\prime }}\subseteq {\mathcal{R}}^{\prime }\subseteq \mathrm{(}\mathcal{R}\cup {\mathcal{R}}^{?}\mathrm{)}{|}_{{\mathcal{A}}^{\prime }}$ where the restriction $\mathcal{R}{|}_{{\mathcal{A}}^{\prime }}$ of an attack $\mathcal{R}$ to a set of arguments ${\mathcal{A}}^{\prime }$ is defined as $\mathcal{R}{|}_{{\mathcal{A}}^{\prime }}=\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\in \mathcal{R}|\mathit{A}\in {\mathcal{A}}^{\prime }\text{ and }\mathit{B}\in {\mathcal{A}}^{\prime }\}$ .

Example 4 (Completions).

The incomplete argumentation framework from our previous example has eight completions. These are illustrated in Fig. 3.

Fig. 3.

The eight completions of our incomplete argumentation framework.

Since completions are abstract argumentation frameworks, we can use the semantics from Section 2.1 to evaluate arguments in the completions of an incomplete argumentation framework. This leads to two ways of defining acceptance for incomplete argumentation frameworks, proposed in [3, pages 6-7]: necessary and possible acceptance. Informally, some argument is necessarily accepted if it is accepted in each completion, whereas the argument is possibly accepted if this holds for some completion. The definitions below make a distinction between the different acceptability strategies.

Fig. 4.

Visualisation of the cp extensions of each of the eight completions of $\mathcal{I}$ from Example 3, where the completion is repeated for each cp extension and argument that are present in that extension are coloured green.

Definition 5 (Necessary acceptance).

Given an incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ , some semantics σ in $\{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and some acceptability strategy $\mathit{\alpha }\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\mathrm{,}\mathit{\text{sceptical-existent}}\}$ , A is necessarily α-σ accepted w.r.t. $\mathcal{I}$ iff A is α-σ accepted in each completion of $\mathcal{I}$ .

Definition 6 (Possible acceptance).

Given an incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ , some semantics σ in $\{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and an acceptability strategy $\mathit{\alpha }\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\mathrm{,}\mathit{\text{sceptical-existent}}\}$ , A is possibly α-σ accepted w.r.t. $\mathcal{I}$ iff A is α-σ accepted in some completion of $\mathcal{I}$ .

Example 5 (Necessary and possible acceptance).

Fig. 4 displays the cp extensions of each of the eight completions of $\mathcal{I}$ from Example 4, where the completion is repeated for each cp extension. None of the certain arguments in $\mathcal{I}$ is necessarily sceptically accepted w.r.t. cp semantics, because no argument is in all extensions of all completions. Note that A, although it is present in all extensions of all completions of $\mathcal{I}$ in which it occurs, is not necessarily sceptically accepted w.r.t. cp semantics: A is not a certain argument in $\mathcal{I}$ . The only argument that is necessarily credulously accepted w.r.t. cp semantics is E. B is possibly sceptically accepted w.r.t. cp semantics, because the argument is in each extension of the completion ${\mathit{\text{AF}}}_7$ (as well as ${\mathit{\text{AF}}}_8$ ). C and E are possibly sceptically accepted w.r.t. cp semantics as well, thanks to their presence in the only extension of ${\mathit{\text{AF}}}_2$ . Finally, all certain arguments of $\mathcal{I}$ (B, C and E) are possibly credulously accepted w.r.t. cp semantics.

The definitions of necessary and possible acceptance are particularly interesting for our work, as they are strongly related to the notion of stability, to be defined formally in Section 4. Before we do so, we first explain the polynomial hierarchy in the next section.

2.3. The polynomial hierarchy

In this section, we give a brief introduction to the polynomial hierarchy – for a more detailed explanation, we refer to [14]. This is required for the complexity study presented in this paper as the problems we study are situated on various levels in the polynomial hierarchy.

The polynomial hierarchy [19] is a hierarchy of complexity classes defined using oracle machines, i.e., Turing machines that are allowed to call a subroutine (oracle), deciding some fixed problem in constant time. For a class of decision problems $\mathcal{C}$ and a class $\mathcal{X}$ defined by resource bounds, ${\mathcal{X}}^{\mathcal{C}}$ denotes the class of problems decidable on a Turing machine with a resource bound given by $\mathcal{X}$ and an oracle for a problem in $\mathcal{C}$ . For example, problems in NP are decidable with a resource bound given by NP and an oracle for a problem in P, therefore $\text{NP}={\text{NP}}^{\text{P}}$ .

Based on these notions, the sets ${\mathrm{\Sigma }}_{\mathit{k}}^{\mathit{p}}$ and ${\mathrm{\Pi }}_{\mathit{k}}^{\mathit{p}}$ are defined as follows: ${\mathrm{\Sigma }}_0^{\mathit{p}}={\mathrm{\Pi }}_0^{\mathit{p}}=\mathit{P}$ , ${\mathrm{\Sigma }}_{\mathit{k}+1}^{\mathit{p}}={\text{NP}}^{{\mathrm{\Sigma }}_{\mathit{k}}^{\mathit{p}}}$ and ${\mathrm{\Pi }}_{\mathit{k}+1}^{\mathit{p}}={\text{CoNP}}^{{\mathrm{\Sigma }}_{\mathit{k}}^{\mathit{p}}}$ . So problems in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ are decidable with a resource bound given NP and an oracle for a problem in ${\mathrm{\Sigma }}_1^{\mathit{p}}=\text{NP}$ . The polynomial hierarchy (PH) is then defined as the union of these complexity classes: $\text{PH}={\bigcup }_{\mathit{k}=0}^{\infty }{\mathrm{\Sigma }}_{\mathit{k}}^{\mathit{p}}={\bigcup }_{\mathit{k}=0}^{\infty }{\mathrm{\Pi }}_{\mathit{k}}^{\mathit{p}}$ . Finally, note that the definition over classes in the polynomial hierarchy imply a subset relation, illustrated in Fig. 5. By this relation, for each $\mathit{i}\in \mathbb{N}$ , each problem in ${\mathrm{\Sigma }}_{\mathit{i}}^{\mathit{p}}$ is also in ${\mathrm{\Sigma }}_{\mathit{i}+1}^{\mathit{p}}$ , as well as in ${\mathrm{\Pi }}_{\mathit{i}+1}^{\mathit{p}}$ .

A problem that is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete is ${\mathrm{\Sigma }}_2$ -SAT [22]; in this paper we will use the CNF formulation that is also used in, e.g. [3,4]. An instance of ${\mathrm{\Sigma }}_2$ -SAT would be $\mathrm{(}\mathrm{\Phi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ , where Φ is an input formula in CNF over the pairwise disjoint sets of propositional variables X and Y. Then the ${\mathrm{\Sigma }}_2$ -SAT problem is to decide if there exists a truth value assignment ${\mathit{\tau }}_{\mathit{X}}$ to variables of X such that for each truth value assignment ${\mathit{\tau }}_{\mathit{Y}}$ : $\mathrm{\Phi }[{\mathit{\tau }}_{\mathit{X}}\mathrm{,}{\mathit{\tau }}_{\mathit{Y}}]=\text{False}$ , where $\mathrm{\Phi }[{\mathit{\tau }}_{\mathit{X}}\mathrm{,}{\mathit{\tau }}_{\mathit{Y}}]$ is the truth value that Φ evaluates to when applying the assignment ${\mathit{\tau }}_{\mathit{X}}$ to X and ${\mathit{\tau }}_{\mathit{Y}}$ to Y.

Fig. 5.

The relation between complexity classes in the polynomial hierarchy. The lines between classes denote a subset relationship: all problems in the class of the left side are also contained in the class on the right side.

3. Justification status

In this section, we define the notion of justification status and study the complexity of determining this status for a given argument. The justification status [6] is a notion of acceptance for arguments in abstract argumentation frameworks that is more fine-grained than only considering the presence or absence in extensions. Given an AF $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ , an argument A and a semantics σ, A’s justification status can be determined by either considering all σ-extensions (sceptical and sceptical-existent) or at least one σ-extension of the AF (credulous). In this context, an argument can be in (part of all/some σ-extensions); out (attacked by all/some σ-extensions), or undec (otherwise).

Definition 7 (Argument justification status).

Let $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an argumentation framework and σ some semantics in $\{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ . Let A be some argument in $\mathcal{A}$ .

The justification statuses for the in label are:

• A is σ-sceptical-in iff A belongs to each σ-extension of $\mathit{\text{AF}}$ ;

• A is σ-credulous-in iff A belongs to some σ-extension of $\mathit{\text{AF}}$ ; and

• A is σ-sceptical-existent-in iff $\mathit{\text{AF}}$ has a σ-extension and A belongs to each σ-extension of $\mathit{\text{AF}}$ .

The justification statuses for the out label are:

• A is σ-sceptical-out iff for each σ-extension S of $\mathit{\text{AF}}$ , A is attacked by some argument in S;

• A is σ-credulous-out iff for some σ-extension S of $\mathit{\text{AF}}$ , A is attacked by some argument in S; and

• A is σ-sceptical-existent-out iff $\mathit{\text{AF}}$ has a σ-extension and for each σ-extension S of $\mathit{\text{AF}}$ , A is attacked by some argument in S.

The justification statuses for the undec label are:

• A is σ-sceptical-undec iff for each σ-extension S of $\mathit{\text{AF}}$ , A is not in S and not attacked by any argument in S;

• A is σ-credulous-undec iff for some σ-extension S of $\mathit{\text{AF}}$ , A is not in S and not attacked by any argument in S; and

• A is σ-sceptical-existent-undec iff $\mathit{\text{AF}}$ has a σ-extension and for each σ-extension S of $\mathit{\text{AF}}$ , A is not in S and not attacked by any argument in S.

The justification statuses that we consider in this paper are $\{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}\times \{\text{sceptical}\mathrm{,}\text{credulous}\mathrm{,}\text{sceptical-existent}\}\times \{\mathrm{\text{IN}}\mathrm{,}\mathrm{\text{OUT}}\mathrm{,}\mathrm{\text{UNDEC}}\}$ . In the remainder of this paper, we refer to in-, out or undec-justification in case the semantics and acceptability strategy is obvious or irrelevant.

Example 6 (Argument justification status).

Consider the argumentation framework ${\mathit{\text{AF}}}_1$ , as illustrated in Fig. 4. For $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ , A is σ-sceptical-in, while B is σ-sceptical-out. For $\mathit{\sigma }\in \{\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ , the arguments C, D and E are σ-credulous-in, σ-credulous-out as well as σ-credulous-undec.

We formulate the identification of justification status as a decision problem j-justification (where $\mathit{j}\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}\times \{\text{sceptical}\mathrm{,}\text{credulous}\mathrm{,}\text{sceptical-existent}\}\times \{\mathrm{\text{IN}}\mathrm{,}\mathrm{\text{OUT}}\mathrm{,}\mathrm{\text{UNDEC}}\}$ ):

j-justification
Given:	An argumentation framework $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ , a justification status j and an argument $\mathit{A}\in \mathcal{A}$
Question:	Does A’s justification status in $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ equal j?

The remainder of this section provides proofs for complexity results related to justification problems. Whereas the complexity of in-justification has been studied before (as acceptance problems, see [8–11]), this is not the case for out- and undec-justification. This is unfortunate, as detecting out- and undec-justification has interesting applications as well: since arguments that are undec are “more acceptable” than arguments that are out, these justification statuses provide a more fine-grained notion of acceptability than the distinction between accepted and not accepted. In addition, more insight in the complexity of detecting these justification statuses could for example be helpful in developing fast algorithms. Furthermore, we will use the complexities of out- and undec-justification later for finding the complexities of out- and undec-stability (Section 4) and out- and undec-relevance (Section 5). We will therefore provide complexity proofs for these types of justification under gr, cp, st and pr semantics. Our strategy in proving these complexities is to relate them to the complexities of in-justification and using existing results from the complexity of acceptance problems. Short proofs will be given directly after the lemmas and propositions, whereas we provide sketches for longer proofs; the full proofs can be found in Appendix A. We start with a lemma for justification that shows that in-justification and out-justification are in the same complexity class:

Lemma 1 (Justification status in and out).

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and $\mathit{c}\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\}$ , the complexity of σ-c- out - justification equals the complexity of σ-c- in - justification .

Proof.

Let $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an AF and $\mathit{A}\in \mathcal{A}$ an argument. Now construct ${\mathcal{A}}^{\prime }$ as $\mathcal{A}\cup \{\mathit{B}\}$ (where $\mathit{B}\notin \mathcal{A}$ ) and ${\mathcal{R}}^{\prime }=\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\}$ ; let ${\mathit{\text{AF}}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ . Then A is σ-c-out in $\mathit{\text{AF}}$ iff B is σ-c-in in ${\mathit{\text{AF}}}^{\prime }$ ; in addition, A is σ-c-in in $\mathit{\text{AF}}$ iff B is σ-c-out in ${\mathit{\text{AF}}}^{\prime }$ . □

Contrary to out-justification, undec-justification is not necessarily in the same complexity class as in-justification. However, under gr, cp and pr semantics, there is another relation, as we will show in Lemma 3.2

²

This relation does not exist for st semantics as arguments cannot be st-credulous-undec. We will prove the complexity of st-credulous-, st-sceptical-existent- and st-sceptical-justification later in this section.

Before we can do so, we prove relations between credulous-in- and sceptical-undec-justification, as well as between credulous-undec- and sceptical-in-justification, in the following lemma. The transformations used in this lemma are illustrated in Fig. 6.

Fig. 6.

Illustration of the argumentation frameworks that are used in transformations between justification problem instances used for proving Lemma 2. The figure illustrates three argumentation frameworks: $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ (first column), ${\mathit{\text{AF}}}^{\prime }=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ (second column) and ${\mathit{\text{AF}}}^{″}=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ (third column). The dotted, rounded rectangles represent all arguments in $\mathcal{A}$ except A. Each of the argumentation frameworks is displayed three times, corresponding to different extensions of $\mathit{\text{AF}}$ : the first row, where A is coloured yellow, represents extensions that do not contain A or any attacker of A (“A is undec”). The second row, where A is green and with boldface font, represents extensions containing A (“A is in”). Finally, the third row, where A is red and with italic font, represents extensions containing some attacker of A (“A is out”). The colours and typesetting refer to the justification statuses of arguments, where green and boldface font stands for in; yellow and regular font for undec and red and italic font for out.

Lemma 2 (Complementary relation in- and undec-justification).

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ , for each argumentation theory $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ and argument $\mathit{A}\in \mathcal{A}$ , each of the following holds:

A is σ-credulous- in in AF iff ${\mathit{A}}^{\prime }$ is not σ-sceptical- undec in $⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ ;

A is σ-sceptical- in in AF iff ${\mathit{A}}^{\prime }$ is not σ-credulous- undec in $⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ ;

A is σ-credulous- undec in AF iff ${\mathit{A}}^{\prime }$ is not σ-sceptical- in in $⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ ; and

A is σ-sceptical- undec in AF iff ${\mathit{A}}^{\prime }$ is not σ-credulous- in in $⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ .

Proof sketch.

We give the proof for the first item here. For full proofs of all items, we refer to Appendix A. Consider an arbitrary semantics $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ , argumentation theory $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ and argument $\mathit{A}\in \mathcal{A}$ . Construct ${\mathit{\text{AF}}}^{\prime }=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ ; for an illustration, see the first and second columns of Fig. 6. ⇒

Suppose that A is σ-credulous-in in $\mathit{\text{AF}}$ : then there is some σ-extension S of $\mathit{\text{AF}}$ containing A. Note that S also must be a σ-extension of ${\mathit{\text{AF}}}^{\prime }$ : all arguments in $\mathcal{A}$ attacking attackers of A are still in $\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}$ and $\mathit{S}\cup \{{\mathit{A}}^{\prime }\}$ is not a σ-extension as it is not conflict-free. Then there exists some σ-extension (i.e. S) of ${\mathit{\text{AF}}}^{\prime }$ in which ${\mathit{A}}^{\prime }$ is attacked by S, so ${\mathit{A}}^{\prime }$ is not σ-sceptical-undec in ${\mathit{\text{AF}}}^{\prime }$ .

⇐

Suppose that ${\mathit{A}}^{\prime }$ is not σ-sceptical-undec in ${\mathit{\text{AF}}}^{\prime }$ ; then there exists some σ-extension S of ${\mathit{\text{AF}}}^{\prime }$ such that either ${\mathit{A}}^{\prime }\in \mathit{S}$ or some argument attacking ${\mathit{A}}^{\prime }$ is in S. Given that ${\mathit{A}}^{\prime }$ is self-attacking, ${\mathit{A}}^{\prime }\notin \mathit{S}$ , so ${\mathit{A}}^{\prime }$ is attacked by some argument in S, which can only be A. Furthermore note that S is also a σ-extension of $\mathit{\text{AF}}$ , since the arguments that are acceptable w.r.t. S in $\mathit{\text{AF}}$ are exactly the same as the arguments acceptable w.r.t. S in ${\mathit{\text{AF}}}^{\prime }$ . To conclude, there exists some σ-extension (i.e. S) of $\mathit{\text{AF}}$ in which $\mathit{A}\in \mathit{S}$ , so A is σ-credulous-in in $\mathit{\text{AF}}$ .

 □

Lemma 2 is used in the following lemma to show that credulous-in-justification and sceptical-undec-justification are in complementary complexity classes, as well as credulous-undec-justification and sceptical-in-justification, under gr, cp and pr semantics.

Lemma 3 (Complexities undec-justification).

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ :

If the complexity of σ-credulous- in - justification is $\mathcal{C}$ , then the complexity of σ-sceptical- undec - justification is co- $\mathcal{C}$ ; and

If the complexity of σ-sceptical- in - justification is $\mathcal{C}$ , then the complexity of σ-credulous- undec - justification is co- $\mathcal{C}$ .

Proof sketch.

We give a proof sketch for the first item here and refer to the full proofs for both items to Appendix A. The first item can be proved by two reductions:

Each instance ${\mathit{I}}_1=\mathrm{(}⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩\mathrm{,}\mathit{A}\mathrm{)}$ of σ-credulous-in-justification can, in polynomial time, be converted to an instance ${\mathit{I}}_2=\mathrm{(}⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}$ of σ-sceptical-undec-justification where, by Lemma 2 item 1, ${\mathit{I}}_1$ is a positive instance iff ${\mathit{I}}_2$ is a negative instance.

Similarly, each instance ${\mathit{I}}_1=\mathrm{(}⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩\mathrm{,}\mathit{A}\mathrm{)}$ of σ-sceptical-undec-justification can, in polynomial time, be converted to an instance ${\mathit{I}}_2=\mathrm{(}⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}$ of σ-credulous-in-justification where, by Lemma 2 item 4, ${\mathit{I}}_1$ is a positive instance iff ${\mathit{I}}_2$ is a negative instance.

 □

Using Lemma 3, we can now directly derive justification statuses for undec-justification under cp, gr and pr semantics in Propositions 1, 2 and 3.

Proposition 1.

cp -credulous- undec - justification , gr -credulous- undec - justification and gr -sceptical- undec - justification are P-complete.

Proof.

This follows directly from Lemma 3 in combination with P-completeness of cp-sceptical-in-justification, gr-sceptical-in-justification and gr-credulous-in-justification [10] and the fact that P = CoP. □

Proposition 2.

cp -sceptical- undec - justification and pr -sceptical- undec - justification are CoNP-complete.

Proof.

This follows directly from Lemma 3 and the fact that cp-credulous-in-justification and pr-credulous-in-justification are NP-complete [8,9]. □

Proposition 3.

pr -credulous- undec - justification is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proof.

This follows directly from Lemma 3 and the fact that pr-sceptical-in-justification is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete [11]. □

For st semantics, the situation is different, since for each st extension S, each argument is either in S or attacked by some argument in S. In the remainder of this section, we give the complexity results of undec-justification for st semantics.

Proposition 4.

st -credulous- undec - justification and st -sceptical-existent- undec - justification are trivial.

Proof.

In each st extension S, each argument is either in S or attacked by some argument in S. Consequently, each instance of st-credulous-undec-justification or st-sceptical-existent-undec-justification is False. □

In addition, an argument can only be st-sceptical-undec in a given argumentation framework AF if AF does not have any st extension.

Proposition 5.

st -sceptical- undec - justification is CoNP-complete.

Proof.

For each AF $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ and argument $\mathit{A}\in \mathcal{A}$ , A is st-sceptical-undec in $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ iff no stable extension exists for $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ . The problem of deciding if a given AF has a stable extension is NP-complete [9], so the complementary problem of deciding if an AF has no stable extension is CoNP-complete. □

At this point, we have studied the complexity of the justification problem for $\mathrm{\text{GR}}$ , $\mathrm{\text{CP}}$ , $\mathrm{\text{PR}}$ and $\mathrm{\text{ST}}$ semantics, for sceptical and credulous (and sceptical-existent of st semantics) acceptance and labels in, out and undec. These results are summarised in Table 2. In the following sections, we will see that these definitions and complexity results can be used for defining and studying the complexity of the stability and relevance problems.

Table 2

Overview of all complexity results related to justification. If a reference is specified, this complexity result is trivial from an earlier result in the literature. New results are printed bold; we refer to the corresponding proposition by “P” and the proposition number. Full proofs for each of the propositions are presented in the appendix. The complexities for in- and out-justification are the same; this follows from Lemma 1

4. Stability

In this section, we will formally define stability and study its complexity. Stability can be seen as a dynamic variant of justification, defined on incomplete argumentation frameworks: whereas the notion of justification only takes certain arguments and attacks into account, the notion of stability also considers arguments and attacks for which their presence is still uncertain. Whereas justification status is defined on arguments in an abstract argumentation framework, stability status is defined on certain arguments in an incomplete argumentation framework. Informally, a certain argument is stable if its justification is the same in all completions of the IAF. In the definition below, we define j-stability based on j-justification, where j can be any justification status considered in the previous section: $\mathit{j}\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}\times \{\text{sceptical}\mathrm{,}\text{credulous}\mathrm{,}\text{sceptical-existent}\}\times \{\mathrm{\text{IN}}\mathrm{,}\mathrm{\text{OUT}}\mathrm{,}\mathrm{\text{UNDEC}}\}$ .

Definition 8 (Stability on IAFs).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ and some justification status j, A is stable-j w.r.t. $\mathcal{I}$ iff A is j in each completion of $\mathcal{I}$ .

Example 7 (Stability).

We reconsider the incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ from Example 3. The arguments in $\mathcal{A}$ are B, C and E. Figure 7 illustrates the complete in/out/undec-labellings of each of the completions ( ${\mathit{\text{AF}}}_1\mathrm{,}\dots \mathrm{,}{\mathit{\text{AF}}}_8$ ) of $\mathcal{I}$ . For each of these eight AFs, each complete extension is represented by colouring the argument nodes: nodes corresponding to arguments in the extension are coloured green and with boldface font; arguments attacked by an argument in the extension are coloured red and with italic font; all other arguments are yellow and with regular font. Note that for each completion of $\mathcal{I}$ , there is at least one complete extension containing E. In other words: E is stable-cp-credulous-in. Similarly, for each completion of $\mathcal{I}$ , there is at least one preferred and stable extension containing E, so E is stable-pr-credulous-in and stable-st-credulous-in as well. Under grounded semantics, E is not stable-in, since there are completions (such as ${\mathit{\text{AF}}}_1$ ) for which E is not in the grounded extension.

For each $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ , there is no argument that is stable-σ-sceptical-in, -out or -undec. In practice, this means that a sceptical reasoner interested in one of the arguments in $\mathcal{A}$ would require more information.

Fig. 7.

Visualisation of the complete in/out/undec-labellings of each of the eight unique completions of $\mathcal{I}$ , where the argumentation framework is repeated for each cp extension. Arguments that are in that extension are coloured green and with boldface font; argument attacked by some argument in that extension are red and with italic font; and all other arguments are yellow and with regular font.

Finally recall that stability is not defined for A and D, since they are in ${\mathcal{A}}^{?}$ rather than $\mathcal{A}$ . So although the argument A is in each gr, cp, pr and st extension in each completion in which the argument exists, it is not stable-gr/cp/pr/st-sceptical/credulous-in because there are completions that do not contain A.3

³

One may also be interested in an alternative notion of stability for uncertain arguments, which we call existent-stability here: an uncertain argument $\mathit{A}\in {\mathcal{A}}^{?}$ is j-existent-stable w.r.t. some IAF $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ if it has justification status j in all completions $⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ such that $\mathit{A}\in {\mathcal{A}}^{\prime }$ . Note that the set of completions $⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ of $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ such that $\mathit{A}\in {\mathcal{A}}^{\prime }$ equals the set of completions of $⟨\mathcal{A}\cup \{\mathit{A}\}\mathrm{,}{\mathcal{A}}^{?}\setminus \{\mathit{A}\}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Therefore, $\mathit{A}\in {\mathcal{A}}^{?}$ is j-existent-stable w.r.t. some $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ iff A is j-stable w.r.t. $⟨\mathcal{A}\cup \{\mathit{A}\}\mathrm{,}{\mathcal{A}}^{?}\setminus \{\mathit{A}\}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Analogously, $\mathit{B}\in \mathcal{A}$ is j-stable w.r.t. some $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ iff B is j-existent-stable w.r.t. $⟨\mathcal{A}\setminus \{\mathit{B}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{B}\}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ . This implies that the problem of deciding j-existent-stability is in the same complexity class as the problem of deciding j-stability.

Note that the notion of stability is strongly related to the notion of necessary acceptance, defined in Section 2. In fact, for any semantics σ, certain arguments are stable-σ-sceptical-in if and only if they are necessarily sceptically accepted (i.e. in each extension of each completion); similarly, certain arguments are stable-σ-credulous-in if and only if they are necessarily credulously accepted (i.e. in some extension of each completion). However, stability provides a more fine-grained notion of (non-)acceptance in IAFs than necessary acceptance. Using (out-)stability, it is, for example, also possible to express that, in any completion, some certain argument is attacked by an argument (not necessarily the same) in a σ-extension of that completion.

In the remainder of this section, we present our results on the complexity of the task of identifying a stability status. The following formulates this task as a decision problem.

j-stability
Given:	An incomplete argumentation framework $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a justification status j and an argument $\mathit{A}\in \mathcal{A}$
Question:	Does A’s stability status w.r.t. $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ equal stable-j?

Next, we give complexity results for variants of the stability problem. We start with relating in-stability to necessary (sceptical and credulous) acceptance, as defined in Definition 5 (which was adapted from [3]).

Lemma 4.

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and $\mathit{c}\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\}$ , the complexity of σ-c- in - stability equals the complexity of necessary c acceptance w.r.t. semantics σ.

Proof.

This is trivial from Definition 8 of stability and Definition 5 of necessary acceptance. □

We continue with relating in- and out-stability. Similar to what we did for in- and out-justification in Lemma 1, we show that the complexity of in-stability is the same as the complexity of out-stability.

Lemma 5.

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and $\mathit{c}\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\}$ , the complexity of σ-c- out - stability equals the complexity of σ-c- in - stability .

Proof sketch.

We prove this by a reduction from σ-c-out-stability to σ-c-in-stability and by a reduction in the other direction. Below, we give proof sketch; the full proof can be found in Appendix B.

For each instance $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ of the σ-c-out-stability problem where $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and $\mathit{A}\in \mathcal{A}$ , one can construct ${\mathcal{I}}^{\ast }=⟨\mathcal{A}\cup \{\mathit{B}\}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ , where $\mathit{B}\notin \mathcal{A}\cup {\mathcal{A}}^{?}$ . Then $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ is a positive instance of σ-c-out-stability iff $\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{,}\mathit{B}\mathrm{)}$ is a positive instance of σ-c-in-stability.

Similarly, each instance $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ of the σ-c-in-stability problem, where $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and $\mathit{A}\in \mathcal{A}$ , can be transformed into $\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{,}\mathit{B}\mathrm{)}$ where ${\mathcal{I}}^{\ast }=⟨\mathcal{A}\cup \{\mathit{B}\}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ with $\mathit{B}\notin \mathcal{A}\cup {\mathcal{A}}^{?}$ . The instance $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ is positive for σ-c-in-stability iff $\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{,}\mathit{B}\mathrm{)}$ is a positive instance for σ-c-out-stability.

From these two reductions, it follows that σ-c-in-stability and σ-c-out-stability have the same complexity. □

Using Lemma 5, we can show that for any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}$ and $\mathit{c}\in \{\text{sceptical}\mathrm{,}\text{credulous}\}$ , we can derive the complexity of σ-c-out-stability directly from the complexity of σ-c-in-stability. In the following lemma, we relate undec-stability for specific semantics with possible sceptical and credulous acceptance (Definition 6). Similar to Lemma 2, we prove this for gr, cp and pr semantics but not for st semantics: the relation does not hold for st semantics because arguments cannot be st-credulous-undec.

Lemma 6 (Complexities undec-stability).

For any given $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ :

If possible credulous acceptance w.r.t. σ semantics is in the complexity class $\mathcal{C}$ , then σ-sceptical- undec - stability is in the complexity class co- $\mathcal{C}$ ; and

If possible sceptical acceptance w.r.t. σ semantics is in the complexity class $\mathcal{C}$ , then σ-credulous- undec - stability is in the complexity class co- $\mathcal{C}$ .

Proof sketch.

We only give a proof sketch for the first item here; full proofs of both items are in Appendix B. This proof consists of two reductions: we show that possible credulous acceptance w.r.t. σ semantics reduces to the complementary problem of σ-sceptical-undec-stability and the other way around. The proof strategy is similar to the proof of Lemma 2, illustrated in Fig. 6.

Let ${\mathit{I}}_1=\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ where $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and $\mathit{A}\in \mathcal{A}$ . Construct ${\mathit{I}}_2=\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}$ where ${\mathcal{I}}^{\ast }=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ and ${\mathit{A}}^{\prime }\notin \mathcal{A}\cup {\mathcal{A}}^{?}$ . Then ${\mathit{I}}_1$ is a positive instance of possible credulous acceptance w.r.t. σ semantics iff ${\mathit{I}}_2$ is a negative instance of σ-sceptical-undec-stability.

Let ${\mathit{I}}_1=\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ where $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and $\mathit{A}\in \mathcal{A}$ . Now let ${\mathit{I}}_2=\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}$ where ${\mathcal{I}}^{\ast }=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ and none of ${\mathit{A}}^{\prime }$ , B and C is in $\mathcal{A}\cup {\mathcal{A}}^{?}$ . ${\mathit{I}}_1$ is a positive instance of σ-sceptical-undec-stability iff ${\mathit{I}}_2$ is a negative instance of possible credulous acceptance w.r.t. σ semantics.

 □

The results of Lemma 6 can be used to derive the complexity classes of undec-stability based on existing results for possible acceptance from [3] for cp, gr and pr semantics.

Proposition 6.

gr -sceptical- undec - stability , gr -credulous- undec - stability and cp -credulous- undec - stability are CoNP-complete.

Proof.

This follows directly from Lemma 6 and the fact that possible sceptical acceptance under gr and cp semantics and possible credulous acceptance under gr semantics are NP-complete [3]. □

Proposition 7.

cp -sceptical- undec - stability and pr -sceptical- undec - stability are CoNP-complete.

Proof.

This follows directly from Lemma 6 and the fact that possible credulous acceptance under cp and pr semantics are NP-complete [3]. □

Proposition 8.

pr -credulous- undec - stability is ${\mathrm{\Pi }}_3^{\mathit{p}}$ -complete.

Proof.

This follows directly from Lemma 6 and the fact that possible sceptical acceptance under pr semantics is ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete [3]. □

Finally, we turn to st semantics. Our strategy for proving these complexities is similar to our approach for the st-undec-justification complexity proofs in the previous section.

Proposition 9.

st -sceptical- undec - stability is CoNP-complete.

Proof.

The problem is in CoNP, as a negative instance $\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩\mathrm{,}\mathit{A}\mathrm{)}$ can be verified in polynomial time given a certificate $\mathrm{(}{\mathit{\text{AF}}}^{\prime }\mathrm{,}\mathit{S}\mathrm{)}$ such that ${\mathit{\text{AF}}}^{\prime }$ is a completion of $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , $\mathit{A}\in \mathcal{A}$ and S is a st extension of ${\mathit{\text{AF}}}^{\prime }$ . If S is a st extension then each argument in $\mathcal{A}$ , including A, is either in S or attacked by S; therefore A cannot be stable-st-sceptical-undec w.r.t. $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

For hardness, we can reduce from the CoNP-complete problem st-sceptical-undec-justification: any instance ${\mathit{I}}_1=\mathrm{(}⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩\mathrm{,}\mathit{A}\mathrm{)}$ of st-sceptical-undec-justification can be solved by solving st-sceptical-undec-stability for ${\mathit{I}}_2=\mathrm{(}⟨\mathcal{A}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{,}\mathit{A}\mathrm{)}$ . Given that $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ is the only completion of $⟨\mathcal{A}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩$ , ${\mathit{I}}_1$ is positive iff ${\mathit{I}}_2$ is positive. □

Proposition 10.

st -credulous- undec - stability and st -sceptical-existent- undec - stability are trivial.

Proof.

For each argumentation framework $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ such that a st extension S exists, each argument in $\mathcal{A}$ is either in S or attacked by an argument in S. Therefore, A cannot be st-credulous-undec or st-sceptical-existent-undec in $\mathit{\text{AF}}$ . This applies for each AF, including all completions of each possible IAF, so each instance of st-credulous-undec-stability and st-sceptical-existent-undec-stability must be negative. □

To conclude this section, we have studied the complexity of the stability problem for gr, cp, pr and st semantics, for sceptical and credulous (and sceptical-existent for st semantics) acceptance and labels in, out and undec. For an overview of the results, we refer to Table 3. In the following section, we consider the problem of identifying relevance.

Table 3

Overview of all complexity results related to stability. If a reference is specified, this complexity result is trivial from an earlier result in the literature. New results are printed bold; we refer to the corresponding proposition by “P” and the proposition number. Full proofs for each of the propositions are presented in Appendix B. The complexities for in- and out-stability are the same; this follows from Lemma 5

5. Relevance

For IAFs in which a given argument is not stable, a natural follow-up question would be: which uncertainties should be resolved in order to reach a point where the argument is stable? These uncertainties are relevant to investigate in the given IAF. In this section, we will define the problem of relevance and study its complexity. First, we give some intuition on the notion of relevance in the context of stability.

Fig. 8.

Illustration of the IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ from Example 3.

Example 8.

We return to the IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ from Example 3, which is shown in Fig. 8 (which is a repetition of Fig. 2). Suppose that we want to know how we can make the certain argument C stable-gr-sceptical-in. In order to do so, we should make sure that argument B is stable-gr-sceptical-out, which can only be the case if it is attacked by argument A. So in order to make sure that C is stable-gr-sceptical-in, we need to make sure that argument A is present. In addition, argument C is attacked by the uncertain argument D. If argument D turns out to be present, then C cannot be stable-gr-sceptical-in as there is no suitable argument to defend C from D under grounded semantics. Therefore it is relevant to make sure that argument D is absent. To conclude, the two relevant operations in this case are adding argument A and removing argument D. Note that there is still some uncertainty left in the resulting IAF: it is still unknown if the attack $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ should be present or absent. However, adding or removing this attack does not influence the gr-sceptical-in-stability status of C. Therefore, these operations are not relevant.

The example showed that being certain about the existence of the attack $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ does not contribute anything to the stability status of C in a situation where we already know that A is present and D is absent: both with and without $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ , C is stable-gr-sceptical-in. In general, adding or removing an argument or attack is only relevant if there is a situation in which this argument or attack is really necessary to obtain stability. In order to define which uncertainties are relevant to be resolved for obtaining some stability status, we therefore need some notion of “partial” completions, in which only those uncertainties are resolved that are required for stability. A partial completion of an IAF $\mathcal{I}$ is an IAF ${\mathcal{I}}^{\prime }$ such that a (possibly empty) part of the uncertain elements of $\mathcal{I}$ is resolved in ${\mathcal{I}}^{\prime }$ , while another (possibly empty) part of the uncertain elements is still uncertain.4

⁴

Partial completions in this paper are a corrected version of specifications in [18].

Next, we formally define such partial completions.

Definition 9 (Partial completion).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a partial completion is an IAF ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?\prime }\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?\prime }⟩$ , where:

$\mathcal{A}\subseteq {\mathcal{A}}^{\prime }\subseteq \mathcal{A}\cup {\mathcal{A}}^{?}$ ;

$\mathcal{R}{|}_{\mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}}\subseteq {\mathcal{R}}^{\prime }\subseteq \mathrm{(}\mathcal{R}\cup {\mathcal{R}}^{?}\mathrm{)}{|}_{\mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}}$ ;

${\mathcal{A}}^{?\prime }\subseteq {\mathcal{A}}^{?}$ ;

${\mathcal{R}}^{?\prime }\subseteq {\mathcal{R}}^{?}$ .

Note that, since ${\mathcal{I}}^{\prime }$ is an IAF, it must still hold that ${\mathcal{A}}^{\prime }\cap {\mathcal{A}}^{?\prime }=\varnothing$ ; ${\mathcal{R}}^{\prime }\cap {\mathcal{R}}^{?\prime }=\varnothing$ ; ${\mathcal{R}}^{\prime }\subseteq \mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}\times \mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}$ and ${\mathcal{R}}^{?\prime }\subseteq \mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}\times \mathrm{(}{\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\mathrm{)}$ . We denote all possible partial completions for $\mathcal{I}$ by $\mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ .

In order to be able to apply the semantics of [10], which are defined on AFs, to IAFs, we define the certain projection of an IAF. This is an AF consisting of only the IAF’s certain arguments and the attacks between them.

Definition 10 (Certain projection).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , the certain projection $\mathtt{\text{cert}}\mathrm{(}\mathcal{I}\mathrm{)}$ is the argumentation framework $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}{|}_{\mathcal{A}}⟩$ .

Example 9 (Partial completions and certain projections).

Returning to the IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , given in Example 3 and illustrated in Fig. 8, the following IAFs are some (but not all) examples of partial completions in $\mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ :

${\mathcal{I}}_1=⟨\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}\cup {\mathcal{R}}^{?}\mathrm{,}\varnothing ⟩$ : all uncertain arguments and attacks have become certain.

${\mathcal{I}}_2=⟨\mathcal{A}\mathrm{,}\varnothing \mathrm{,}\{\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}\mathrm{,}\varnothing ⟩$ : all uncertain arguments and attacks are removed, as well as all attacks that are not in the restriction of $\mathcal{R}$ to $\mathcal{A}$ .

${\mathcal{I}}_3=⟨\mathcal{A}\cup \{\mathit{A}\}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ : the argument A is moved from the uncertain to the certain part. The argument D and the attack $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ are still uncertain.

Fig. 9.

Three partial completions of our incomplete argumentation framework and their certain projections.

The partial completions ${\mathcal{I}}_1$ , ${\mathcal{I}}_2$ and ${\mathcal{I}}_3$ are illustrated on the left side of Fig. 9. The certain projection of ${\mathcal{I}}_1$ is $⟨\mathcal{A}\cup {\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\cup {\mathcal{R}}^{?}⟩$ . For ${\mathcal{I}}_2$ , the certain projection is $⟨\mathcal{A}\mathrm{,}\{\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}⟩$ . Finally, $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}_3\mathrm{)}=⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{)}\}⟩$ . These AFs are illustrated on the right side of Fig. 9.

Before proceeding to a formal definition of relevance that matches the intuitions in the example above, we define the notion of minimal stable partial completions. In this definition, j refers to the justification status: $\mathit{j}\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\mathrm{,}\mathrm{\text{ST}}\}\times \{\text{sceptical}\mathrm{,}\text{credulous}\mathrm{,}\text{sceptical-existent}\}\times \{\mathrm{\text{IN}}\mathrm{,}\mathrm{\text{OUT}}\mathrm{,}\mathrm{\text{UNDEC}}\}$ .

Definition 11 (Minimal stable-j partial completion).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ and a justification status j, a minimal stable-j partial completion for A w.r.t. $\mathcal{I}$ is a partial completion ${\mathcal{I}}^{\prime }$ in $\mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is stable-j in ${\mathcal{I}}^{\prime }$ and there is no partial completion ${\mathcal{I}}^{″}$ in $\mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is stable-j in ${\mathcal{I}}^{″}$ , ${\mathcal{I}}^{″}\ne {\mathcal{I}}^{\prime }$ and ${\mathcal{I}}^{\prime }\in \mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{″}\mathrm{)}$ .

Intuitively, the minimal stable-j partial completion for A is a partial completion in which A is stable-j, while A would not be stable-j in any partial completion with more uncertain elements.

Example 10 (Minimal stable-j partial completion).

Recall the IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ from Example 3. Suppose that we are interested to know if argument C is stable-gr-sceptical-in. $\mathcal{I}$ has one minimal stable-gr-sceptical-in partial completion, which is ${\mathcal{I}}_4=⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\varnothing \mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Given that ${\mathcal{R}}^{?}$ contains the attack $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ as its only uncertain element, ${\mathcal{I}}_4$ has three partial completions, resulting in two unique certain projections. These are $⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}⟩$ (depicted as ${\mathit{\text{AF}}}_2$ in Fig. 7) and $⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}⟩$ (depicted as ${\mathit{\text{AF}}}_4$ in the same figure). Since ${\mathit{\text{AF}}}_2$ and ${\mathit{\text{AF}}}_4$ each have a grounded extension – in both cases $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ – that contains C, C is stable-gr-sceptical-in in ${\mathcal{I}}_4$ . In addition, note that ${\mathcal{I}}_4$ is minimal in that C would not be stable-gr-sceptical-in in partial completions with more uncertain elements:

Suppose that the presence of argument A is unknown as in ${\mathcal{I}}_5=⟨\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathit{A}\}\mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}⟩$ . Then ${\mathit{\text{AF}}}_6$ and ${\mathit{\text{AF}}}_8$ would be certain projections of partial completions of ${\mathcal{I}}_5$ . Since C is not in the grounded extension of each of these AFs, C is not stable-gr-sceptical-in w.r.t. ${\mathcal{I}}_5$ .

Alternatively, suppose that the absence of argument D is yet unknown, as in ${\mathcal{I}}_3$ , defined earlier as $⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathit{D}\}\mathrm{,}\mathcal{R}\mathrm{,}\{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}⟩$ . Then ${\mathit{\text{AF}}}_1$ and ${\mathit{\text{AF}}}_3$ would also be certain projections of partial completions of ${\mathcal{I}}_3$ , where these AFs would not have C in their grounded extensions. Therefore, C is not stable-gr-sceptical-in w.r.t. ${\mathcal{I}}_3$ .

This shows that ${\mathcal{I}}_4$ is a minimal stable-gr-sceptical-in partial completion for C w.r.t. $\mathcal{I}$ . Note that, although in this case there is a single minimal stable-gr-sceptical-in partial completion for C w.r.t. $\mathcal{I}$ , in general there can be multiple minimal stable partial completions.

For example, there are three minimal stable-cp-credulous-undec partial completions for C w.r.t. $\mathcal{I}$ :

$⟨\mathcal{A}\cup \{\mathit{A}\mathrm{,}\mathit{D}\}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}\mathrm{,}\{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}⟩$ (having ${\mathit{\text{AF}}}_1$ and ${\mathit{\text{AF}}}_3$ as certain projections of partial completions);

$⟨\mathcal{A}\cup \{\mathit{D}\}\mathrm{,}\{\mathit{A}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}\mathrm{,}\varnothing ⟩$ (for ${\mathit{\text{AF}}}_1$ and ${\mathit{\text{AF}}}_5$ ); and

$⟨\mathcal{A}\mathrm{,}\{\mathit{D}\}\mathrm{,}\mathcal{R}\setminus \{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\}\cup \{\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}\}\mathrm{,}\varnothing ⟩$ (for ${\mathit{\text{AF}}}_5$ and ${\mathit{\text{AF}}}_6$ ).

Using the notion of minimal stable-j partial completions, we can now define j-relevance.

Definition 12 (j-relevance).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , an argument $\mathit{A}\in \mathcal{A}$ , an uncertain argument or attack $\mathit{U}\in {\mathcal{A}}^{?}\cup {\mathcal{R}}^{?}$ and a justification status j,

Addition of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there is a minimal stable-j partial completion ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?\prime }\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?\prime }⟩$ for A w.r.t. $\mathcal{I}$ such that $\mathit{U}\in {\mathcal{A}}^{\prime }\cup {\mathcal{R}}^{\prime }$ ; and

Removal of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there is a minimal stable-j partial completion ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?\prime }\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?\prime }⟩$ for A w.r.t. $\mathcal{I}$ such that $\mathit{U}\notin {\mathcal{A}}^{\prime }\cup {\mathcal{A}}^{?\prime }\cup {\mathcal{R}}^{\prime }\cup {\mathcal{R}}^{?\prime }$ .

In other words, addition of an uncertain element U is j-relevant if a minimal stable-j partial completion can be reached by moving U from the uncertain to the certain part of the IAF $\mathcal{I}$ ; and removal of U is j-relevant if completely removing U from $\mathcal{I}$ , possibly in combination with other actions, leads to a minimal stable-j partial completion.

Fig. 10.

Partial completion ${\mathcal{I}}_4$ , which is the only minimal stable-gr-sceptical-in partial completion for C w.r.t. $\mathcal{I}$ where $\mathcal{I}=⟨\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathit{A}\mathrm{,}\mathit{E}\}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and ${\mathcal{I}}_4=⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\varnothing \mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

Example 11 (j-relevance).

To illustrate j-relevance, we build on the minimal stable-j partial completions from Example 10. Recall that ${\mathcal{I}}_4$ , illustrated in Fig. 10, is the only minimal stable-gr-sceptical-in partial completion for C w.r.t. $\mathcal{I}$ where $\mathcal{I}=⟨\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\{\mathit{A}\mathrm{,}\mathit{D}\}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ and ${\mathcal{I}}_4=⟨\{\mathit{A}\mathrm{,}\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}\mathrm{,}\varnothing \mathrm{,}\{\mathrm{(}\mathit{A}\mathrm{,}\mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Given that A was an uncertain argument in $\mathcal{I}$ and is a certain argument in (the minimal stable-gr-sceptical-in partial completion) ${\mathcal{I}}_4$ , addition of A is gr-sceptical-in-relevant for C w.r.t. $\mathcal{I}$ . Furthermore, as D was an uncertain argument in $\mathcal{I}$ and is no longer present in ${\mathcal{I}}_4$ , the removal of D is gr-sceptical-in-relevant for C w.r.t. $\mathcal{I}$ .

Considering the justification status cp-credulous-undec, there are three minimal stable-cp-credulous-undec partial completions for C (see Example 10). The cp-credulous-undec-relevant operations are:

Addition of A;

Addition of D;

Addition of $\mathrm{(}\mathit{C}\mathrm{,}\mathit{B}\mathrm{)}$ ; and

Removal of A.

Note that this example shows the possibility that both the addition and removal of some uncertain argument or attack are relevant. This example also demonstrates that performing a relevant action does not necessarily lead to a stable situation, but may be just the first step in becoming stable. For instance, the addition of A to $\mathcal{I}$ does not yet result in an IAF that is stable-cp-credulous-undec as this IAF still has at least one completion (to be precise, the completions ${\mathit{\text{AF}}}_2$ and ${\mathit{\text{AF}}}_4$ in Fig. 7) in which C is not cp-credulous-undec. In order to become stable, an additional relevant action (in this case, the addition of D) is required.

Like for justification and stability status, we formulate the identification of j-relevance as a decision problem:

j-relevance of action a
Given:	An incomplete argumentation framework $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a justification status j, an action $\mathbf{\text{a}}\in \{\mathit{\text{addition}}\mathrm{,}\mathit{\text{removal}}\}$ , an argument $\mathit{A}\in \mathcal{A}$ and an uncertain argument or attack $\mathit{U}\in {\mathcal{A}}^{?}\cup {\mathcal{R}}^{?}$ .
Question:	Is a of U j-relevant for A w.r.t. $⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ ?

In the remainder of this section, we study the complexity of relevance for complete, grounded, preferred and stable semantics. This work builds on initial research in [18], where we proved the complexity of in-relevance under grounded semantics. In order to prove complexity of j-relevance for each justification status j, we first give proofs for the upper bounds, that is: the membership in a given complexity class, in Section 5.1. Subsequently, we provide lower bounds, that is: hardness results, for relevance under grounded, complete and preferred semantics in Section 5.2. Finally, we prove the remaining hardness results for stable semantics in Section 5.3.

5.1. Upper bounds

First, we will prove a general upper bound on j-relevance. In order to do so, we first prove Lemma 7. This lemma shows that the relevance of adding an uncertain argument can be validated by checking the justification status of the certain projections of two particular future partial completions.

Lemma 7.

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ and a justification status j:

For each $\mathit{U}\in {\mathcal{A}}^{?}$ , addition of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there exists some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\in \mathit{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is not j in the certain projection of ${\mathcal{I}}^{\prime }$ , while A is j in the certain projection of $⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩$ .

For each $\mathit{U}\in {\mathcal{R}}^{?}$ , addition of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there exists some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\{\mathit{U}\}⟩\in \mathit{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is not j in the certain projection of ${\mathcal{I}}^{\prime }$ , while A is j in the certain projection of $⟨{\mathcal{A}}^{\prime }\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing ⟩$ .

For each $\mathit{U}\in {\mathcal{A}}^{?}$ , removal of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there exists some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\in \mathit{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is j in the certain projection of ${\mathcal{I}}^{\prime }$ , while A is not j in the certain projection of $⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩$ .

For each $\mathit{U}\in {\mathcal{R}}^{?}$ , removal of U is j-relevant for A w.r.t. $\mathcal{I}$ iff there exists some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\in \mathit{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is j in the certain projection of ${\mathcal{I}}^{\prime }$ , while A is not j in the certain projection of $⟨{\mathcal{A}}^{\prime }\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing ⟩$ .

Proof sketch.

Let $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ be an incomplete argumentation framework, $\mathit{A}\in \mathcal{A}$ a certain argument and j a justification status. We prove both directions of the first item here. For proofs for the other items, we refer to Appendix C. ⇒

See Fig. 11 for an illustration of the steps in this proof.

Suppose that addition of $\mathit{U}\in {\mathit{A}}^{?}$ is j-relevant for A w.r.t. $\mathcal{I}$ .

Then by Definition 12 there is a minimal stable-j partial completion ${\mathcal{I}}^{\ast }=⟨{\mathcal{A}}^{\ast }\mathrm{,}{\mathcal{A}}^{?\ast }\mathrm{,}{\mathcal{R}}^{\ast }\mathrm{,}{\mathcal{R}}^{?\ast }⟩$ for A w.r.t. $\mathcal{I}$ such that $\mathit{U}\in {\mathcal{A}}^{\ast }$ .

Now construct the IAF ${\mathcal{I}}^{\prime }$ from ${\mathcal{I}}^{\ast }$ by moving U from the certain to the uncertain part: ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\ast }\setminus \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?\ast }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\ast }\mathrm{,}{\mathcal{R}}^{?\ast }⟩$ .

Given that ${\mathcal{I}}^{\ast }$ was minimal and ${\mathcal{I}}^{\ast }\in \mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ , A cannot be stable-j w.r.t. ${\mathcal{I}}^{\prime }$ . So there must be some ${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{″}\mathrm{,}{\mathcal{A}}^{?″}\mathrm{,}{\mathcal{R}}^{″}\mathrm{,}{\mathcal{R}}^{?″}⟩$ in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ such that A’s justification status in the certain projection of ${\mathcal{I}}^{″}$ is not j – note that this means that U is not in ${\mathcal{A}}^{″}$ (since A was stable-j in ${\mathcal{I}}^{\ast }$ ).

Then A’s justification status in the certain projection of ${\mathcal{I}}^{‴}=⟨{\mathcal{A}}^{″}\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{″}\mathrm{,}\varnothing ⟩$ is not j (because this is the same as the certain projection of ${\mathcal{I}}^{″}$ , i.e. $⟨{\mathcal{A}}^{″}\mathrm{,}{\mathcal{R}}^{″}{|}_{{\mathcal{A}}^{″}}⟩$ ).

Next, construct ${\mathcal{I}}^{\ast \prime }=⟨{\mathcal{A}}^{″}\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{″}\mathrm{,}\varnothing ⟩$ from ${\mathcal{I}}^{‴}$ by moving U from the uncertain part to the certain part. Since ${\mathcal{I}}^{\ast \prime }$ is in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{\ast }\mathrm{)}$ and A is stable-j in ${\mathcal{I}}^{\ast }$ , A must be j in the certain projection of ${\mathcal{I}}^{\ast \prime }$ .

⇐

Suppose that there exists some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\in \mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ such that A is not j in $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ and A is j in $\mathtt{\text{cert}}\mathrm{(}⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\mathrm{)}$ . Given that $⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩$ has only one completion (i.e., its certain projection), A must be stable-j w.r.t. $⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩$ . Consequently, there must be some minimal stable-j partial completion ${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{″}\mathrm{,}{\mathcal{A}}^{?″}\mathrm{,}{\mathcal{R}}^{″}\mathrm{,}{\mathcal{R}}^{?″}⟩$ for A w.r.t. $\mathcal{I}$ such that $⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\in \mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{″}\mathrm{)}$ . Note that $\mathit{U}\in {\mathcal{A}}^{″}$ : otherwise $⟨{\mathcal{A}}^{\prime }\mathrm{,}\varnothing \mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩$ would also be in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{″}\mathrm{)}$ , which contradicts the assumption that A is not j in $\mathtt{\text{cert}}\mathrm{(}⟨{\mathcal{A}}^{\prime }\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}\varnothing ⟩\mathrm{)}$ . To conclude, addition of U is j-relevant for A w.r.t. $\mathcal{I}$ .

 □

Fig. 11.

Illustration of the steps in the proof of Lemma 7 item 1 (from left to right). The IAFs used in the proof are depicted as rectangles; grey arrows between these rectangles represent partial completions – note that not all partial completions of all IAFs are shown in the figure, but only those that we refer to in the proof. Rectangles corresponding to ${\mathcal{I}}^{‴}$ and ${\mathcal{I}}^{\ast \prime }$ are coloured blue, as these are the partial completions of $\mathcal{I}$ for which Lemma 7 shows some properties.

In the following proposition, we use the results from Lemma 7 to prove a general upper bound on the complexity of j-relevance.

Proposition 11 (Upper bound j-relevance).

Given an IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ , an uncertain argument or attack $\mathit{U}\in {\mathcal{A}}^{?}\cup {\mathcal{R}}^{?}$ and a justification status j, if the problem of deciding j’s justification status in a given completion of $\mathcal{I}$ is in the complexity class $\mathcal{C}$ , then the problem of deciding if addition or removal of U is j-relevant for A w.r.t. $\mathcal{I}$ is in the complexity class ${\mathit{\text{NP}}}^{\mathcal{C}}$ .

Proof.

In order to validate that a given $\mathit{U}\in {\mathcal{A}}^{?}\cup {\mathcal{R}}^{?}$ is j-relevant for a given $\mathit{A}\in \mathcal{A}$ , a suitable polynomial-sized certificate would be some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?\prime }\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?\prime }⟩$ as specified in Lemma 7 (so ${\mathcal{A}}^{?\prime }\cup {\mathcal{R}}^{?\prime }=\{\mathit{U}\}$ ). The following procedure can be used to validate that U is j-relevant for A w.r.t. $\mathcal{I}$ :

Check in polynomial time if ${\mathcal{I}}^{\prime }\in \mathtt{\text{part}}\mathrm{(}\mathcal{I}\mathrm{)}$ and store the result in ${\mathit{r}}_1$ ;

Call the $\mathcal{C}$ oracle for finding justification status j to check if A is j w.r.t. $⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }{|}_{{\mathcal{A}}^{\prime }}⟩$ and store the result in ${\mathit{r}}_2$ ;

Let $\mathit{A}{\mathit{F}}^{\prime }=⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }{|}_{{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}}⟩$ if $\mathit{U}\in {\mathit{A}}^{?}$ and $\mathit{A}{\mathit{F}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\mathrm{(}{\mathcal{R}}^{\prime }\cup \{\mathit{U}\}\mathrm{)}{|}_{{\mathcal{A}}^{\prime }}⟩$ otherwise. Then call the $\mathcal{C}$ oracle to check if A is j w.r.t. $\mathit{A}{\mathit{F}}^{\prime }$ and store the result in ${\mathit{r}}_3$ .

Then by Lemma 7, addition of U is j-relevant for A w.r.t. $\mathcal{I}$ iff ${\mathit{r}}_1\wedge \neg {\mathit{r}}_2\wedge {\mathit{r}}_3$ . Removal of U is j-relevant for A w.r.t. $\mathcal{I}$ iff ${\mathit{r}}_1\wedge {\mathit{r}}_2\wedge \neg {\mathit{r}}_3$ . Checking that ${\mathit{r}}_1\wedge \neg {\mathit{r}}_2\wedge {\mathit{r}}_3$ (for addition) or $\mathcal{I}$ iff ${\mathit{r}}_1\wedge {\mathit{r}}_2\wedge \neg {\mathit{r}}_3$ (for removal) can be done in polynomial time. To conclude, the problem of deciding if addition or removal of U is j-relevant for A w.r.t. $\mathcal{I}$ is in ${\mathit{\text{NP}}}^{\mathcal{C}}$ . □

Proposition 11 gives a general upper bound that can be exploited to obtain an upper bound for j-relevance for all justification statuses for which we know the complexity of j-justification. For example, given that $\mathrm{\text{ST}}$ -credulous-in-justification is in NP, both the addition and the removal variants of $\mathrm{\text{ST}}$ -credulous-in-relevance must be in ${\mathit{\text{NP}}}^{\mathit{\text{NP}}}$ , so in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ . For justification statuses for which the justification problem is in P, like gr-credulous-in, the relevance problem is in $\mathit{\text{NP}}$ . If the justification problem is on the second level of the polynomial hierarchy, like pr-sceptical-out-justification, then the relevance variant is in ${\mathrm{\Sigma }}_3^{\mathit{p}}$ . Having proved the upper bounds for all variants of the relevance problem, we turn to the lower bounds in the following two sections.

5.2. Lower bounds for grounded, complete and preferred semantics

In order to prove lower bounds for relevance under gr, cp and pr semantics, we give reductions from the complementary problem of stability, to which we will refer as the instability problem.5

⁵

st semantics will be covered in Section 5.3.

More formally, for every IAF $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , justification status j and certain argument $\mathit{A}\in \mathcal{A}$ , the instance $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ is negative for j-stability iff it is positive for j-instability. In the following lemma, we provide some relations between instability and relevance that will turn out to be useful for reductions from instability to relevance for specific justification statuses.

Fig. 12.

Illustration of the IAFs that are used to show Lemma 8 item 1. The IAFs given on the left are ${\mathcal{I}}^{\prime }$ (upper) and ${\mathcal{I}}^{″}$ (lower). The rounded rectangle with dotted borders represents the original IAF $\mathcal{I}$ (without A and in- and outgoing attacks). The grey arrows point to certain projections ${\mathit{\text{AF}}}_1$ , ${\mathit{\text{AF}}}_2$ and ${\mathit{\text{AF}}}_3$ of partial completions. For each of these AFs, the possible justification statuses are colour-coded: green arguments with boldface font are in, yellow arguments are undec and red arguments with italic font are out. Note that, for a given justification status of A, there is only one possible justification status for each of the additional arguments in $\{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\mathrm{,}{\mathit{U}}^{\prime }\}$ .

Lemma 8 (Reduction instability to relevance).

Given an incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ , semantics $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ and $\mathit{c}\in \{\mathit{\text{sceptical}}\mathrm{,}\mathit{\text{credulous}}\}$ :

Construct ${\mathcal{I}}^{\prime }$ and ${\mathcal{I}}^{″}$ as follows (see Fig.  12 ), where ${\mathit{A}}^{\prime }$ , ${\mathit{A}}^{″}$ , U and ${\mathit{U}}^{\prime }$ are not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ :

${\mathcal{A}}^{\prime }=\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\}$ ;

${\mathcal{R}}^{\prime }=\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}$ ;

${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?}⟩$ ; and

${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

The following three items are equivalent:

• A is not stable-σ-c- in w.r.t. $\mathcal{I}$ ; and

• addition of U is σ-c- in -relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{\prime }$ ; and

• removal of ${\mathit{U}}^{\prime }$ is σ-c- in -relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{″}$ .

Let ${\mathcal{I}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{U}\mathrm{,}\mathit{A}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ and ${\mathcal{I}}^{″}=⟨\mathcal{A}\cup \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{U}\mathrm{,}\mathit{A}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ where U and ${\mathit{U}}^{\prime }$ are not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ . The following three items are equivalent:

• A is not stable-σ-c- out w.r.t. $\mathcal{I}$ ; and

• addition of U is σ-c- out -relevant for A w.r.t. ${\mathcal{I}}^{\prime }$ ; and

• removal of ${\mathit{U}}^{\prime }$ is σ-c- out -relevant for A w.r.t. ${\mathcal{I}}^{″}$ .

Construct ${\mathcal{I}}^{\prime }$ and ${\mathcal{I}}^{″}$ as follows, where ${\mathit{A}}^{\prime }$ , ${\mathit{A}}^{″}$ , U and ${\mathit{U}}^{\prime }$ are not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ :

${\mathcal{A}}^{\prime }=\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\}$ ;

${\mathcal{R}}^{\prime }=\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}\mathit{U}\mathrm{)}\}$ ;

${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?}⟩$ ; and

${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

The following three items are equivalent:

• A is not stable-σ-c- undec w.r.t. $\mathcal{I}$ ; and

• addition of U is σ-c- undec -relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{\prime }$ ; and

• removal of ${\mathit{U}}^{\prime }$ is σ-c- undec -relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{″}$ .

Proof sketch.

We only prove the first item here, related to in justification statuses. For the other items, see Appendix C. Let ${\mathcal{I}}^{\prime }=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ and let ${\mathcal{I}}^{″}=⟨\mathcal{A}\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ (see Fig. 12). (a) ⇒ (b) and (c)

If A is not stable-σ-c-in w.r.t. $\mathcal{I}$ (a) then by Definition 8 of stability there is some completion ${\mathit{\text{AF}}}^{\ast }=⟨{\mathcal{A}}^{\ast }\mathrm{,}{\mathcal{R}}^{\ast }⟩$ of $\mathcal{I}$ in which A is not σ-c-in. Next, we construct three argumentation frameworks based on $\mathit{\text{AF}}$ , containing the argument ${\mathit{A}}^{″}$ , and discuss its status.

First, construct ${\mathit{\text{AF}}}_1=⟨{\mathcal{A}}^{\ast }\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\}\mathrm{,}{\mathcal{R}}^{\ast }\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\}⟩$ . Given that ${\mathit{A}}^{″}$ is attacked by ${\mathit{A}}^{\prime }$ , which is only attacked by A in ${\mathit{\text{AF}}}_1$ , ${\mathit{A}}^{″}$ cannot be σ-c-in in ${\mathit{\text{AF}}}_1$ .

Next, construct ${\mathit{\text{AF}}}_2=⟨{\mathcal{A}}^{\ast }\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\ast }\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}⟩$ . ${\mathit{A}}^{″}$ is σ-c-in in ${\mathit{\text{AF}}}_2$ , since the unattacked argument U attacks the only attacker of ${\mathit{A}}^{″}$ (i.e. ${\mathit{A}}^{\prime }$ ).

Let ${\mathit{\text{AF}}}_3=⟨{\mathcal{A}}^{\ast }\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\mathrm{,}{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\ast }\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}⟩$ . Given that A is not σ-c-in in ${\mathit{\text{AF}}}^{\ast }$ , A cannot be σ-c-in in ${\mathit{\text{AF}}}_3$ either. Since the argument ${\mathit{A}}^{″}$ in ${\mathit{\text{AF}}}_3$ is attacked by ${\mathit{A}}^{\prime }$ , which is only attacked by A, ${\mathit{A}}^{″}$ cannot be σ-c-in in ${\mathit{\text{AF}}}_3$ .

Now item (b) (addition of U is σ-c-in-relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{\prime }$ ) follows from Lemma 7, the fact that the IAF $⟨{\mathcal{A}}^{\ast }\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\}\mathrm{,}\{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\ast }\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}\mathrm{,}\varnothing ⟩$ is in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ and the status of ${\mathit{A}}^{″}$ in ${\mathit{\text{AF}}}_1$ and ${\mathit{\text{AF}}}_2$ .

Similarly, item (c) (removal of ${\mathit{U}}^{\prime }$ is σ-c-in-relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{″}$ ) follows from Lemma 7, the fact that the IAF $⟨{\mathcal{A}}^{\ast }\cup \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\}\mathrm{,}\{{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\ast }\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}\varnothing ⟩$ is in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{″}\mathrm{)}$ and the status of ${\mathit{A}}^{″}$ in ${\mathit{\text{AF}}}_2$ and ${\mathit{\text{AF}}}_3$ .

(b) ⇒ (a)

If addition of U is σ-c-in-relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{\prime }$ then there is some ${\mathcal{I}}^{\ast \prime }$ in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ such that ${\mathit{A}}^{″}$ is not σ-c-in in $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}^{\ast \prime }\mathrm{)}=⟨{\mathcal{A}}^{\ast \prime }\mathrm{,}{\mathcal{R}}^{\ast \prime }⟩$ . Then A cannot be σ-c-in in $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}^{\ast \prime }\mathrm{)}$ either (since A attacks ${\mathit{A}}^{\prime }$ , which is the only attacker of ${\mathit{A}}^{″}$ ). Now construct ${\mathit{\text{AF}}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ where ${\mathcal{A}}^{\prime }={\mathcal{A}}^{\ast \prime }\setminus \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\}$ and ${\mathcal{R}}^{\prime }={\mathcal{R}}^{\ast \prime }\setminus \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}$ . Since A is not σ-c-in in $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}^{\ast \prime }\mathrm{)}$ , it cannot be σ-c-in in ${\mathit{\text{AF}}}^{\prime }$ . Given that ${\mathit{\text{AF}}}^{\prime }$ is a completion of $\mathcal{I}$ , A cannot be stable-σ-c-in w.r.t.  $\mathcal{I}$ .

(c) ⇒ (a)

If removal of ${\mathit{U}}^{\prime }$ is σ-c-in-relevant for ${\mathit{A}}^{″}$ w.r.t. ${\mathcal{I}}^{″}$ then by Lemma 7, there is some ${\mathcal{I}}^{\ast ″}$ in $\mathtt{\text{part}}\mathrm{(}{\mathcal{I}}^{″}\mathrm{)}$ such that ${\mathit{A}}^{″}$ is not σ-c-in in the certain projection of ${\mathcal{I}}^{\ast ″}$ – without loss of generality, let this certain projection be ${\mathit{\text{AF}}}^{\ast ″}=⟨{\mathcal{A}}^{\ast ″}\mathrm{,}{\mathcal{R}}^{\ast ″}⟩$ . Now construct ${\mathit{\text{AF}}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ where ${\mathcal{A}}^{\prime }={\mathcal{A}}^{\ast ″}\setminus \{{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}\mathrm{,}{\mathit{U}}^{\prime }\}$ and ${\mathcal{R}}^{\prime }={\mathcal{R}}^{\ast ″}\setminus \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}$ ; since ${\mathit{A}}^{″}$ is not σ-c-in in ${\mathit{\text{AF}}}^{\ast \prime }$ , it cannot be that A is σ-c-in in ${\mathit{\text{AF}}}^{\prime }$ . Given that ${\mathit{\text{AF}}}^{\prime }$ is a completion of $\mathcal{I}$ , A cannot be stable-σ-c-in w.r.t. $\mathcal{I}$ .

 □

Using Lemma 8 and the complexity results for stability from Section 4, we obtain lower bounds for both the addition and removal variants of relevance under complete, grounded and preferred semantics. For some variants of the relevance problem, combining the upper bounds identified in Section 5.1 with these lower bounds already yields tight complexity results. We present these results in Propositions 12, 13 and 14. The “easiest” of these problems are NP-complete, as we show in Proposition 12.

Proposition 12.

The following problems are NP-complete:

cp -credulous- undec - relevance ;

cp -sceptical- in - relevance ;

cp -sceptical- out - relevance ;

gr -credulous- in - relevance ;

gr -credulous- out - relevance ;

gr -credulous- undec - relevance ;

gr -sceptical- in - relevance ;

gr -sceptical- out - relevance ; and

gr -sceptical- undec - relevance .

Proof sketch.

For each of these problems, membership in NP follows from membership in P of the corresponding justification problems [10], listed in Table 1, and Proposition 11 (since $\text{NP}={\text{NP}}^{\text{P}}$ ).

For NP-hardness, we can give a reduction from the complementary of the corresponding stability problem, using Lemma 8. Here we only consider item 1; the other items are proved in Appendix C. By Proposition 6, cp-credulous-undec-stability is CoNP-complete, which means that the complementary problem cp-credulous-undec-instability is NP-complete. By Lemma 8 item 3, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of cp-credulous-undec-instability can be transformed into an instance ${\mathit{I}}^{\prime }$ such that I is a positive instance of cp-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of cp-credulous-undec-relevance. □

For each of the four justification statuses j for which we discuss relevance in Proposition 13, the j-stability problem is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete, hence j-instability must be ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete and j-relevance (both addition and removal) must be ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard. In combination with the upper bound identified in Section 5.1, this implies that the corresponding relevance problems are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proposition 13.

The following problems are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete:

cp -credulous- in - relevance ;

cp -credulous- out - relevance ;

pr -credulous- in - relevance ; and

pr -credulous- out - relevance .

Proof.

For each of these problems, membership in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ follows from NP-completeness of the corresponding justification problems [8,9] in combination with Proposition 11. For ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hardness, we can give a reduction from the corresponding instability problem, using Lemma 8.

Since cp-credulous-in-stability is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete (by Lemma 4 and [3, Theorem 24]), the complementary problem (cp-credulous-in-instability) is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete. By Lemma 8 item 1, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of cp-credulous-in-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{″}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of cp-credulous-in-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of cp-credulous-in-relevance.

cp-credulous-out-stability is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete (by Lemma 4 and [3, Theorem 24] in combination with Lemma 5), which means that cp-credulous-in-instability is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete. By Lemma 8 item 2, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of cp-credulous-out-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}\mathit{A}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of cp-credulous-out-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of cp-credulous-out-relevance.

Since pr-credulous-in-stability is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete (by Lemma 4 and [3, Theorem 24]), the complementary problem (pr-credulous-in-instability) is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete. By Lemma 8 item 1, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of pr-credulous-in-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{″}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of pr-credulous-in-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-credulous-in-relevance.

pr-credulous-out-stability is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete (by Lemma 4 and [3, Theorem 24] in combination with Lemma 5), which means that pr-credulous-in-instability is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete. By Lemma 8 item 2, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of pr-credulous-out-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}\mathit{A}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of pr-credulous-out-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-credulous-out-relevance.

 □

Similarly, in Proposition 14 we show that pr-credulous-undec-relevance must be ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete, as pr-credulous-undec-instability is ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -hard and pr-credulous-undec-justification is on the second level of the polynomial hierarchy.

Proposition 14.

pr -credulous- undec - relevance is ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete.

Proof.

Membership in ${\mathrm{\Sigma }}_3^{\mathit{p}}$ follows from ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -completeness of the corresponding justification problem (Proposition 3) in combination with Proposition 11.

For ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -hardness, we reduce from pr-credulous-undec-instability, which is ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete since the co-problem pr-credulous-undec-stability is ${\mathrm{\Pi }}_3^{\mathit{p}}$ -complete (Proposition 8). By Lemma 8 item 3, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of pr-credulous-undec-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{″}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of pr-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-credulous-undec-relevance. □

For some other variants of the relevance problem, the strategy used in Propositions 12, 13 and 14 does not yield tight complexity results. For instance, for cp-sceptical-undec-relevance, using this strategy we could only derive that the problem is in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ (because cp-sceptical-undec-justification is CoNP-complete by Proposition 2) and that it is NP-hard (because cp-sceptical-undec-stability is CoNP-complete by Proposition 7). For these variants, we use another approach, based on an alternative reduction: for the sceptical in- and out-relevance variants, we reduce from credulous undec-instability; for the sceptical undec-relevance variants, we reduce from credulous in-instability. We will use these reductions to prove the remaining complexities for relevance under complete, grounded and preferred semantics in Propositions 15 and 16. In order to use these reductions, we need the following lemma:

Lemma 9 (Reduction co-inverted-stability to relevance).

Given an incomplete argumentation framework $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ , a certain argument $\mathit{A}\in \mathcal{A}$ , semantics $\mathit{\sigma }\in \{\mathrm{\text{GR}}\mathrm{,}\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ :

Construct ${\mathcal{I}}^{\prime }$ and ${\mathcal{I}}^{″}$ as follows, where ${\mathit{A}}^{\prime }$ , U and ${\mathit{U}}^{\prime }$ are fresh arguments not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ :

${\mathcal{A}}^{\prime }=\mathcal{A}\cup \{{\mathit{A}}^{\prime }\}$ ;

${\mathcal{R}}^{\prime }=\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}^{\prime }\mathrm{)}\}$ ;

${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?}⟩$ ; and

${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

The following items are equivalent:

• A is not stable-σ-credulous- in w.r.t. $\mathcal{I}$ ; and

• addition of ${\mathit{U}}^{\prime }$ is σ-sceptical- undec -relevant for ${\mathit{A}}^{\prime }$ w.r.t. ${\mathcal{I}}^{″}$ ; and

• removal of U is σ-sceptical- undec -relevant for ${\mathit{A}}^{\prime }$ w.r.t. ${\mathcal{I}}^{\prime }$ .

Construct ${\mathcal{I}}^{\prime }$ and ${\mathcal{I}}^{″}$ as follows, where ${\mathit{A}}_1$ , ${\mathit{A}}_2$ , ${\mathit{A}}_3$ , ${\mathit{A}}_4$ , U and ${\mathit{U}}^{\prime }$ are fresh arguments not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ :

${\mathcal{A}}^{\prime }=\mathcal{A}\cup \{{\mathit{A}}_1\mathrm{,}{\mathit{A}}_2\mathrm{,}{\mathit{A}}_3\mathrm{,}{\mathit{A}}_4\}$ ;

${\mathcal{R}}^{\prime }=\mathcal{R}\cup \{\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}_1\mathrm{)}\mathrm{,}\mathrm{(}\mathit{A}\mathrm{,}{\mathit{A}}_2\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}_1\mathrm{,}{\mathit{A}}_2\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}_2\mathrm{,}{\mathit{A}}_3\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{A}}_3\mathrm{,}{\mathit{A}}_4\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}\mathit{U}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}{\mathit{A}}_3\mathrm{)}\}$ ;

${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}{\mathcal{R}}^{\prime }\mathrm{,}{\mathcal{R}}^{?}⟩$ ; and

${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{\prime }\cup \{\mathit{U}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{{\mathit{U}}^{\prime }\}\mathrm{,}{\mathcal{R}}^{\prime }\cup \{\mathrm{(}{\mathit{U}}^{\prime }\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

The following items are equivalent:

• A is not stable-σ-credulous- undec w.r.t. $\mathcal{I}$ ; and

• addition of ${\mathit{U}}^{\prime }$ is σ-sceptical- in -relevant for ${\mathit{A}}_3$ w.r.t. ${\mathcal{I}}^{″}$ ; and

• removal of U is σ-sceptical- in -relevant for ${\mathit{A}}_3$ w.r.t. ${\mathcal{I}}^{\prime }$ ; and

• addition of ${\mathit{U}}^{\prime }$ is σ-sceptical- out -relevant for ${\mathit{A}}_4$ w.r.t. ${\mathcal{I}}^{″}$ ; and

• removal of U is σ-sceptical- out -relevant for ${\mathit{A}}_4$ w.r.t. ${\mathcal{I}}^{\prime }$ .

Proof idea.

The proof for this lemma, given in Appendix C, is structured in the same way as the proof for Lemma 8. □

In the following two propositions, we will use Lemma 9 to prove the remaining complexities for relevance under cp and pr semantics. First, we prove that cp-sceptical-undec-relevance and pr-sceptical-undec-relevance are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proposition 15.

cp -sceptical- undec - relevance and pr -sceptical- undec - relevance are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proof.

Membership in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ follows from CoNP-completeness of the corresponding justification problems (Proposition 2) in combination with Proposition 11.

For ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hardness and $\mathit{\sigma }\in \{\mathrm{\text{CP}}\mathrm{,}\mathrm{\text{PR}}\}$ , we reduce from σ-credulous-in-instability, which is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete since the co-problem σ-credulous-in-stability is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -complete (Lemma 4 and the results for necessary credulous acceptance from [3, Theorem 24]). By Lemma 9 item 1, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of σ-credulous-in-instability can be transformed into an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}⟩$ (for addition) or ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{″}\mathrm{,}{\mathit{U}}^{\prime }⟩$ (for removal) such that I is a positive instance of σ-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of σ-sceptical-undec-relevance. □

In Proposition 16 we use Lemma 9 to show that pr-sceptical-in- and -out-relevance are ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -hard. Together with upper bounds from Section 5.1, this implies that pr-sceptical-in- and -out-relevance are ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete.

Proposition 16.

pr -sceptical- in - relevance and pr -sceptical- out - relevance are ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete.

Proof.

Membership in ${\mathrm{\Sigma }}_3^{\mathit{p}}$ follows from ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -completeness of the corresponding justification problems ([11] and Lemma 1) in combination with Proposition 11.

For ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -hardness, we reduce from pr-credulous-undec-instability, which is ${\mathrm{\Sigma }}_3^{\mathit{p}}$ -complete since the co-problem pr-credulous-undec-stability is ${\mathrm{\Pi }}_3^{\mathit{p}}$ -complete (by Proposition 8 and Lemma 5). By Lemma 9 item 2, each instance $\mathit{I}=⟨\mathcal{I}\mathrm{,}\mathit{A}⟩$ of pr-credulous-undec-instability can be transformed into:

an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{‴}\mathrm{,}{\mathit{U}}^{\prime }⟩$ such that I is a positive instance of pr-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-sceptical-in-relevance (for addition); or

an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{‴}\mathrm{,}\mathit{U}⟩$ such that I is a positive instance of pr-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-sceptical-in-relevance (for removal); or

an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{″}\mathrm{,}{\mathit{A}}^{″}\mathrm{,}{\mathit{U}}^{\prime }⟩$ such that I is a positive instance of pr-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-sceptical-out-relevance (for addition); or

an instance ${\mathit{I}}^{\prime }=⟨{\mathcal{I}}^{\prime }\mathrm{,}{\mathit{A}}^{″}\mathrm{,}\mathit{U}⟩$ such that I is a positive instance of pr-credulous-undec-instability iff ${\mathit{I}}^{\prime }$ is a positive instance of pr-sceptical-out-relevance (for removal).

 □

At this point, we have proven all complexity results for relevance under complete, grounded and preferred semantics as summarised in Table 4.

5.3. Lower bounds for stable semantics

In this section, we will consider the relevance problems under st semantics. We will prove that the in and out variants of these problems are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete in Proposition 17. For the hardness-proof in this proposition, we require two transformations from ${\mathrm{\Sigma }}_2$ -SAT instances into IAFs. Recall from Section 2.3 that the ${\mathrm{\Sigma }}_2$ -SAT problem is to decide if there is some truth value assignment ${\mathit{\tau }}_{\mathit{X}}$ to variables of X such that for each truth value assignment ${\mathit{\tau }}_{\mathit{Y}}$ : $\mathrm{\Phi }[{\mathit{\tau }}_{\mathit{X}}\mathrm{,}{\mathit{\tau }}_{\mathit{Y}}]=\text{False}$ where Φ is a formula in CNF. The transformations are given in the following definition:

Definition 13 (Transformations).

Let $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ be an instance of ${\mathrm{\Sigma }}_2$ -SAT and let $\mathrm{\Phi }={\bigwedge }_{\mathit{i}}{\mathit{c}}_{\mathit{i}}$ and ${\mathit{c}}_{\mathit{i}}={\bigvee }_{\mathit{j}}{\mathit{\alpha }}_{\mathit{j}}$ for each clause ${\mathit{c}}_{\mathit{i}}$ in Φ, where ${\mathit{\alpha }}_{\mathit{j}}$ are the literals over $\mathit{X}\cup \mathit{Y}$ that occur in clause ${\mathit{c}}_{\mathit{i}}$ . We define two transformations for this instance. Let:

$\mathcal{A}=\{{\mathit{x}}_{\mathit{i}}\mathrm{,}\overline{{\mathit{x}}_{\mathit{i}}}|{\mathit{x}}_{\mathit{i}}\in \mathit{X}\}\cup \{{\mathit{y}}_{\mathit{i}}\mathrm{,}\overline{{\mathit{y}}_{\mathit{i}}}|{\mathit{y}}_{\mathit{i}}\in \mathit{Y}\}\cup \{\overline{{\mathit{c}}_{\mathit{i}}}|{\mathit{c}}_{\mathit{i}}\in \mathit{\varphi }\}\cup \{{\mathit{\varphi }}^{\prime }\mathrm{,}\bar{\mathit{\varphi }}\mathrm{,}\mathit{\varphi }\}$ ;

${\mathcal{A}}^{?}=\{{\mathit{g}}_{\mathit{i}}|{\mathit{x}}_{\mathit{i}}\in \mathit{X}\}$ ;

$\mathcal{R}=\{\mathrm{(}\overline{{\mathit{x}}_{\mathit{i}}}\mathrm{,}{\mathit{x}}_{\mathit{i}}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{g}}_{\mathit{i}}\mathrm{,}\overline{{\mathit{x}}_{\mathit{i}}}\mathrm{)}|{\mathit{x}}_{\mathit{i}}\in \mathit{X}\}\cup \{\mathrm{(}\overline{{\mathit{y}}_{\mathit{i}}}\mathrm{,}{\mathit{y}}_{\mathit{i}}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{y}}_{\mathit{i}}\mathrm{,}\overline{{\mathit{y}}_{\mathit{i}}}\mathrm{)}|{\mathit{y}}_{\mathit{i}}\in \mathit{Y}\}\cup \{\mathrm{(}{\mathit{x}}_{\mathit{k}}\mathrm{,}\overline{{\mathit{c}}_{\mathit{i}}}\mathrm{)}|{\mathit{x}}_{\mathit{k}}\in {\mathit{c}}_{\mathit{i}}\}\cup \{\mathrm{(}\overline{{\mathit{x}}_{\mathit{k}}}\mathrm{,}\overline{{\mathit{c}}_{\mathit{i}}}\mathrm{)}|\neg {\mathit{x}}_{\mathit{k}}\in {\mathit{c}}_{\mathit{i}}\}\cup \{\mathrm{(}{\mathit{y}}_{\mathit{k}}\mathrm{,}\overline{{\mathit{c}}_{\mathit{i}}}\mathrm{)}|{\mathit{y}}_{\mathit{k}}\in {\mathit{c}}_{\mathit{i}}\}\cup \{\mathrm{(}\overline{{\mathit{y}}_{\mathit{k}}}\mathrm{,}\overline{{\mathit{c}}_{\mathit{i}}}\mathrm{)}|\neg {\mathit{y}}_{\mathit{k}}\in {\mathit{c}}_{\mathit{i}}\}\cup \{\mathrm{(}\overline{{\mathit{c}}_{\mathit{i}}}\mathrm{,}{\mathit{\varphi }}^{\prime }\mathrm{)}|{\mathit{c}}_{\mathit{i}}\in \mathrm{\Phi }\}\cup \{\mathrm{(}{\mathit{\varphi }}^{\prime }\mathrm{,}\bar{\mathit{\varphi }}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{\chi }\mathrm{,}\bar{\mathit{\varphi }}\mathrm{)}\mathrm{,}\mathrm{(}\bar{\mathit{\varphi }}\mathrm{,}\mathit{\varphi }\mathrm{)}\}$ .

A first transformation into an IAF can be constructed as: ${\mathit{T}}_1\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{\chi }\}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩$ , where χ is a fresh uncertain argument not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ . A second transformation is ${\mathit{T}}_2\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}=⟨\mathcal{A}\cup \{\mathit{\chi }\}\mathrm{,}{\mathcal{A}}^{?}\cup \{\bar{\mathit{\chi }}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\bar{\mathit{\chi }}\mathrm{,}\mathit{\chi }\mathrm{)}\}\mathrm{,}\varnothing ⟩$ where χ and $\bar{\mathit{\chi }}$ are not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ .

An example of transformation ${\mathit{T}}_1$ is illustrated in Fig. 13 for the instance $\mathrm{(}\mathrm{\Phi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ where the formula $\mathrm{\Phi }=\mathrm{(}{\mathit{x}}_1\vee \neg {\mathit{y}}_1\mathrm{)}\wedge \mathrm{(}{\mathit{y}}_1\vee {\mathit{y}}_2\mathrm{)}$ , $\mathit{X}=\{{\mathit{x}}_1\}$ and $\mathit{Y}=\{{\mathit{y}}_1\mathrm{,}{\mathit{y}}_2\}$ . Figure 14 shows transformation ${\mathit{T}}_2$ for the same ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathrm{\Phi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ .

Fig. 13.

Visualisation of the IAF created for the clauses ${\mathit{c}}_1={\mathit{x}}_1\vee \neg {\mathit{y}}_1$ and ${\mathit{c}}_2={\mathit{y}}_1\vee {\mathit{y}}_2$ using transformation ${\mathit{T}}_1$ of Definition 13.

Fig. 14.

Visualisation of the IAF created for the clauses ${\mathit{c}}_1={\mathit{x}}_1\vee \neg {\mathit{y}}_1$ and ${\mathit{c}}_2={\mathit{y}}_1\vee {\mathit{y}}_2$ using transformation ${\mathit{T}}_2$ of Definition 13.

In the following lemma, we use the transformations ${\mathit{T}}_1$ and ${\mathit{T}}_2$ to identify equivalences between instances of ${\mathrm{\Sigma }}_2$ -SAT and relevance.

Lemma 10.

Let $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ be an instance of ${\mathrm{\Sigma }}_2$ -SAT and let $\mathit{\varphi }={\bigwedge }_{\mathit{i}}{\mathit{c}}_{\mathit{i}}$ and ${\mathit{c}}_{\mathit{i}}={\bigvee }_{\mathit{j}}{\mathit{\alpha }}_{\mathit{j}}$ for each clause ${\mathit{c}}_{\mathit{i}}$ in ϕ, where ${\mathit{\alpha }}_{\mathit{j}}$ are the literals over $\mathit{X}\cup \mathit{Y}$ that occur in clause ${\mathit{c}}_{\mathit{i}}$ . Now let ${\mathcal{I}}_1={\mathit{T}}_1\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and let ${\mathcal{I}}_2={\mathit{T}}_2\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ , using the transformations ${\mathit{T}}_1$ and ${\mathit{T}}_2$ specified in Definition  13 . The following items are equivalent:

$\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive instance of ${\mathrm{\Sigma }}_2$ -SAT;

Removal of χ is st -sceptical- in -relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_1$ ;

Addition of χ is st -credulous- in -relevant for ϕ w.r.t. ${\mathcal{I}}_1$ ;

Addition of $\bar{\mathit{\chi }}$ is st -sceptical- in -relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_2$ ;

Removal of $\bar{\mathit{\chi }}$ is st -credulous- in -relevant for ϕ w.r.t. ${\mathcal{I}}_2$ ;

Removal of χ is st -sceptical- out -relevant for ϕ w.r.t. ${\mathcal{I}}_1$ ;

Addition of χ is st -credulous- out -relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_1$ ;

Addition of $\bar{\mathit{\chi }}$ is st -sceptical- out -relevant for ϕ w.r.t. ${\mathcal{I}}_2$ ; and

Removal of $\bar{\mathit{\chi }}$ is st -credulous- out -relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_2$ .

Proof sketch.

We introduce an auxiliary statement, for which we prove that it equals all of the items above:

There is some ${\mathcal{I}}^{\ast }\in \mathtt{\text{part}}\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{)}$ such that $\bar{\mathit{\varphi }}$ is st-sceptical-in in its certain projection ${\mathit{\text{AF}}}^{\ast }$ (where $\mathcal{A}$ , ${\mathcal{A}}^{?}$ and $\mathcal{R}$ are chosen as in Definition 13).

Using this additional item, we prove these items separately. For brevity, we only show the equivalence between items 0 and 1 and 0 and 2 here; for full proofs for all equivalences, we refer to Appendix C. (0) ⇒ (1)

Suppose that there is some ${\mathcal{I}}^{\ast }\in \mathtt{\text{part}}\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{)}$ such that $\bar{\mathit{\varphi }}$ is st-sceptical-in in the certain projection ${\mathit{\text{AF}}}^{\ast }=⟨{\mathcal{A}}^{\ast }\mathrm{,}{\mathcal{R}}^{\ast }⟩$ of ${\mathcal{I}}^{\ast }$ . Let ${\mathit{\tau }}_{\mathit{X}}$ be an assignment to variables in X such that it assigns True to all ${\mathit{x}}_{\mathit{i}}\in \mathit{X}$ such that ${\mathit{g}}_{\mathit{i}}\in {\mathcal{A}}^{\ast }$ and False otherwise. Let ${\mathit{\tau }}_{\mathit{Y}}$ be an arbitrary assignment to all variables in Y. Given that $\bar{\mathit{\varphi }}$ is st-sceptical-in in ${\mathit{\text{AF}}}^{\ast }$ , for each st extension S of ${\mathit{\text{AF}}}^{\ast }$ , at least one of the arguments $\overline{{\mathit{c}}_{\mathit{i}}}$ must have been in S, so there is at least one clause in the formula Φ for which none of the variables was assigned True by ${\mathit{\tau }}_{\mathit{X}}$ and ${\mathit{\tau }}_{\mathit{Y}}$ . Since we chose ${\mathit{\tau }}_{\mathit{Y}}$ arbitrarily, we have that $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive instance of ${\mathrm{\Sigma }}_2$ -SAT.

(1) ⇒ (0)

Let $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ be a positive instance of ${\mathrm{\Sigma }}_2$ -SAT. Then there is some assignment ${\mathit{\tau }}_{\mathit{X}}$ to all variables of X such that for each assignment ${\mathit{\tau }}_{\mathit{Y}}$ to the variables of Y, $\mathrm{\Phi }[{\mathit{\tau }}_{\mathit{X}}\mathrm{,}{\mathit{\tau }}_{\mathit{Y}}]$ is False. Let $\mathit{G}=\{{\mathit{g}}_{\mathit{i}}|{\mathit{x}}_{\mathit{i}}\in \mathit{X}\text{ and }{\mathit{x}}_{\mathit{i}}\text{ is assigned True by }{\mathit{\tau }}_{\mathit{X}}\}$ . Construct ${\mathcal{I}}^{\ast }=⟨\mathcal{A}\cup \mathit{G}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}{|}_{\mathcal{A}\cup \mathit{G}}\mathrm{,}\varnothing ⟩$ and let ${\mathit{\text{AF}}}^{\ast }$ be its certain projection. Note that ${\mathcal{I}}^{\ast }\in \mathtt{\text{part}}\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{)}$ . Given that all arguments in G are unattacked, each $\mathrm{\text{ST}}$ extension of ${\mathit{\text{AF}}}^{\ast }$ contains all arguments in G. Furthermore, for each argument $\mathit{x}\in \mathit{X}$ , each st extension of ${\mathit{\text{AF}}}^{\ast }$ contains either x (if x is assigned True by ${\mathit{\tau }}_{\mathit{X}}$ ) or $\bar{\mathit{y}}$ (if x is assigned False by ${\mathit{\tau }}_{\mathit{Y}}$ ). Additionally, for each argument $\mathit{y}\in \mathit{Y}$ , each $\mathrm{\text{ST}}$ extension of ${\mathit{\text{AF}}}^{\ast }$ contains either y or $\bar{\mathit{y}}$ . Given that for each assignment ${\mathit{\tau }}_{\mathit{Y}}$ to the variables of Y, $\mathit{\varphi }[{\mathit{\tau }}_{\mathit{X}}\mathrm{,}{\mathit{\tau }}_{\mathit{Y}}]$ is False, it must be that for each st extension S of this AF, at least one of the clause arguments $\overline{{\mathit{c}}_{\mathit{i}}}$ is in S, so ${\mathit{\varphi }}^{\prime }$ is attacked by an argument in S; therefore $\bar{\mathit{\varphi }}\in \mathit{S}$ . Thus, $\bar{\mathit{\varphi }}$ is st-sceptical-in in ${\mathit{\text{AF}}}^{\ast }$ .

(0) ⇒ (2)

Suppose that there is some ${\mathcal{I}}^{\ast }=⟨{\mathcal{A}}^{\ast }\mathrm{,}{\mathcal{A}}^{?\ast }\mathrm{,}\mathcal{R}{|}_{{\mathcal{A}}^{\ast }\cup {\mathcal{A}}^{?\ast }}\mathrm{,}\varnothing ⟩$ in $\mathtt{\text{part}}\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{)}$ such that $\bar{\mathit{\varphi }}$ is st-sceptical-in in its certain projection ${\mathit{\text{AF}}}^{\ast }$ . This implies that for ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\ast }\mathrm{,}\{\mathit{\chi }\}\mathrm{,}\mathcal{R}{|}_{{\mathcal{A}}^{\ast }\cup \{\mathit{\chi }\}}\mathrm{,}\varnothing ⟩$ it also holds that $\bar{\mathit{\varphi }}$ is st-sceptical-in in its certain projection ${\mathit{\text{AF}}}^{\prime }={\mathit{\text{AF}}}^{\ast }=⟨{\mathcal{A}}^{\ast }\mathrm{,}\mathcal{R}{|}_{{\mathcal{A}}^{\ast }}⟩$ . Note that ${\mathcal{I}}^{\prime }\in \mathtt{\text{part}}\mathrm{(}{\mathcal{I}}_1\mathrm{)}$ . Now consider ${\mathcal{I}}^{″}=⟨{\mathcal{A}}^{\ast }\cup \{\mathit{\chi }\}\mathrm{,}\varnothing \mathrm{,}\mathcal{R}{|}_{{\mathcal{A}}^{\ast }\cup \{\mathit{\chi }\}}\mathrm{,}\varnothing ⟩$ and its certain projection ${\mathit{\text{AF}}}^{″}$ . In ${\mathit{\text{AF}}}^{″}$ , the argument $\bar{\mathit{\varphi }}$ is attacked by the unattacked argument χ, so $\bar{\mathit{\varphi }}$ is not st-sceptical-in in ${\mathit{\text{AF}}}^{″}$ . Then by Lemma 7 item 3, removal of χ is st-sceptical-in-relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_1$ .

(2) ⇒ (0)

If removal of χ is st-sceptical-in-relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_1$ then by Lemma 7 item 3 there is some ${\mathcal{I}}^{\prime }=⟨{\mathcal{A}}^{\ast }\mathrm{,}\varnothing \mathrm{,}\mathcal{R}{|}_{{\mathcal{A}}^{\ast }}\mathrm{,}\varnothing ⟩$ in ${\mathcal{I}}_1$ (where $\mathit{\chi }\notin {\mathcal{A}}^{\ast }$ , so ${\mathcal{I}}^{\prime }\in \mathtt{\text{part}}\mathrm{(}⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩\mathrm{)}$ ) such that $\bar{\mathit{\varphi }}$ is st-sceptical-in in $\mathtt{\text{cert}}\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{)}$ .

 □

The equivalences proven in Lemma 10 are exploited in Proposition 17 to show ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -completeness of some of the relevance instances under st semantics.

Proposition 17.

The following problems are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete:

st -credulous- in - relevance ;

st -sceptical- in - relevance ;

st -credulous- out - relevance ; and

st -sceptical- out - relevance .

Proof.

From Proposition 11 and [8,9] it follows that these problems are in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ .

For the hardness proofs, we use Lemma 10.

st-credulous-in-relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard because ${\mathrm{\Sigma }}_2$ -SAT can be reduced to this problem:

• For the addition variant, convert a given ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ to the IAF ${\mathcal{I}}_1={\mathit{T}}_1\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and check that addition of χ is st-credulous-in-relevant for ϕ w.r.t. ${\mathcal{I}}_1$ ; this is the case iff $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive ${\mathrm{\Sigma }}_2$ -SAT instance (by the equality between item 1 and item 3 of Lemma 10).

• For the removal variant, convert a given ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ to the IAF ${\mathcal{I}}_2={\mathit{T}}_2\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and check that removal of $\bar{\mathit{\chi }}$ is st-credulous-in-relevant for ϕ w.r.t. ${\mathcal{I}}_2$ ; this is the case iff $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive ${\mathrm{\Sigma }}_2$ -SAT instance (by the equality between item 1 and item 5 of Lemma 10).

st-sceptical-in-relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard because ${\mathrm{\Sigma }}_2$ -SAT can be reduced to this problem: for addition, convert a given ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ to the IAF ${\mathcal{I}}_2={\mathit{T}}_2\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and check that addition of $\bar{\mathit{\chi }}$ is st-sceptical-in-relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_2$ ; this is the case iff $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive ${\mathrm{\Sigma }}_2$ -SAT instance (by the equality between item 1 and item 4 of Lemma 10). For removal, the proof is similar but we use the equality between item 1 and item 2.

st-credulous-out-relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard because ${\mathrm{\Sigma }}_2$ -SAT can be reduced to this problem: for addition, convert a given ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ to the IAF ${\mathcal{I}}_1={\mathit{T}}_1\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and check that addition of χ is st-credulous-out-relevant for $\bar{\mathit{\varphi }}$ w.r.t. ${\mathcal{I}}_1$ ; this is the case iff $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive ${\mathrm{\Sigma }}_2$ -SAT instance (by the equality between item 1 and item 7 of Lemma 10). For removal, the proof is similar but we use the equality between item 1 and item 9.

st-sceptical-out-relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard because ${\mathrm{\Sigma }}_2$ -SAT can be reduced to this problem: for addition, convert a given ${\mathrm{\Sigma }}_2$ -SAT instance $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ to the IAF ${\mathcal{I}}_2={\mathit{T}}_2\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ and check that addition of $\bar{\mathit{\chi }}$ is st-credulous-in-relevant for ϕ w.r.t. ${\mathcal{I}}_2$ ; this is the case iff $\mathrm{(}\mathit{\varphi }\mathrm{,}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ is a positive ${\mathrm{\Sigma }}_2$ -SAT instance (by the equality between item 1 and item 8 of Lemma 10). For removal, the proof is similar but we use the equality between item 1 and item 6.

 □

The problems st-credulous-undec-relevance and st-sceptical-existent-undec-relevance are easy, as we show in Proposition 18, because these problems only have negative instances.

Proposition 18.

st -credulous- undec - relevance and st -sceptical-existent- undec - relevance are trivial.

Proof.

For each argumentation framework $\mathit{\text{AF}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ such that a st extension S exists, each argument in $\mathcal{A}$ is either in S or attacked by an argument in S. Therefore, A cannot be st-credulous-undec or st-sceptical-existent-undec in $\mathit{\text{AF}}$ . This applies for each AF, including all certain projections of all partial completions of each possible IAF, so each instance of st-credulous-undec-relevance and st-sceptical-existent-undec-relevance must be negative. □

Next, we consider the st-sceptical-undec-relevance problem.

Proposition 19.

st -sceptical- undec - relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proof sketch.

First, we will show that st-sceptical-undec-relevance is in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ . By Proposition 5, st-sceptical-undec-justification is CoNP-complete. By Proposition 11, this implies that st-sceptical-undec-relevance is in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ .

For the hardness proof, we use an existing result on the problem of necessary nonempty existence under st semantics from [21], which is defined as follows: given an IAF $\mathcal{I}$ , does each completion ${\mathit{\text{AF}}}^{\prime }$ of $\mathcal{I}$ have a nonempty st extension? It is shown in [21, Theorem 21] that this problem is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -hard.

Let $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ be an arbitrary instance of the necessary nonempty existence problem under st semantics. If $\mathcal{A}=\varnothing$ then $\mathcal{I}$ is a negative instance, because there is a completion ${\mathit{\text{AF}}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ of $\mathcal{I}$ where ${\mathcal{A}}^{\prime }=\varnothing$ , which means that ${\mathit{\text{AF}}}^{\prime }$ has no nonempty st extension. Alternatively, assume that $\mathcal{A}$ contains at least one argument and let A be an arbitrary argument in $\mathcal{A}$ . Then we transform $\mathcal{I}$ into an instance $\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ of the argument removal variant of the st-sceptical-undec-relevance problem, where:

U is a fresh uncertain argument, not occurring in $\mathcal{A}\cup {\mathcal{A}}^{?}$ ; and

${\mathcal{I}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{U}\mathrm{,}\mathit{B}\mathrm{)}|\mathit{B}\in \mathcal{A}\cup {\mathcal{A}}^{?}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ .

Then $\mathcal{I}$ is a positive instance of necessary nonempty existence under st semantics iff $\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ is a negative instance of st-sceptical-undec-relevance – we prove this in Appendix C. This appendix also contains proofs for the argument addition, attack addition and attack removal variants of the st-sceptical-undec-relevance problem.

Given that the necessary nonempty existence problem under st semantics is ${\mathrm{\Pi }}_2^{\mathit{p}}$ -hard, the complementary problem of st-sceptical-undec-relevance must be ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard. Together with the membership result from the beginning of this proof, this implies that st-sceptical-undec-relevance is ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete. □

The final variants of the relevance problem are st-sceptical-existent-in-relevance and st-sceptical-existent-out-relevance. These are on the second level of the polynomial hierarchy, as we prove in Proposition 20.

Proposition 20.

st -sceptical-existent- in - relevance and st -sceptical-existent- out - relevance are ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -complete.

Proof sketch.

Membership in ${\mathrm{\Sigma }}_2^{\mathit{p}}$ directly follows from the complexity of st-sceptical-existent-in- and -out-justification and Proposition 11, in the following way: st-sceptical-existent-in-justification is DP-complete by [12, page 92]. By Lemma 1, st-sceptical-existent-out-justification is DP-complete as well. Then by Proposition 11 the problems of st-sceptical-existent-in-relevance and st-sceptical-existent-out-relevance are in ${\mathit{\text{NP}}}^{\mathit{\text{DP}}}={\mathrm{\Sigma }}_2^{\mathit{p}}$ ; note that ${\mathit{\text{NP}}}^{\mathit{\text{DP}}}\subseteq {\mathrm{\Sigma }}_2^{\mathit{p}}$ as any DP query can be answered by two (adaptive) SAT queries.

In order to prove ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hardness, we reduce from possible sceptical-existent acceptance under st semantics (Definition 6), which was proven to be ${\mathrm{\Sigma }}_2^{\mathit{p}}$ -hard in [3, Theorem 25]. Let $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ be an arbitrary instance of possible sceptical-existent acceptance under st semantics where $\mathcal{I}=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\mathrm{,}\mathcal{R}\mathrm{,}{\mathcal{R}}^{?}⟩$ . We transform this into an instance $\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ of st-sceptical-existent-in-relevance where U is a fresh uncertain argument that is not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ and ${\mathcal{I}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{U}\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Then $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ is a positive instance of possible sceptical-existent acceptance under st semantics iff $\mathrm{(}{\mathcal{I}}^{\prime }\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ is a positive instance of st-sceptical-existent-in-relevance; this is proven in Appendix C.

For st-sceptical-existent-out-relevance, we transform an arbitrary instance of possible sceptical-existent acceptance under st semantics $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ to an instance $\mathrm{(}{\mathcal{I}}^{″}\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ of st-sceptical-existent-out-relevance, where U is a fresh uncertain argument that is not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ , B is a fresh argument that is not in $\mathcal{A}\cup {\mathcal{A}}^{?}$ and ${\mathcal{I}}^{″}=⟨\mathcal{A}\cup \{\mathit{B}\}\mathrm{,}{\mathcal{A}}^{?}\cup \{\mathit{U}\}\mathrm{,}\mathcal{R}\cup \{\mathrm{(}\mathit{B}\mathrm{,}\mathit{A}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{U}\mathrm{,}\mathit{U}\mathrm{)}\}\mathrm{,}{\mathcal{R}}^{?}⟩$ . Then $\mathrm{(}\mathcal{I}\mathrm{,}\mathit{A}\mathrm{)}$ is a positive instance of possible sceptical-existent acceptance under st semantics iff $\mathrm{(}{\mathcal{I}}^{″}\mathrm{,}\mathit{A}\mathrm{,}\mathit{U}\mathrm{)}$ is a positive instance of st-sceptical-existent-out-relevance. □

This proposition completes our study on complexity for j-relevance for all justification statuses j within the scope of this paper. These results, proven in Propositions 12–20, can be found in Table 4.

Table 4

Overview of all complexity results related to relevance. We refer to the corresponding proposition by “P” and the proposition number. Full proofs for each of the propositions are presented in the appendix

6. Related work

The computational complexity of various problems defined on argumentation frameworks is well-studied; see [14] for an overview. Most studies only identify accepted arguments and do not distinguish other justification statuses. Notable exceptions are [13] and [2], but neither of these works give complexity results for separate statuses, as we do. In [13], the complexity of justification is studied for the eight justification statuses proposed in [25]. These are related to, but not the same as the justification statuses that we study: in their work, every subset of $\{\mathrm{\text{IN}}\mathrm{,}\mathrm{\text{UNDEC}}\mathrm{,}\mathrm{\text{OUT}}\}$ is a justification status, which should be interpreted as “there is at least one extension where the argument has this label”. Accordingly, the justification status $\{\mathrm{\text{IN}}\}$ w.r.t. some semantics σ from [25] corresponds to our σ-sceptical-in justification status; their $\{\mathrm{\text{OUT}}\}$ corresponds to our σ-sceptical-out and their $\{\mathrm{\text{UNDEC}}\}$ corresponds to our σ-sceptical-undec justification status. There is however no direct mapping between the other statuses. As an additional difference, the authors of [13] give an aggregated result for all statuses, whereas we prove the complexity for each justification status separately. [2] consider the same three justification statuses as we do, but give complexity results for an aggregation of these statuses: they introduce the notions of determinism, totality and functionality and provide complexity results for determining these for a given argument. They define an argument as deterministic if has the same label (in, out or undec) in all extensions. An argument is total if it is in or out in all extensions; arguments are functional if they are both deterministic and total.

Complexity studies on problems defined on IAFs emerged more recently. For example, variants of the verification problem on IAFs are studied in [4]. The problems of stability and relevance differ from the verification problem as they are defined on arguments rather than sets of arguments. More related is [3]: the authors study potential and necessary credulous and sceptical acceptance in IAFs, where necessary sceptical acceptance of a given argument A, for example, means that in each partial completion’s certain projection, each extension (under a given semantics) contains A. The notions of necessary credulous and sceptical acceptance are very similar to specific stability problems: in fact, we used results regarding their complexity for proving the complexity of stable-in statuses. Finally, the notion of stability, which was originally defined on structured argumentation frameworks in [23], is transposed to the context of IAFs in [15] and preliminary complexity results for stability under four semantics are provided. In our work, we define a more fine-grained notion of stability and provide more precise complexity characterisations.

Our notion of relevance has not been introduced or studied before the early version of this work in [18]. Relevance is related to the notion of influenced sets in e.g. [1], which intuitively are sets of arguments whose justification status may change after an update. However, this notion is less strict than relevance: there are situations in which some argument A would be in the influenced set of adding an uncertain attack $\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}$ , while addition of $\mathrm{(}\mathit{B}\mathrm{,}\mathit{C}\mathrm{)}$ is not relevant for A. Other work related to relevance is [20] on the notion of independence in abstract argumentation. Building on the graph-theoretical criterion of d-separation, the authors introduce independence between argument sets, where the evaluation of one set of arguments can be independent of the evaluation of another set of arguments if the status of a third set of arguments is already known. This seems to be related to our notion of relevance, which also can be seen as a kind of dependence, but in contrast to (ir)relevance, their notion of independence is conditional. Finally, our notion of relevance is related to work on repairing abstract argumentation frameworks [24]. An AF can be repaired if it is possible to remove (a subset-minimal set of) arguments such that some argument becomes accepted. It is therefore related to our notion of in-relevance, but a difference is that relevance is defined on incomplete argumentation frameworks rather than normal AFs, and therefore puts a constraint on the arguments that can be removed.

7. Conclusion

We have studied the complexity of detecting stability and relevance in incomplete argumentation frameworks. First, we redefined stability [15–17,23] on IAFs. Our definition is a more fine-grained notion than the existing definition on IAFs [15], since it distinguishes between in, out and undec justification statuses. This distinction is appropriate in, for example, applications in inquiry [17,23], where a dialogue discussing a given argument should be terminated if more information cannot change the argument’s (exact) justification status.

As second main contribution of this paper, we performed a complexity analysis for the relevance problem on incomplete argumentation frameworks. Relevance was introduced before for incomplete argumentation frameworks in an early version of this work in [18], but that paper did not contain a full complexity analysis for all relevance statuses considered in this paper. In contrast to the earlier version, we provide complexity results for complete, preferred and stable semantics and study not only in-, but also out- and undec-relevance. Returning to the application in inquiry [16,17], the identification of relevant elements can be used to select the next question, reaching a stable situation in an efficient way.

It is unlikely that the stability and relevance problem itself can be solved efficiently for all inputs: our complexity analysis revealed that the nontrivial variants of the relevance and stability problems have a complexity ranging from the first to the third level of the polynomial hierarchy (cf. Table 1). Interestingly, even within the same semantics, there are differences in the complexity of undec-stability problems and the corresponding in-stability problems – we consider this to be an additional reason to study a fine-grained notion of stability and relevance.

In order to apply these theoretical concepts in practice, we plan to develop algorithms for evaluating or estimating stability and relevance in future work. In addition, we will study stability and relevance in structured argumentation frameworks, such as a dynamic version of ASPIC⁺, for various semantics.