Probabilistic abstract argumentation combines Dung's abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that an argument is (credulously) acceptable according to a given semantics. Specifically, we focus on the most popular semantics (i.e., admissible, stable, semi-stable, complete, grounded, preferred, ideal, ideal-set), and show that computing the probability that an argument is credulously accepted is FP #Pcomplete independently from the adopted semantics.
Several argumentation frameworks have been proposed, with the aim of suitably modeling disputes between two or more parties. Typically, argumentation frameworks model both the possibility of parties to present arguments supporting their theses, and the possibility that some arguments rebut other arguments.
A powerful yet simple argumentation framework is that proposed in the seminal paper [10], called abstract argumentation framework (AAF). An AAF is a representation of a dispute in terms of an argumentation graph A, D , where A is the set of nodes (each called argument) and D is the set of edges (each called defeat or, equivalently, attack ). Basically, an argument is an abstract entity that may attack and/or be attacked by other arguments, and an attack expresses the fact that an argument rebuts/weakens another argument.
Several semantics for AAFs, such as admissible, stable, preferred, complete, grounded, semi-stable, ideal-set and ideal, have been proposed [10,11,2,4] to identify "reasonable" sets of arguments, called extensions. Basically, each of these semantics corresponds to some properties that "certify" whether a set of arguments can be profitably used to support a point of view in a discussion. For instance, under the admissible semantics, a set S of arguments is an extension if S is "conflict-free" (i.e., there is no defeat between arguments in S) and is "robust" against the other arguments (i.e., every argument outside S attacking an argument in S is counterattacked by an argument in S). This means that one using the set of arguments S in a discussion does not contradict her/himself, and can rebut to the arguments possibly presented by the other parties.
As a matter of fact, in the real world, arguments and defeats are often uncertain. For instance, consider an argument a (or a defeat δ) encoding an interpretation or a translation of the description of a fact reported in a reference text. Then, a (or δ) may be uncertain in the sense that the original paragraph may have interpretations other than that encoded by a (or δ).
Thus, several proposals have been made to model uncertainty in AAFs, by considering weights, preferences, or probabilities associated with arguments and/or defeats. One of the most popular approaches based on probability theory for modeling the uncertainty is the so called constellations approach [12,32,7,9,25,27,30,19,20]: the dispute is represented by means of a Probabilistic Argumentation Framework (PrAAF), that consists in a set of alternative scenarios, each represented by an argumentation graph associated with a probability. The various works in the literature investigating PrAAFs can differ in the assumption on how the probability distribution function (pdf) over the scenarios is specified. For instance, in [12], the pdf is defined "extensively", by enumerating all the possible scenarios and, for each of them, the value of its probability. On the other hand, in [30], the restriction that arguments and defeats are independent is assumed, and this is exploited to simplify the way probabilities are specified: the pdf is not explicitly specified, as it is implied by the marginal probabilities associated with arguments and defeats.
As regards reasoning over an argumentation framework, in the deterministic setting, two classical problems supporting the reasoning over AAFs have been deeply investigated and used in practical applications:
-Ext sem (S): the problem of deciding whether a set of arguments S is an extension according to the semantics sem; -CA sem : the problem of deciding whether the argument a is acceptable, i.e., it belongs to at least one extension under the semantics sem.
Basically, the relevance of these problems is that solving Ext sem (S) supports the decision on whether presenting a set of arguments in a dispute is a reasonable strategy, while solving CA sem focuses this analysis on single arguments. In the probabilistic setting, there are multiple scenarios to be taken into account, and an argument a can be acceptable in some scenarios, but not in others. Thus, the natural probabilistic counterparts P-Ext sem (S) and P-CA sem of the above-mentioned problems Ext sem (S) and CA sem consist in evaluating the overall probability that S is an extension and a is acceptable, respectively, where "overall" means summing the probabilities of the scenarios where the property is verified.
The complexity of Ext sem (S) and P-Ext sem (S) has been deeply investigated. Specifically, in the probabilistic setting the complexity of P-Ext sem (S) has been investigated both in the case that the assumption that arguments and defeats are independent holds [19][20][21][22] and in more general cases [23].
As regards CA sem , its complexity has been deeply investigated, showing that it ranges from PTIME to p 2 -complete, depending on the adopted semantics [6,14,5,13]. Detailed complexity results from the literature are reported in the first column of Table 1.
However, to the best of our knowledge no work has been done for characterizing the complexity of P-CA sem .
In this paper we focus on the constellations approach with independence proposed in [30] and analyze the complexity of P-CA sem showing that it is F P #P -complete independently from the adopted semantics (see the second column of Table 1). Proving that the problem is intractable backs the usage of alternative strategies for solving P-CA sem , such as resorting to Monte-carlo based probability estimation approaches.
In this section, we briefly recall some basic notions about computational complexity, and concisely overview Dung's abstract argumentation framework, and its probabilistic extension introduced in [30].
The computational complexity of the problem addressed in this paper is related to the complexity classes of counting problems. A counting problem f is a function from strings over a finite alphabet into integers. #P is the complexity class of the functions f such that f counts the number of accepting paths of a nondeterministic polynomial-time Turing machine [34]. Although the problem addressed in the paper is closely related to #P , strictly speaking, it cannot belong to it, since the outputs of our problem are not integers. In fact, we deal with the class F P #P , that is, the class of functions computable by a polynomialtime Turing machine with a #P oracle. In this regard, note that a function is F P #P -hard iff it is #P -hard, and thus to prove that a problem is F P #P -hard it suffices to reduce a #P -hard problem to it.
An abstract argumentation framework [10] (AAF ) is a pair A, D , where A is a finite set, whose elements are referred to as arguments, and D ⊆ A × A is a binary relation over A, whose elements are referred to as defeats (or attacks). An argument is an abstract entity whose role is entirely determined by its relationships with other arguments. Given an AAF A, we also refer to the set of its arguments and the set of its defeats as Arg(A) and Def (A), respectively. Given arguments a, b ∈ A, we say that a defeats b iff there is (a, b) ∈ D. Similarly, a set S ⊆ A defeats an argument b ∈ A iff there is a ∈ S such that a defeats b.
A set S ⊆ A of arguments is said to be conflict-free if there are no a, b ∈ S such that a defeats b. An argument a is said to be acceptable w.r.t. S ⊆ A iff ∀b ∈ A such that b defeats a, there is c ∈ S such that c defeats b. Given a set S ⊆ A of arguments, we define S + as the set of arguments that are defeated by S, that is, S + = {a ∈ A s.t. S defeats a}.
Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions. We consider the following well-known semantics [10,11,4]: admissible (ad), stable (st), complete (co), grounded (gr), semi-stable (sst), preferred (pr), ideal-set (ids), and ideal (ide). A set S ⊆ A is said to be:
an admissible extension iff S is conflict-free and all its arguments are acceptable w.r.t. S; a stable extension iff S is conflict-free and S defeats each argument in A \ S; a complete extension iff S is admissible and S contains all the arguments that are acceptable w.r.t. S; a grounded extension iff S is a minimal (w.r.t. ⊆) complete set of arguments; a semi-stable extension iff S is a complete extension where S ∪S + is maximal (w.r.t. ⊆); a preferred extension iff S is a maximal (w.r.t. ⊆) admissible set of arguments; an ideal-set extension iff S is admissible and S is contained in every preferred set of arguments; an ideal extension iff S is a maximal (w.r.t. ⊆) ideal-set extension; 1, where arguments are represented as nodes and defeats are represented as edges between nodes. As S = {a, c} is conflict-free and every argument in S is acceptable w.r.t. S, it is the case that S is admissible. It is easy to see that the sets {b}, {c}, and ∅ are admissible extensions as well. Since S is conflict-free and defeats b (the only argument in A\S) it is also a stable extension. As S is maximally admissible, it a preferred extension, while {c} is not, since a is acceptable w.r.t {c}. It is easy to check that S is complete, while it neither is grounded (since it is not minimally complete, as the emptyset is complete) nor ideal or ideal-set (since it is not contained in {b} which is a preferred extension). Given an AAF A, a set S ⊆ Arg(A) of arguments, an argument a ∈ Arg(A) and a semantics sem ∈{ad, st, gr, co, sst, pr, ids, ide}, we define the function acc(A, sem, a) that returns true if ∃S ⊆ Arg(A) such that a ∈ S and S is an extension according to sem, false otherwise.
Example 2. Consider the AAF A, D introduced in Example 1. The argument a is credulously accepted under the admissible, stable, complete, semi-stable and preferred semantics. a is not credulousy accepted under the grounded, ideal-set and ideal semantics. 2
We now review the probabilistic abstract argumentation framework proposed in [30].
Definition 1 (PrAAF). A probabilistic argumentation framework (PrAAF) is a tuple A, P A , D, P D where A, D is an AAF, and P A and P D are, respectively, functions assigning a non-zero1 probability value to each argument in A and defeat in D, that is,
Basically, the value assigned by P A to an argument a represents the probability that a actually occurs, whereas the value assigned by P D to a defeat (a, b) represents the conditional probability that a defeats b given that both a and b occur.
The meaning of a PrAAF is given in terms of possible worlds, each of them representing a scenario that may occur in the reality. Given a PrAAF F, a possible world is modeled by an AAF which is derived from F by considering only a subset of its arguments and defeats. More formally, given a PrAAF F = A, P A , D, P D , a possible world w of F is an AAF A , D such that A ⊆ A and D ⊆ D ∩ (A × A ). The set of the possible worlds of F will be denoted as pw(F).
Example 3. As a running example, consider the PrAAF F = A, P A , D, P D reported in Figure 2, where A and D are those of Example 1, and P A (a) = .9, P A (b) = .7, P A (c) = .2, P D (δ 1 ) = .9 and P D (δ 2 ) = P D (δ 3 ) = 1. The set pw(F) contains the following possible worlds:
.9
Fig. 2: The PrAAF A, PA, D, PD
An interpretation for a PrAAF F = A, P A , D, P D is a probability distribution function I over the set pw(F) of the possible worlds. Assuming that arguments represent pairwise independent events, and that each defeat represents an event conditioned by the occurrence of its argument events but independent from any other event, the interpretation for the PrAAF F = A, P A , D, P D is as follows. For each possible world w ∈ pw(F), w is assigned by I the probability:
where D(w) is the set of defeats that may appear in the possible world w, that is D(w) = D ∩ (Arg(w) × Arg(w)). Hence, the probability of a possible world w is given by the product of four contributions: (i ) the product of the probabilities of the arguments belonging to w; (ii ) the product of the one's complements of the probabilities of the arguments that do not appear in w; (iii ) the product of the conditional probabilities of the defeats in w (recall that a defeat δ = (a, b) may appear in w only if both a and b are in w); (iv ) the product of the one's complements of the conditional probabilities of the defeats that, though they may appear in w, they do not. The probability that an argument a is acceptable according to a given semantics sem is defined as the sum of the probabilities of the possible worlds w for which a is acceptable according to sem, i.e., acc(w, sem, a) = true.
Obviously, computing P rCA sem F (a) by directly applying Definition 2 would require exponential time, since it relies on summing the probabilities of an exponential number of possible worlds. However, this does not rule out the possibility that efficient strategies for computing P rCA sem F (a) exist. Unfortunately, this is not true in the general case. Indeed, in the next section we show that the problem of computing P rCA sem F (S) is F P #P -complete.
Definition 3 (P-CA sem ). Given a PrAAF F = A, P A , D, P D , an argument a ∈ A, and a semantics sem, P-CA sem is the problem of computing the probability P rCA sem F (a).
In this section we characterize the complexity of P-CA sem , by first showing that it is in F P #P and then showing that it is F P #P -hard.
Theorem 1. For sem ∈ {ad, st, co, gr, sst, pr, ids, ide }, it holds that P-CA sem is in F P #P . Proof. First, observe that P rCA sem F (a) with sem ∈ {ad, st, co, gr, sst, pr, ids, ide }, can be expressed as a rational number whose denominator d is the product of the denominators of the probabilities of arguments in A and defeats in D.
We first prove the statement for sem = gr. First observe that CA sem is in PTIME for sem = gr. We show that PrCA gr F (a) can be computed by a polynomial time algorithm A with access to a #P oracle. Algorithm A first computes d in polynomial time w.r.t. the size of F, then calls a #P oracle to determine the numerator of PrCA gr F (a). The oracle counts the number of accepting paths of a nondeterministic polynomial-time Turing machine M such that:
(i) M nondeterministically guesses a subset of arguments in A and defeats in D so that each leaf of the resulting computation tree is a possible world w ∈ pw(F); (ii) At each leaf, let w be the guessed world, and I(w) its probability, the computation tree is then split again d • I(w) times to reflect the probability of the guessed world (for each w ∈ pw(F), I(w) is a rational number whose denominator is d, and I(w) can be computed in polynomial time w.r.t. the size of F); (iii) Finally, M checks in polynomial time if a is an acceptable argument in the world w w.r.t. the grouded semantics.
Thus, the number of accepting paths of M is d• PrCA gr F (a) that is the numerator n of PrCA gr F (a). As a final step, algorithm A returns both n and d. To prove the statement for sem ∈{ad, st, co, sst, pr, ids, ide} it suffices to reason analogously to the membership proof for the grounded semantics, by considering that CA sem for those semantics is either in NP, or in Θ p 2 , or in p 2 . Specifically, for sem ∈{ad, st, co, sst, pr, ids, ide}, PrCA sem F (a) can be computed by an algorithm A which behaves as follows. A first computes (in polynomial time) the denominator d of PrCA sem F (a). Then A invokes a #N P , or a #Θ p 2 or a # p 2 oracle that counts the number of accepting paths of a non-deterministic Turing machine M defined in the same way of M with the difference that the step (iii ) of the computation of M is replaced by the invocation of either an N P , a Θ p 2 or a p 2 oracle that checks whether a is an acceptable argument w.r.t. sem in the world w obtained as final leaf of the computation tree. Therefore, since F P #P = F P #N P = F P #Θ p 2 = F P # p 2 , then P-CA sem is in F P #P . 2
To prove that P-CA sem is F P #P -hard we show a reduction from the #P -hard problem #P 2CN F , that is the problem of counting the number of satisfying assignments of a CN F formula where each clause consists of exactly 2 positive literals, to P-CA sem .
Definition 4. Let φ = C 1 ∧ C 2 ∧ . . . C k be a P 2CN F , where X = {X 1 , . . . , X n } is the set of its propositional variables.
We define the PrAAF associated to φ (F(φ) = A, P A , D, P D ) as follows:
Moreover, let γ be a truth assignment for the propositional variables x 1 , . . . , x n . We define as w(γ, F(φ)) the possible world w = A w , D w ∈ pw(F(φ)) defined as follows:
It is easy to see that given a possible world w ∈ pw(F(φ)) the probability of
, where probabilities different from 1.0 are reported next to each node and edge. Moreover, consider the truth assignment γ for X 1 , X 2 and X 3 such that γ(X 1 ) =true, γ(X 2 ) =true and γ(X 3 ) =false.
The possible world w(γ, F(φ)) is reported in Figure 3(b). Lemma 1. Let φ = C 1 ∧ C 2 ∧ . . . C k be a P 2CN F , where X = {X 1 , . . . , X n } is the set of its propositional variables.
For each truth assignment γ for the propositional variables X 1 , . . . , X n it holds that CA ad w(γ,F (φ)) (a) is true iff γ(φ) is true.
Proof. We first prove that for each truth assignment γ for X 1 , . . . , X n the fact that CA ad w(γ,F (φ)) (a) is true implies that γ(φ) is true. Reasoning by contradiction assume that there exists a truth assignment γ for X 1 , . . . , X n such that w = w(γ, F(φ)) and CA ad w (a) is true while γ(φ) is false. Since CA ad w (a) is true there exists an admissible extension S for w such that a ∈ S. It is easy to see that S ∩ {c 1 , . . . , c k } = ∅, as otherwise S would not be an admissible extension (S would not be conflict-free). Moreover, it is easy to see that there exists a subset {x i1 , . . . , x i h } of {x 1 , . . . , x n } such that {x i1 , . . . , x i h } ⊆ S and for each j ∈ [1..k] there is l ∈ [1..h] such that:
1. x i l ∈ A w , and 2. (x i l , c j ) ∈ D w , as otherwise S would not be an admissible extension as there would be a c j attacking a which is not attacked by any argument in S.
Since γ(φ) is false it must be the case that there is a j ∈ [i.
.k] such that C j = X l ∨ X h and γ(X l ) = γ(X h ) =false. This implies that x l ∈ A w , x h ∈ A w , (x l , c j ) ∈ D w and (x h , c j ) ∈ D w , thus contradicting the fact that S is an admissible extension. Hence, it holds that for each truth assignment γ for x 1 , . . . , x n the fact that CA ad w(γ,F (φ)) (a) is true implies that γ(φ) is true. We now prove that for each truth assignment γ for x 1 , . . . , x n the fact that γ(φ) is true implies that CA ad w(γ,F (φ)) (a) is true. Reasoning by contradiction assume that there exists a truth assignment γ for x 1 , . . . , x n such that w = w(γ, F(φ)) and CA ad w (a) is false while γ(φ) is true. Let S be the set of arguments {a} ∪ {x
We show that S is an admissible extension reasoning by contradiction. Since S is not an admissible extension it must be the case that there is a j ∈ [1..k] such that C j = X h ∨ X l and both x h / ∈ S and x l / ∈ S. Hence, by construction of S it holds that γ(X h ) = γ(X h ) = false which, in turn, implies that γ(φ) = false, thus contradicting that γ is a truth assignment γ for x 1 , . . . , x n such that γ(φ) is true. This implies that for each truth assignment γ for x 1 , . . . , x n the fact that γ(φ) is true implies that CA ad w(γ,F (φ)) (a) is true.
, where X = {X 1 , . . . , X n } is the set of its propositional variables. For a possible world w ∈ pw(F(φ)) CA ad w(γ,F (φ)) (a) is true iff CA sem w(γ,F (φ)) (a), where sem ∈{st, co, gr, sst, pr, ids, ide}, is true.
Proof. The if part is straightforward since stable, complete, grounded, semistable, preferred, ideal-set and ideal extensions are admissible extensions. As regards the proof of the only if part, reasoning by contradiction we assume that there is an admissible extension S such that a ∈ S and there is no extension S according to sem, where sem ∈{st, co, gr, sst, pr, ids, ide }, such that a ∈ S .
Consider the set of arguments Ŝ = S ∪ (Arg(w) ∩ {x 1 , . . . , x n }), and note that Arg(w) \ Ŝ = {c 1 , . . . , c k }. It is straightforward to see that, since S is an admissible extension then Ŝ is an admissible extension. Moreover, it is easy to see that (i) Ŝ is a stable extension since it defeats each argument in Arg(w) \ Ŝ, (ii) Ŝ is a complete extension since it contains all the argument that are acceptable w.r.t. Ŝ, (iii) Ŝ is a preferred extension since Ŝ is an admissible extension and any argument in Arg(w)\ Ŝ attacks an argument in Ŝ, so that for each argument α ∈ Arg(w) \ Ŝ it holds that Ŝ ∪ α is not conflict-free. Moreover, observe that Ŝ is the unique preferred extension for w.
Furthermore, since Ŝ is a complete extension and since removing any argument from Ŝ make it loose the property that it contains all the arguments that are acceptable w.r.t. it, it holds that Ŝ is a grounded extension.
Moreover, since Ŝ ∪ Ŝ+ = Arg(w) then there is no complete extension S such that S ∪ S + ⊃ Ŝ ∪ Ŝ+ . Therefore, since Ŝ is a complete extension it follows that Ŝ is a semi-stable extension.
Finally, it is straightforward to see that Ŝ is an ideal-set and ideal extension for w as it is the unique preferred extension for w.
Hence, for possible world w ∈ pw(F(φ)) CA ad w(γ,F (φ)) (a) is true only if CA sem w(γ,F (φ)) (a) is true, where sem ∈ {st, co, gr, sst, pr, ids, ide}, which completes the proof.
Theorem 2. For sem ∈{ad, st, co, gr, sst, pr, ids, ide}, it holds that P-CA sem is F P #P -hard.
Proof. Given an instance φ of #P 2CN F , we construct an instance of P-CA sem by defining a PrAAF F = F(φ) as in Definition 4, and we return 2 n • (P rCA sem F (a)). Since for each possible world w ∈ pw(F(φ)) we have that I(w) = 1 2 n , from Lemmas 1 and 2 it follows that 2 n • (P rCA sem F (a)) is the number of satisfying assignments of φ.
Hence, as the above described reduction from the #P -hard problem #P 2CN F to P-CA sem is a Cook reduction, this suffices to prove that P-CA sem is F P #P -hard, since a problem is F P #P -hard iff it is #P -hard.
The main state-of-the-art approaches for handling uncertainty in AAFs by relying on probability theory can be classified in two categories, based on the way they interpret the probabilities of the arguments: those adopting the classical constellations approach [27,12,32,7,9,25,30,19,20] and those adopting the recent epistemic one [33,29,28]. As regards the epistemic approach, probabilities and extensions have a different semantics, compared with the constellations approach. Specifically, the probability of an argument represents the degree of belief in the argument (the higher the probability, the more the argument is believed), and a key concept is the "rational" probability distribution, that requires that if the belief in an argument is high, then the belief in the arguments attacked by it is low. In this approach, epistemic extensions are considered rather than Dung's extensions, where an epistemic extension is the set of arguments that are believed to be true to some degree. The interested reader can find a more detailed comparative description of the two categories in [26].
We now focus our attention on the approaches classified as constellations, as the complexity characterization provided in our work refers to this class of PrAAFs. [12] addressed the modeling of jury-based dispute resolutions, and proposed a prAAF where uncertainty is taken into account by specifying probability distribution functions (pdfs) over possible AAFs and showing how an instance of the proposed prAAF can be obtained by specifying a probabilistic assumption-based argumentation framework (introduced by themselves). In the same spirit, [32] defined a prAAF as a pdf over the set of possible AAFs, and introduced a probabilistic version of a fragment of the ASPIC framework [31] that can be used to instantiate the proposed prAAF. [8] addresses the problem of computing all the subgraphs of an AAF in which an argument a belongs to the grounded extension, and [9] extends it by focusing on computing the probability that an argument a belongs to the grounded extension of a probabilistic abstract argumentation framework. In particular, [9] assumes to receive a joint probability distribution over the arguments as input. In fact, providing a joint probability distribution usually means specifying the probability values for all the possible correlations, i.e., P (a), P (a ∧ b), P (a ∧ b ∧ c)... and so on. This is analogous to providing the probabilities for all the possible AAFs (since defeats are considered as certain).
Differently from [12] and [32], [30] proposed a prAAF where probabilities are directly associated with arguments and defeats, instead of being associated with possible AAFs, and independence among pairs of arguments/defeats is assumed. After claiming that computing the probability P sem (S) that a set S of arguments is an extension according to sem requires exponential time for every semantics, [30] proposed a Monte-Carlo simulation approach to approximate P sem (S). [7,19,20] build upon [30]: [7] characterizes different semantics from the approach of [30] in terms of probabilistic logic, as a first step in the direction of creating a uniform logical formalization for all the proposed AAFs of the literature, in order to understand and compare the different approaches. [19,20], instead, showed that computing P sem (S) is actually tractable for the admissible and stable semantics, but it is F P #P -complete for other semantics, including complete, grounded, preferred and ideal-set. Furthermore, [18,21] proposed a Monte-Carlo approach to efficiently estimate P sem (S) based on the polynomiality results of [19,20]. In [30], as well as in [12] and [32], P sem (S) is defined as the sum of the probabilities of the possible AAFs where S is an extension according to semantics sem.
In the above-cited works, probability theory is recognized as a fundamental tool to model uncertainty. However, a deeper understanding of the role of probability theory in abstract argumentation was developed only later in [25,26], where the justification and the premise perspectives of probabilities of arguments are introduced. According to the former perspective the probability of an argument indicates the probability that it is justified in appearing in the argumentation system. In contrast, the premise perspective views the probabil-ity of an argument as the probability that the argument is true based on the degrees to which the premises supporting the argument are believed to be true. Starting from these perspectives, in [26], a formal framework showing the connection among argumentation theory, classical logic, and probability theory was investigated. Furthermore, qualification of attacks is addressed in [27], where an investigation of the meaning of the uncertainty concerning defeats in probabilistic abstract argumentation is provided.
The computational complexity of computing extensions has been thoroughly investigated for classical AAFs [15,16,13,17,24,3] with respect to several semantics (a comprehensive overview of argumentation semantics can be found in [1]). In particular, [15] presents a number of results on the complexity of some decision questions for semi-stable semantics, while [13] focuses on ideal semantics; complexity results for preferred semantics can be found in [16].
Complexity results about skeptical and credulous acceptance under admissible, complete, grounded, stable and preferred semantics have been provided in [6,14,5], while [13] characterizes the complexity of skeptical and credulous acceptance under ideal and ideal-set.
Focusing on the constellations approach with independence proposed in [30], in this paper we characterized the complexity of P-CA sem showing that it is F P #P -complete independently from the adopted semantics. Future work will be devoted to the characterization of the complexity of the problem of computing the probability that an argument is skeptically acceptable w.r.t. a given semantics sem. Moreover, another interesting direction for future work is that of finding tractable cases for P-CA sem by identifying structural properties of the argumentation graph that will ensure that P-CA sem is solvable in polynomial time.