On the Complexity of Probabilistic Abstract Argumentation

1 Introduction

Argumentation allows disputes to be modeled, which arise between two or more parties, each of them providing arguments to assert her reasons. Although argumentation is strongly related to philosophy and law, it has gained remarkable interest in AI as a reasoning model for representing dialogues, making decisions, and handling inconsistency and uncertainty [Bench-Capon and Dunne, 2007; Besnard and Hunter, 2008; Rahwan and Simari, 2009].

A simple but powerful argumentation framework is that proposed in the seminal paper [Dung, 1995], where the abstract argumentation framework (AAF) was introduced. An AAF is a pair 〈A, D〉 consisting of a set A of arguments, and of a binary relation D over A, called defeat (or, equivalently, attack) relation. Basically, an argument is an abstract entity that may attack and/or be attacked by other arguments. For instance, consider the following scenario (inspired by an example in [Hunter, 2013]), where we are interested in deciding whether to organize or not a BBQ party in our garden on Saturday. Assume that our decision should be taken considering the argument a, which is "Our friends will have great fun at the party", and the argument b, which is "Saturday will rain" (according to the BBC weather forecasting service). This scenario can be modeled by the AAF A, whose set of arguments is {a, b}, and whose defeat relation consists of the defeat δ = (b, a), meaning that the fun at the party is jeopardized if it rains.

∗The first and the second author were partially supported by the project PON01 01286 - eJRM.

Several semantics for AAFs, such as admissible, stable, preferred, complete, grounded, and ideal, have been proposed [Dung, 1995; Dung et al., 2007; Baroni and Giacomin, 2009] to identify "reasonable" sets of arguments, called extensions. Basically, each of these semantics corresponds to some properties which "certify" whether a set of arguments can be profitably used to support a point of view in a discussion. For instance, a set S of arguments is an extension according to the admissible semantics if it has two properties: it is conflictfree (that is, there is no defeat between arguments in S), and every argument (outside S) attacking an argument in S is counterattacked by an argument in S. Intuitively enough, the fact that a set is an extension according to the admissible semantics means that, using the arguments in S, you do not contradict yourself, and you can rebut to anyone who uses any of the arguments outside S to contradict yours. The other semantics correspond to other ways of determining whether a set of arguments would be a "good point" in a dispute, and will be described in the core of the paper. For any semantics sem, the fundamental problem of verifying whether a set S of arguments is an extension according to sem is denoted as VERsem(S), and its complexity, for the above-mentioned semantics, has been addressed in [Dunne and Wooldridge, 2009; Dunne, 2009].

As a matter of fact, in the real world, arguments and defeats are often uncertain, thus, several proposals have been made to model uncertainty in AAFs, by considering weights, preferences, or probabilities associated with arguments and/or defeats. In this regard, [Dung and Thang, 2010; Li et al., 2011; Thimm, 2012; Rienstra, 2012] have recently extended the original Dung framework in order to achieve probabilistic abstract argumentation frameworks (PrAFs), where uncertainty of arguments and defeats is modeled by exploiting the probability theory. In particular, [Li et al., 2011] proposed a PrAF where both arguments and defeats are associated with probability values. For instance, a PrAF FA can be obtained from the AAF A by considering the arguments a, b, and the defeat δ as probabilistic events, having probabilities Pr(a) = .9, Pr(b) = .7, and Pr(δ) = .9. Basically, this means that there is some uncertainty about the fact that our friends will have fun at the party, about the truthfulness of the BBC weather forecasting service, and about the fact that the bad weather forecast actually entails that the party will be disliked by our friends.

The issue of how to assign probabilities to arguments and defeats in abstract argumentation, with particular reference to the PrAF proposed in [Li et al., 2011], has been deeply investigated in [Hunter, 2012; 2013], where the justification and the premise perspectives have been introduced. In this paper, we do not address this issue, but, assuming that the probabilities of arguments and defeats are given, we tackle the probabilistic counterpart of the problem VERsem(S), that is, the problem PROBsem F (S) of computing the probability P rsem F (S) that a set S of arguments is an extension according to a given semantics sem. To this end, we consider the PrAF proposed in [Li et al., 2011], which is based on the notion of possible world. Basically, given a PrAF F, a possible world represents a (deterministic) scenario consisting of some subset of the arguments and defeats in F. Hence, a possible world can be viewed as an AAF containing exactly the arguments and the defeats occurring in the represented scenario. For instance, considering the above-introduced PrAF FA, the possible world 〈{a}, ∅〉 is the AAF representing the scenario where only a occurs, while the possible world 〈{a, b}, {δ}〉 is the AAF representing the scenario where all the arguments and defeats occur.

In [Li et al., 2011] it was shown that a PrAF admits a unique probability distribution over the set of possible worlds, which assigns a probability value to each possible world coherently with the probabilities of arguments and defeats. This follows from the assumption that arguments are viewed as pairwise independent probabilistic events, while each defeat is viewed as a probabilistic event conditioned by the occurrence of the arguments it relates, but independent from any other event. Once shown that a PrAF admits a unique probability distribution over the set of possible worlds, the probability Prsem F (S) is naturally defined as the sum of the probabilities of the possible worlds where the set S of arguments is an extension according to the semantics sem. Unfortunately, as pointed out in [Li et al., 2011], computing P rsem F (S) by directly exploiting its definition would result in an exponential time algorithm. However, this does not mean that PROBsem F (S) is intractable, since it does not rule out the possibility that polynomial time algorithms for computing P rsem F (S) exist. Hence, the point becomes: what actually is the computational cost of computing Prsem F (S)? To the best of our knowledge this question has not been answered so far.

Main contributions. In this paper, we characterize the computational complexity of the problem PROBsem F (S) of computing Prsem F (S), where sem is one of the following semantics: admissible, stable, complete, grounded, preferred, ideal. The complexity of PROBsem F (S) is reported in (the rightmost column of) Table 1, which, for the sake of completeness, also reports the results concerning VERsem(S) [Dunne and Wooldridge, 2009; Dunne, 2009].

Our results are interesting from two standpoints. First, comparing the complexity of PROBsem F (S) with that of its deterministic counterpart VERsem(S) shows that (i) for some semantics (that is, complete and grounded) VERsem(S) is tractable while PROBsem F (S) is not; (ii) for other semantics (that is, admissible and stable) the two problems are both tractable; and, finally, there are semantics (that is, preferred and ideal) for which these problems are both intractable.

Second, our complexity analysis allows us to understand for which semantics computing P rsem F (S) is feasible in practice or not. Indeed, [Li et al., 2011] claimed that computing the exact value of probability Prsem F (S) requires exponential time, and then proposed a Monte-Carlo simulation approach to approximate Prsem F (S). The claim of [Li et al., 2011] is based on the implicit assumption that, in order to compute P rsem F (S), it is necessary to look at all the possible worlds of F, which are exponential in number. However, as far as the admissible and stable semantics are concerned, our results show that the exact value of Prsem F (S) can be determined in polynomial time, without enumerating the possible worlds. Hence, using approximate techniques for estimating P rsem F (S) is not needed for these semantics. In contrast, the fact that PROBsem F (S) is FP #P -complete for the other semantics (complete, grounded, preferred, ideal) backs the use of the approach of [Li et al., 2011] in these cases.

2 Preliminaries

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 [Li et al., 2011].

2.1 Complexity

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 [Valiant, 1979]. 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 FP #P , that is, the class of functions computable by a polynomial-time Turing machine with a #P oracle.

In the following, we will show that, depending on the adopted semantics, the problem PROBsem F (S) of computing P rsem F (S) belongs to either FP #P or PTIME. We also show lower bounds on the complexity of PROBsem F (S). In this regard, note that a function is FP #P -hard iff it is #P-hard, and thus to prove that a problem is FP #P -hard it suffices to reduce a #P -hard problem to it.

2.2 Abstract Argumentation

An abstract argumentation framework [Dung, 1995] (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.

Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions. We consider the following well-known semantics [Dung, 1995; Dung et al., 2007]: admissible (ad), stable (st), complete (co), grounded (gr), preferred (pr), and ideal (id).

A set S ⊆ A of arguments 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 preferred extension iff S is a maximal (w.r.t. ⊆) admissible set of arguments;
• an ideal extension iff S is admissible and S is contained in every preferred set of arguments.

Note that, with a little abuse of notation, we denote as ideal extension what in the literature is often denoted as ideal set.

Example 1 Consider the AAF 〈A, D〉 obtained by extending the AAF A = 〈{a, b}, {δ1 = (b, a)}〉 presented in the introduction as follows. The set A of arguments is {a, b, c}, where c is the new argument "Saturday will be sunny" (according to the Telegraph weather forecasting service). 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. 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 stable. 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 (since it is not contained in {b} which is a preferred extension).

Given an AAF A, a set S ⊆ Arg(A) of arguments, and a semantics sem ∈ {ad, st, co, gr, pr, id}, we define the function ext(A, sem, S) which returns true if S is an extension according to sem, false otherwise.

2.3 Probabilistic Abstract Argumentation

We now review the probabilistic abstract argumentation framework proposed in [Li et al., 2011].

Definition 1 (PrAF) A probabilistic argumentation framework (PrAF) is a tuple 〈A, PA,D, PD〉 where 〈A,D〉 is an AAF, and PA and PD are, respectively, functions assigning a non-zero 1 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 probability 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 PrAF is given in terms of possible worlds, each of them representing a scenario that may occur in the reality. Given a PrAF 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 PrAF F = 〈A, PA,D, PD〉, 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 2 As a running example, consider the PrAF F = 〈A, PA, D, PD〉 where A and D are those of Example 1, and assume that PD(δ2) = PD(δ3) = 1 (meaning that arguments b and c attack each other in all the possible scenarios), and that PA(c) = .2 (this corresponds to the assumption that the Telegraph weather forecasting service has a low reliability). Furthermore, recall that PA(a) = .9, PA(b) = .7, PD(δ1) = .9, as defined in the introduction. The set pw(F) contains the following possible worlds:

An interpretation for a PrAF F = 〈A, PA,D, PD〉 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 PrAF F = 〈A, PA, D, PD〉 is as follows. For each possible world w ∈ pw(F), w is assigned by I the probability:

1 Assigning probability equal to 0 to arguments/defeats is useless.

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 3 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 ̸∈ Def(w) or δ3 ̸∈ Def(w), then I(w) = 0. The probabilities of the other possible worlds are the following:

The probability that a set S of arguments is an extension according to a given semantics sem is defined as the sum of the probabilities of the possible worlds w for which S is an extension according to sem, i.e., ext(w, sem, S) = true.

F (S)) Given a PrAF F, a set S of arguments, and a semantics sem, the probability Prsem F (S) that

Definition 2 (Prsem S is an extension according to sem is

The following example shows usages of this definition.

Example 4 In our running example, the probabilities that the sets S1 = {b}, and S2 = {ac} are admissible are as follows: P rad F (S1)=I(w3)+I(w5)+I(w9)+I(w12)+I(w16)+I(w19)=.7 P rad F (S2) = I(w6)+ I(w16)+ I(w19)= .18

It is easy to see that, as S2 is stable in the same possible worlds where it is admissible, Prst F (S2) = Prad F (S2). The probability that S1 is stable is as follows: Prst F (S1) = I(w3) + I(w9)+ I(w12) + I(w16) = .637 .

Obviously, computing P rsem F (S) by directly applyingDefinition 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 Prsem F (S) exist. In fact, in the next section we determine tractable and intractable cases for the problem of computing Prsem F (S).

3 Complexity of Probabilistic Argumentation

We characterize the complexity of the following problem.

Definition 3 (Problem PROB sem F (S)) Given a PrAF F = 〈A, PA,D, PD〉, a set S ⊆ A of arguments, and a semantics sem in {ad, st, co, gr, pr, id}, PROBsem F (S) is the problem of computing Prsem F (S).

In the complexity analysis, the size of the input of our problem is the sum of the sizes of A and D 2 .

Our results are summarized in the rightmost column of Table 1. We first show that PROBsem F (S) is tractable for the admissible and stable semantics (Section 3.1). Next, we provide lower and upper bounds on the complexity PROBsem F (S) for the other semantics (Section 3.2).

Due to space limitations, we only give a hint on some of the proofs of our results.

3.1 Tractable Cases

We first show that PROB ad F (S) can be solved in polynomial time. Then, we show a similar result for the stable semantics.

The tractability of PROB ad F (S) follows from the following lemma, which states that Prad F (S) can be determined by evaluating an expression which only involves the probabilities of the arguments and defeats of the PrAF.

This lemma can be proved by observing that the fact that a set S of arguments is admissible can be expressed as the probabilistic event E(S) = e1(S) ∧ e2(S) ∧ e3(S), where:

• e1(S) is the event that all of the arguments in S occur;
• e2(S) is the event that, given that e1(S) holds, S is conflict-free; and
• e3(S) is the event that, given that e1(S) holds, for all the arguments d in A\ S, one of the following events holds:
• e31(S, d): d does not occur,
• e32(S, d): d occurs and no defeat (d, b), with b∈S, occurs,
• e33(S, d): d occurs, there is at least one argument b ∈ S such that (d, b) occurs, and there is at least one argument a ∈ S such that (a, d) occurs.

We point out that the occurrence of events e2(S) and e3(S) is conditioned by the occurrence of event e1(S), and that e2(S) and e3(S) are independent from one another. Moreover, for each pair of distinct arguments d′ , d′′ ∈ A/S, subevents e31(S, d′ ), e32(S, d′ ) and e33(S, d′ ) are independent from subevents e31(S, d′′ ), e32(S, d′′ ) and e33(S, d′′ ). Finally, note that, for each d ∈ A/S, subevents e31(S, d), e32(S, d) and e33(S, d) are mutually exclusive.

2 The sizes of the rational numbers encoding the probabilities of arguments and defeats are assumed to be bounded by a constant.

3 Note that, an empty product evaluates to 1.

Starting from the above considerations, it can be shown that P r(E(S)) = P r(e1(S)) · P r(e2(S)) · P r(e3(S)), where Pr(ei) denotes the probability of event ei. Moreover, it is easy to see that Pr(e1(S)) (resp., Pr(e2(S))) is equal to the value of expression P1(S) (resp., P2(S)) given in Lemma 1. Furthermore, it can be shown that Pr(e3(S)) is equal to P3(S) = ∏ d∈A\S (P31(S, d) + P32(S, d) + P33(S, d)), where P31(S, d), P32(S, d) and P33(S, d) are the probabilities of the mutually exclusive events e31(S, d), e32(S, d), and e33(S, d), respectively.

Example 5 Continuing our running example, where S1 = {b} and S2 = {a, c}, Prad F (S1) can now be computed by applying Lemma 1 :

The result of Lemma 1 allows us to give a polynomial time algorithm to solve PROB ad F (S): evaluate the expression of Lemma 1 by iterating on the arguments and defeats in the PrAF F. The complexity this algorithm is as follows.

We now address the problem of computing the probability that a given set S of arguments is stable for a given PrAF F. We show that PROB st F (S) can be solved in polynomial time by exploiting the result of the following lemma.

Lemma 2 Given a PrAF F = 〈A, PA,D, PD〉, and a set S ⊆ A, Prst F (S) = P1(S) · P2(S) · P3(S), where P1(S) and P2(S) are defined as in Lemma 1 and P3(S) = ∏ d∈A\S (P31(S, d) + P32(S, d)), where

Similar to the case of admissible semantics, the fact that a set S of arguments is stable can be expressed as the probabilistic event E′ (S) = e1(S) ∧ e2(S) ∧ e′3 (S), where:

• e1(S) and e2(S) are the events introduced after Lemma 1, and
• e′3 (S) is the event that, given that e1(S) holds, for all the arguments d in A\ S, one of the following events holds:
• e31(S, d): d does not occur,
• e′32 (S, d): d occurs and it is defeated by S, that is, at least one defeat (a, d), with a ∈ S, occurs.

Reasoning analogously to the case of Lemma 1 it can be shown that Pr(E′ (S)) is equal to P1(S)· P2(S)· P3(S).

Example 6 Considering again our running example, from Lemma 2 we have that:

The complexity of an algorithm for solving PROB st F (S), by exploiting Lemma 2, is stated in the following theorem.

Theorems 1 and 2 show that, for the admissible and stable semantics, the problem of computing Prsem F (S) is tractable. Thus, for PROB ad F (S) and PROB st F (S) there is no need to resort to approximate techniques for estimating Prad F (S) and P rst F (S), as instead proposed in [Li et al., 2011] where a Monte-Carlo simulation approach is adopted. In fact, our results show that PROB ad F (S) and PROB st F (S) belong to the same complexity class as VER ad(S) and VER st(S).

3.2 Hard Cases

We now characterize the computational complexity of the problem of computing the probability that a given set of arguments is an extension according to the complete, grounded, preferred, and ideal semantics. Specifically, we show that the lower bound on the complexity of PROBsem F (S) for each of these semantics is FP #P . This result motivates the use of approximate strategies, such as those adopted in [Li et al., 2011], when dealing with these kinds of extensions. Moreover, we show that FP #P is also an upper bound on the complexity of PROBsem F (S) for each of these semantics, thus providing a tight complexity characterization for PROBsem F (S).

Theorem 3 For sem ∈ {co, gr, pr, id}, it holds that PROBsem F (S) is FP #P -complete.

We give a hint on the FP #P -hardness proof of Theorem 3. The FP #P hardness of PROBsem F (S) for sem∈{co, gr} is shown by providing a Cook reduction to our problem from the #P -hard problem #PP2DNF (Partitioned Positive 2DNF) [Provan and Ball, 1983], that is, the problem of counting the number of satisfying assignments of a DNF formula φ = C1∨C2∨. . .∨Ck whose propositional variables are positive and can be partitioned into two sets X = {x1, . . . , xn} and Y = {y1, . . . , ym}, and each clause Ci has the form xj ∧ yℓ, with xj ∈ X and yℓ ∈ Y .

Given a #PP2DNF instance φ, we construct the PrAF Fφ = 〈A, PA,D, PD〉 such that (i) A contains an argument for each propositional variable in φ, an argument cℓ for each clause Cℓ of φ, and an argument s; (ii) D contains the defeats (xi, cℓ) and (yj, cℓ) for each clause Cℓ = xi ∧ yj of φ, and the defeats (s, xi) and (xi, xi) (resp., (s, yj) and (yj , yj)) for each variable xi (resp., yj) of φ; (iii) PA assigns probability 1 to all the arguments in A; PD assigns probability 1 to all the defeats in D except the defeats (s, xi) and (s, yj), which are assigned .5. As an example of this construction, the PrAF Fφ′ resulting fromφ′ = (x1∧y1)∨(x2∧y1)∨(x3∧y2)∨(x3∧y3) is represented by the direct graph shown in Figure 1(a). In this graph, (i) every node represents an argument, (ii) every edge represents a defeat, and (iii) for each argument/defeat, its probability (if different from 1) is specified near to it.

(b) Possible world wτ ′

It can be shown that there is a bijection b : T → pw(F) between the set T of truth assignments of φ and the set pw(F) of possible worlds. For instance, in the example above, the truth assignment τ ′ = x1/1, x2/0, x3/0, y1/1, y2/0, y3/0 for φ′ one-to-one corresponds to the world wτ ′ shown in Figure 1(b), where the fact that variable x1 (resp., y1) is assigned 1 by τ is encoded by the occurrence of the defeat (s, x1) (resp., (s, y1)) in wτ ′ .

We proved that, given a truth assignment τ for the variables of φ, φ evaluates to true under τ iff S = {s} is not a complete extension in the world w = b(τ). Continuing our example, it is easy to see that the truth assignment τ ′ makes φ′ true and {s} is not a complete extension in wτ ′ since s defeats both x1 and y1 which makes c1 acceptable w.r.t {s}.

Furthermore, it can be shown that the number of satisfying assignments #φ of φ is equal to 2n+m · (1-Prco F ({s})), which completes the FP #P -hardness proof for PROB co F (S).

To summarize, our complexity analysis shows that, while the problem VERsem(S) of verifying whether a set S of arguments is an extension according to sem is intractable only for the preferred and the ideal semantics, its probabilistic counterpart PROBsem F (S) results to be intractable for the grounded and the complete semantics as well.

4 Related work

Recently approaches for handling uncertainty in AAFs by relying on probability theory have been proposed in [Dung and Thang, 2010; Rienstra, 2012; Li et al., 2011; Thimm, 2012]. With the aim of modeling jury-based dispute resolutions, [Dung and Thang, 2010] proposed a PrAF where uncertainty is taken into account by specifying probability distribution functions (PDFs) over possible worlds and shown how an instance of the proposed PrAF can be obtained by specifying a probabilistic assumption-based argumentation framework (introduced by themselves). In the same spirit, [Rienstra, 2012] defined a PrAF as a PDF over the set of possible worlds, and introduced a probabilistic version of a fragment of ASPIC framework [Prakken, 2010] that can be used to instantiate the proposed PrAF. Differently from the two previous approaches, [Li et al., 2011] proposed a PrAF where probabilities are directly associated with arguments and defeats, instead of being associated with possible worlds. [Li et al., 2011] claimed that computing the probability Pr(S) that a set S of arguments belongs to an extension requires exponential time for every semantics, and then proposes a MonteCarlo simulation approach to approximate Pr(S). In [Li et al., 2011], as well as in [Dung and Thang, 2010], [Rienstra,

2012], Pr(S) is defined as the sum of the probabilities of the possible worlds where S is an extension, according to a given semantics. [Thimm, 2012], instead, did not define a probabilist version of a classical semantics, but introduced a new probabilistic semantics. This semantics is based on specifying a class of PDFs, called p-justifiable PDFs, over sets of possible AAFs, and shown that this probabilistic semantics generalizes the complete semantics.

Though in the above-cited works probability theory is recognized as a fundamental tool to model uncertainty, a deeper understanding of the role of probability theory in abstract argumentation was developed only later in [Hunter, 2012; 2013], where the connection among argumentation theory, classical logic, and probability theory was investigated.

Besides the approaches that model uncertainty in AAFs by relying on probability theory, many proposals have been made where uncertainty is represented by exploiting weights or preferences on arguments and/or defeats [Bench-Capon, 2003; Amgoud and Vesic, 2011; Amgoud and Cayrol, 2002; Modgil, 2009; Dunne et al., 2011; Coste-Marquis et al., 2012], or by relying on the possibility theory [Amgoud and Prade, 2004; Alsinet et al., 2008a; 2008b].

Although the approaches based on weights, preferences, possibilities, or probabilities to model uncertainty have been proved to be effective in different contexts, there is no common agreement on what kind of approach should be used in general. In this regard, [Hunter, 2012; 2013] observed that the probability-based approaches may take advantage from relying on a well-established and well-founded theory, whereas the approaches based on weights or preferences do not conform to well-established theories yet.

The computational complexity of computing extensions has been throughly investigated for AAFs [Dunne and Wooldridge, 2009; Dunne, 2009], for the case of adding weights to AAFs [Dunne et al., 2011; Coste-Marquis et al., 2012], and for the case of using preferences [Amgoud and Vesic, 2011]. To the best of our knowledge, this work is the first one characterizing the computational complexity of the problem of computing the probability that a set of arguments is an extension according to a given semantics.

5 Conclusions and future work

In this paper we focused on the probabilistic argumentation framework proposed in [Li et al., 2011], and characterized the complexity of computing the probability that a set of arguments is an extension according to a given semantics. We showed that the complexity of this problem is either PTIME or FP #P , depending on the considered semantics. Extending the complexity study presented in this paper to other AAF semantics, such as the semi-stable [Caminada, 2006], the stage [Caminada, 2010], the CF2 [Baroni et al., 2005] and the prudent [Coste-Marquis et al., 2005] semantics, is an interesting direction for future work. Another promising direction is that of characterizing the complexity of the probabilistic version of the credulous/sceptical acceptance problem, that is, the problem of computing the probability that an argument belongs to any/every extension according to a given semantics.