Credulous acceptability in probabilistic abstract argumentation: complexity results Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro DIMES, University of Calabria, Italy ICAR-CNR, Italy {flesca,furfaro}@dimes.unical.it {fazzinga}@icar.cnr.it Abstract. Probabilistic abstract argumentation combines Dung’s ab- stract 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 comput- ing the probability that an argument is credulously accepted is FP #P - complete independently from the adopted semantics. Keywords: Acceptability, Probabilistic Abstract Argumentation, Com- plexity 1 Introduction Several argumentation frameworks have been proposed, with the aim of suitably modeling disputes between two or more parties. Typically, argumentation frame- works 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 sem- inal paper [10], called abstract argumentation framework (AAF). An AAF is a representation of a dispute in terms of an argumentation graph hA, Di, 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 argu- ments 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 2 Bettina Fazzinga et al. 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 uncer- tain. For instance, consider an argument a (or a defeat δ) encoding an interpre- tation 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 Argu- mentation 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 speci- fied. 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: – Extsem (S): the problem of deciding whether a set of arguments S is an extension according to the semantics sem; – CAsem : 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 Extsem (S) sup- ports the decision on whether presenting a set of arguments in a dispute is a reasonable strategy, while solving CAsem focuses this analysis on single argu- ments. 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 oth- ers. Thus, the natural probabilistic counterparts P-Extsem (S) and P-CAsem of the above-mentioned problems Extsem (S) and CAsem 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 Extsem (S) and P-Extsem (S) has been deeply investi- gated. Specifically, in the probabilistic setting the complexity of P-Extsem (S) has been investigated both in the case that the assumption that arguments and defeats are independent holds [19–22] and in more general cases [23]. Credulous acceptability... 3 As regards CAsem , its P complexity has been deeply investigated, showing that p it ranges from PTIME to 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 character- izing the complexity of P-CAsem . In this paper we focus on the constellations approach with independence proposed in [30] and analyze the complexity of P-CAsem showing that it is F P #P -complete independently from the adopted semantics (see the second col- umn of Table 1). Proving that the problem is intractable backs the usage of alternative strategies for solving P-CAsem , such as resorting to Monte-carlo based probability estimation approaches. Table 1: Complexity of CAsem and P-CAsem . sem CAsem P-CAsem admissible NP -complete F P #P -complete stable NP -complete F P #P -complete complete NP -complete F P #P -complete grounded PTIME F P #P -complete Pp #P semi-stable 2 -complete F P -complete preferred NP -complete F P #P -complete ideal-set in Θ2p , coNP -h F P #P -complete ideal in Θ2p , coNP -h F P #P -complete 2 Preliminaries In this section, we briefly recall some basic notions about computational com- plexity, and concisely overview Dung’s abstract argumentation framework, and its probabilistic extension introduced in [30]. 2.1 Complexity The computational complexity of the problem addressed in this paper is re- lated 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 be- long 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 polynomial- time Turing machine with a #P oracle. In this regard, note that a function is 4 Bettina Fazzinga et al. 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. 2.2 Abstract Argumentation An abstract argumentation framework [10] (AAF ) is a pair hA, Di, 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 se- mantics [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 accept- able 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 argu- ments; – 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; Example 1. Consider the AAF hA, Di, where the set A of arguments is {a, b, c} and the set D of defeats is {δ1 = (b, a), δ2 = (b, c), δ3 = (c, b)}, where δ2 and δ3 encode the fact that arguments b and c attack each other. A graphical rap- resentation of the AAF hA, Di is reported in Figure 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 ∅ Credulous acceptability... 5 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). 2 a b c Fig. 1: The AAF hA, Di 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 hA, Di 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 2.3 Probabilistic Abstract Argumentation We now review the probabilistic abstract argumentation framework proposed in [30]. Definition 1 (PrAAF). A probabilistic argumentation framework (PrAAF) is a tuple hA, PA , D, PD i where hA, Di is an AAF, and PA and PD are, respectively, functions assigning a non-zero1 probability value to each argument in A and defeat in D, that is, PA : A → (0, 1] ∩ Q and PD : D → (0, 1] ∩ Q. Basically, the value assigned by PA to an argument a represents the proba- bility that a actually occurs, whereas the value assigned by PD 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 = hA, PA , D, PD i, a possible world w of F is an AAF hA0 , D0 i such that A0 ⊆ A and D0 ⊆ D ∩ (A0 × A0 ). The set of the possible worlds of F will be denoted as pw(F). 1 Assigning probability equal to 0 to arguments/defeats is useless. 6 Bettina Fazzinga et al. Example 3. As a running example, consider the PrAAF F = hA, PA , D, PD i reported in Figure 2, where A and D are those of Example 1, and PA (a) = .9, PA (b) = .7, PA (c) = .2, PD (δ1 ) = .9 and PD (δ2 ) = PD (δ3 ) = 1. The set pw(F) contains the following possible worlds: w1 = h∅, ∅i w2 = h{a}, ∅i w3 = h{b}, ∅i w4 = h{c}, ∅i w5 = h{a, b}, ∅i w6 = h{a, c}, ∅i w7 = h{b, c}, ∅i w8 = hA, ∅i w9 = h{a, b}, {δ1 }i w10 = h{b, c}, {δ3 }i w11 = h{b, c}, {δ2 }i w12 = h{b, c}, {δ2 , δ3 }i w13 = hA, {δ1 }i w14 = hA, {δ1 , δ3 }i w15 = hA, {δ1 , δ2 }i w16 = hA, Di w17 = hA, {δ2 }i w18 = hA, {δ3 }i w19 = hA, {δ2 , δ3 }i .9 1.0 a b c .9 .7 .2 1.0 Fig. 2: The PrAAF hA, PA , D, PD i 2 An interpretation for a PrAAF F = hA, PA , D, PD i is a probability distri- bution function I over the set pw(F) of the possible worlds. Assuming that ar- guments 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 = hA, PA , D, PD i is as follows. For each possible world w ∈ pw(F), w is assigned by I the probability: Q Q I(w) = a∈Arg(w) PA (a)× a∈A\Arg(w) (1 − PA (a))× Q Q × δ∈Def (w) PD (δ) × δ∈D(w)\Def (w) (1 − PD (δ)) 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. Example 4. Continuing our running example, the interpretation I for F is as follows. First of all, observe that, for each possible world w ∈ pw(F), if both arguments b and c belong to Arg(w) and δ2 6∈ Def (w) or δ3 6∈ Def (w), then I(w) = 0. The probabilities of the other possible worlds are the following: Credulous acceptability... 7 I(w1 ) = .024 I(w2 ) = .216 I(w3 ) = .056 I(w4 ) = .006 I(w5 ) = .0504 I(w6 ) = .054 I(w9 ) = .4536 I(w12 ) = .014 I(w16 ) = .1134 I(w19 ) = .0126 2 The probability that an argument a is acceptable according to a given se- mantics 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. Definition 2 (P rCAsem F (a)). Given a PrAAF F = hA, PA , D, PD i, an argu- ment a ∈ A, and a semantics sem, the probability P rCAsem F (a) that a is accept- able under sem is X P rCAsem F (a) = I(w), w∈pwAcc(F ,a) where pwAcc(F, a) = {w ∈ pw(F) |acc(w, sem, a) =true}. The following example shows usages of this definition. Example 5. In our running example, the probabilities that the arguments a and b are acceptable w.r.t. the admissible semantics are as follows: P rCAad F (a) = I(w2 ) +I(w5 ) +I(w6 ) +I(w16 ) +I(w19 ) = .4464 P rCAad F (b) = I(w3 )+ I(w5)+ I(w9)+ I(w12)+ I(w16)+ I(w19) = .8134 2 Obviously, computing P rCAsem F (a) by directly applying Definition 2 would require exponential time, since it relies on summing the probabilities of an expo- nential number of possible worlds. However, this does not rule out the possibility that efficient strategies for computing P rCAsemF (a) exist. Unfortunately, this is not true in the general case. Indeed, in the next section we show that the problem of computing P rCAsem F (S) is F P #P -complete. Definition 3 (P-CAsem ). Given a PrAAF F = hA, PA , D, PD i, an argument a ∈ A, and a semantics sem, P-CAsem is the problem of computing the proba- bility P rCAsem F (a). 3 Complexity of credulous acceptability in probabilistic abstract argumentation In this section we characterize the complexity of P-CAsem , by first showing that it is in F P #P and then showing that it is F P #P -hard. 8 Bettina Fazzinga et al. 3.1 Upper bound Theorem 1. For sem ∈ {ad, st, co, gr, sst, pr, ids, ide }, it holds that P-CAsem is in F P #P . Proof. First, observe that P rCAsem 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 CAsem is gr in PTIME for sem = gr. We show that PrCAF (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 gr to determine the numerator of PrCAF (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 com- putation 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. gr Thus, the number of accepting paths of M is d· PrCAF (a) that is the numerator gr n of PrCAF (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,Pby p considering that CAsem for those semantics is either in NP, or in Θ2p , or in 2 . sem Specifically, for sem ∈{ad, st, co, sst, pr, ids, ide}, PrCAF (a) can be computed by an algorithm A0 which behaves as follows. A0 first computes (in sem 0 polynomial time) the p Ppdenominator d of PrCAF (a). Then A invokes a #N P , or a #Θ2 or a # 2 oracle that counts the number of accepting paths of a non-deterministic Turing machine M 0 defined in the same way of M with the difference that the step (iii ) of P the computation of M is replaced by the invoca- p tion of either an N P , a Θ2p or a 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. p Pp Therefore, since F P #P = F P #N P = F P #Θ2 = F P # 2 , then P-CAsem is in F P #P . 2 3.2 Lower bound To prove that P-CAsem 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 Credulous acceptability... 9 assignments of a CN F formula where each clause consists of exactly 2 positive literals, to P-CAsem . Definition 4. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn } is the set of its propositional variables. We define the PrAAF associated to φ (F(φ) = hA, PA , D, PD i) as follows: – A = {a, c1 , . . . , ck , x1 , . .S . , xn }; – D = {(ci , a) | i ∈ [1..k]} (Ch =Xi ∨Xj )∈φ {(xi , ch ), (xj , ch )}; – PA (a) = 1.0, ∀i ∈ [1..k]PA (ci ) = 1.0, and ∀j ∈ [1..n]PA (xj ) = 12 ; – PD (δ) = 1.0 for each δ ∈ D. Moreover, let γ be a truth assignment for the propositional variables x1 , . . . , xn . We define as w(γ, F(φ)) the possible world w = hAw , Dw i ∈ pw(F(φ)) defined as follows: – Aw = A \ {xi | i ∈ [1..n] ∧ γ(xi ) =false};  – Dw = D \ {(xi , cj ) | i ∈ [1..n] ∧ j ∈ [1..k] ∧ γ(xi ) = false} ; It is easy to see that given a possible world w ∈ pw(F(φ)) the probability of w is I(w) = 21n . Example 6. Consider the P 2CN F formula φ = (X1 ∨ X3 ) ∧ (X2 ∨ X3 ). The PrAAf F(φ) is reported in Figure 3(a), where probabilities different from 1.0 are reported next to each node and edge. Moreover, consider the truth assignment γ for X1 , X2 and X3 such that γ(X1 ) =true, γ(X2 ) =true and γ(X3 ) =false. The possible world w(γ, F(φ)) is reported in Figure 3(b). 2 a c1 c2 a c1 c2 1 1 1 x1 2 x2 2 x3 2 x1 x2 (a) (b) Fig. 3: Graphical representation of the PrAAF F(φ) (a) and the possible world w(γ, F(φ)) (b). Lemma 1. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn } is the set of its propositional variables. For each truth assignment γ for the propositional variables X1 , . . . , Xn it holds that CAad w(γ,F (φ)) (a) is true iff γ(φ) is true. 10 Bettina Fazzinga et al. Proof. We first prove that for each truth assignment γ for X1 , . . . , Xn the fact that CAad w(γ,F (φ)) (a) is true implies that γ(φ) is true. Reasoning by contradiction assume that there exists a truth assignment γ for X1 , . . . , Xn such that w = w(γ, F(φ)) and CAad w (a) is true while γ(φ) is false. Since CAad w (a) is true there exists an admissible extension S for w such that a ∈ S. It is easy to see that S ∩ {c1 , . . . , ck } = ∅, 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 {xi1 , . . . , xih } of {x1 , . . . , xn } such that {xi1 , . . . , xih } ⊆ S and for each j ∈ [1..k] there is l ∈ [1..h] such that: 1. xil ∈ Aw , and 2. (xil , cj ) ∈ Dw , as otherwise S would not be an admissible extension as there would be a cj 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 Cj = Xl ∨ Xh and γ(Xl ) = γ(Xh ) =false. This implies that xl 6∈ Aw , xh 6∈ Aw , (xl , cj ) 6∈ Dw and (xh , cj ) 6∈ Dw , thus contradicting the fact that S is an admissible extension. Hence, it holds that for each truth assignment γ for x1 , . . . , xn the fact that CAadw(γ,F (φ)) (a) is true implies that γ(φ) is true. We now prove that for each truth assignment γ for x1 , . . . , xn the fact that γ(φ) is true implies that CAad w(γ,F (φ)) (a) is true. Reasoning by contradiction assume that there exists a truth assignment γ for x1 , . . . , xn such that w = w(γ, F(φ)) and CAad w (a) is false while γ(φ) is true. Let S be the set of arguments {a} ∪ {xi | i ∈ [1..n] ∧ γ(Xi ) = true}. 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 Cj = Xh ∨ Xl and both xh ∈ / S and xl ∈ / S. Hence, by construction of S it holds that γ(Xh ) = γ(Xh ) = false which, in turn, implies that γ(φ) = false, thus contradicting that γ is a truth assignment γ for x1 , . . . , xn such that γ(φ) is true. This implies that for each truth assignment γ for x1 , . . . , xn the fact that γ(φ) is true implies that CAad w(γ,F (φ)) (a) is true. Lemma 2. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn } is the set of its propositional variables. For a possible world w ∈ pw(F(φ)) CAad sem w(γ,F (φ)) (a) is true iff CAw(γ,F (φ)) (a), where sem ∈{st, co, gr, sst, pr, ids, ide}, is true. Proof. The if part is straightforward since stable, complete, grounded, semi- stable, 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 0 according to sem, where sem ∈{st, co, gr, sst, pr, ids, ide }, such that a ∈ S 0 . Consider the set of arguments Ŝ = S ∪ (Arg(w) ∩ {x1 , . . . , xn }), and note that Arg(w) \ Ŝ = {c1 , . . . , ck }. It is straightforward to see that, since S is an admissible extension then Ŝ is an admissible extension. Moreover, it is easy to see Credulous acceptability... 11 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 argu- ment 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(φ)) CAad w(γ,F (φ)) (a) is true only if CAsemw(γ,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- CAsem is F P #P -hard. Proof. Given an instance φ of #P 2CN F , we construct an instance of P- CAsem by defining a PrAAF F = F(φ) as in Definition 4, and we return 2n · (P rCAsem F (a)). Since for each possible world w ∈ pw(F(φ)) we have that I(w) = 21n , from Lemmas 1 and 2 it follows that 2n · (P rCAsem 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-CAsem is a Cook reduction, this suffices to prove that P-CAsem is F P #P -hard, since a problem is F P #P -hard iff it is #P -hard. 4 RELATED WORK The main state-of-the-art approaches for handling uncertainty in AAFs by rely- ing 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 re- cent epistemic one [33, 29, 28]. As regards the epistemic approach, probabilities and extensions have a different semantics, compared with the constellations ap- proach. 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 12 Bettina Fazzinga et al. 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 prob- ability 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 prob- ability 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 as- sumed. 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 ev- ery 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 lit- erature, 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 polynomial- ity 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 fundamen- tal 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 ar- guments 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- Credulous acceptability... 13 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 con- nection 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 probabilis- tic 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 se- mantics (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 admis- sible, 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. 5 Conclusion and future works Focusing on the constellations approach with independence proposed in [30], in this paper we characterized the complexity of P-CAsem 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 com- puting 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-CAsem by identifying structural properties of the argumentation graph that will ensure that P-CAsem is solvable in polynomial time. References 1. Baroni, P., Caminada, M., Giacomin, M.: An introduction to argumentation se- mantics. Knowledge Eng. Review 26(4), 365–410 (2011) 2. Baroni, P., Giacomin, M.: Semantics of abstract argument systems. In: Argumen- tation in Artificial Intelligence, pp. 25–44 (2009) 3. Booth, R., Caminada, M., Dunne, P.E., Podlaszewski, M., Rahwan, I.: Complexity properties of critical sets of arguments. In: Proc. of Computational Models of Argument (COMMA). pp. 173–184 (2014) 4. Caminada, M.: Semi-stable semantics. In: Proc. Int. Conf. Computational Models of Argument (COMMA). pp. 121–130 (2006) 5. Coste-Marquis, S., Devred, C., Marquis, P.: Symmetric argumentation frameworks. In: Proc. of Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU). pp. 317–328 (2005) 6. Dimopoulos, Y., Torres, A.: Graph theoretical structures in logic programs and default theories. Theor. Comput. Sci. 170(1-2), 209–244 (1996) 14 Bettina Fazzinga et al. 7. Doder, D., Woltran, S.: Probabilistic argumentation frameworks - A logical ap- proach. In: Proc. Int. Conf. on Scalable Uncertainty Management (SUM). pp. 134–147 (2014) 8. Dondio, P.: Computing the grounded semantics in all the subgraphs of an argumen- tation framework: An empirical evaluation. In: Proc. Int. Workshop Computational Logic in Multi-Agent Systems (CLIMA). pp. 119–137 (2013) 9. Dondio, P.: Toward a computational analysis of probabilistic argumentation frame- works. Cybernetics and Systems 45(3), 254–278 (2014) 10. Dung, P.M.: On the acceptability of arguments and its fundamental role in non- monotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–358 (1995) 11. Dung, P.M., Mancarella, P., Toni, F.: Computing ideal sceptical argumentation. Artif. Intell. 171(10-15), 642–674 (2007) 12. Dung, P.M., Thang, P.M.: Towards (probabilistic) argumentation for jury-based dispute resolution. In: Proc. Int. Conf. Computational Models of Argument (COMMA). pp. 171–182 (2010) 13. Dunne, P.E.: The computational complexity of ideal semantics. Artif. Intell. 173(18) (2009) 14. Dunne, P.E., Bench-Capon, T.J.M.: Coherence in finite argument systems. Artif. Intell. 141(1/2), 187–203 (2002) 15. Dunne, P.E., Caminada, M.: Computational complexity of semi-stable semantics in abstract argumentation frameworks. In: Proc.European Conf. on Logics in Ar- tificial Intelligence (JELIA). pp. 153–165 (2008) 16. Dunne, P.E., Wooldridge, M.: Complexity of abstract argumentation. In: Argu- mentation in Artificial Intelligence, pp. 85–104 (2009) 17. Dvorák, W., Woltran, S.: Complexity of semi-stable and stage semantics in argu- mentation frameworks. Inf. Process. Lett. 110(11), 425–430 (2010) 18. Fazzinga, B., Flesca, S., Parisi, F.: Efficiently estimating the probability of ex- tensions in abstract argumentation. In: Proc. Int Conf. on Scalable Uncertainty Management (SUM). pp. 106–119 (2013) 19. Fazzinga, B., Flesca, S., Parisi, F.: On the complexity of probabilistic abstract argumentation. In: Proc. Int. Joint Conference on Artificial Intelligence (IJCAI) (2013) 20. Fazzinga, B., Flesca, S., Parisi, F.: On the complexity of probabilistic abstract argumentation frameworks. ACM Trans. Comput. Log. (TOCL) 16(3), 22 (2015) 21. Fazzinga, B., Flesca, S., Parisi, F.: On efficiently estimating the probability of extensions in abstract argumentation frameworks. Int. J. Approx. Reasoning 69, 106–132 (2016) 22. Fazzinga, B., Flesca, S., Parisi, F., Pietramala, A.: PARTY: A mobile system for efficiently assessing the probability of extensions in a debate. In: Proc. Int. Conf. on Database and Expert Systems Applications (DEXA). pp. 220–235 (2015) 23. Fazzinga, B., Flesca, S., Parisi, F., Pietramala, A.: Computing or estimating exten- sion’s probabilities over structured probabilistic argumentation frameworks. Spe- cial Issue on Probabilistic and other Quantitative Approaches to Computational Argumentation of the IfCoLog Journal of Logics and their Applications 3(2), 177– 200 (2016) 24. Gaggl, S.A., Woltran, S.: The cf2 argumentation semantics revisited. J. Log. Com- put. 23(5), 925–949 (2013) 25. Hunter, A.: Some foundations for probabilistic abstract argumentation. In: Proc. Int. Conf. Computational Models of Argument (COMMA). pp. 117–128 (2012) Credulous acceptability... 15 26. Hunter, A.: A probabilistic approach to modelling uncertain logical arguments. Int. J. Approx. Reasoning 54(1), 47–81 (2013) 27. Hunter, A.: Probabilistic qualification of attack in abstract argumentation. Int. J. Approx. Reasoning 55(2), 607–638 (2014) 28. Hunter, A., Thimm, M.: Probabilistic argumentation with epistemic extensions. In: Proc. Int. Workshop on Defeasible and Ampliative Reasoning (DARe@ECAI) (2014) 29. Hunter, A., Thimm, M.: Probabilistic argumentation with incomplete information. In: Proc. European Conf. on Artificial Intelligence (ECAI). pp. 1033–1034 (2014) 30. Li, H., Oren, N., Norman, T.J.: Probabilistic argumentation frameworks. In: Proc. Int. Workshop on Theorie and Applications of Formal Argumentation (TAFA) (2011) 31. Prakken, H.: An abstract framework for argumentation with structured arguments. Argument & Computation 1(2), 93–124 (2010) 32. Rienstra, T.: Towards a probabilistic dung-style argumentation system. In: AT. pp. 138–152 (2012) 33. Thimm, M.: A probabilistic semantics for abstract argumentation. In: Proc. Euro- pean Conf. on Artificial Intelligence (ECAI). pp. 750–755 (2012) 34. Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. (TCS) 8, 189–201 (1979)