Probabilistic bipolar abstract argumentation frameworks: complexity results

1 Introduction

An abstract argumentation framework (AAF) represents a dispute as an argumentation graph 〈A, D〉, where A is the set of nodes (called arguments) and D is the set of edges (called defeats or attacks). Herein, an argument is an abstract entity that may attack and/or be attacked by other arguments, where "a attacks b" means that argument a rebuts/weakens b. Given this, reasoning on the possible strategies for winning the dispute typically requires looking into the extensions of the AAF, i.e. a set of arguments that satisfies some properties certifying its "strength". Different semantics for AAFs have proven reasonable, such as admissible (ad), stable (st), preferred (pr), complete (co), grounded (gr), ideal (id) [Dung, 1995; Dung et al., 2007; Baroni and Giacomin, 2009], and the complexity of the problem EXT of verifying whether a set is an extension has been studied under each of these semantics [Dunne and Wooldridge, 2009; Dunne, 2009].

Since the introduction of AAFs in [Dung, 1995], many variants have been proposed, with the aim of modeling disputes more accurately. Among these, Bipolar Abstract Argumentation Frameworks (BAFs) allow supports, besides attacks, to be specified between arguments. Specifically, two alternative formal semantics of support have been introduced: in [Cayrol and Lagasquie-Schiex, 2005], the support is a generic "inverse" of the notion of attack ("abstract semantics": "a supports b" means that there is a positive interaction between a and b - from a to b), while, in [Boella et al.,

2010], it is viewed as a "deductive" correlation between arguments ("deductive semantics": if a supports b, the acceptance of a implies the acceptance of b). The various extensions' semantics defined for AAFs have been shown to have a natural counterpart over BAFs, after noticing that combining attacks with supports (of any semantics) generates "implicit" attacks.

Example 1 The graph in Figure 1 is a BAF with six arguments a, b, c, d, e, f . The dashed and standard arrows denote supports and attacks, respectively. The co-existence of supports and attacks entails the existence of implicit attacks. For instance, under both the abstract and deductive semantics, the fact that a strengthens b and b attacks c implicitly says that a attacks c. This kind of implicit attack is often called "supported attack". If the deductive semantics is adopted, there are other forms of implicit attacks. For instance, since a supports b and e attacks b, there is an implicit attack from e to a. Otherwise, a would be acceptable while b would be not, thus contradicting the deductive support from a to b.

Other variants of AAFs are those addressing the representation of uncertainty. In this regard, probabilistic AAFs (prAAFs) are a popular paradigm, and in particular those following the constellation approach. Here, the dispute is modeled as a set of possible scenarios, each consisting of a standard AAF (called possible AAF) associated with a probability of representing all and only the arguments and attacks actually occurring in the dispute. In particular, two main paradigms have been adopted for specifying the probability distribution function (pdf), called EX and IND. In the general case, the extensive form EX is used, where the each possible AAF must be explicitly specified along with its probability. Otherwise, when independence between arguments/attacks is assumed, the form IND can be used, where the probabilities of the possible scenarios are represented implicitly by specifying the marginal probabilities of the arguments and attacks. For both EX and IND, the complexity of the probabilistic counterpart P-EXT of EXT (asking for the probability that a set of arguments is an extension) has been characterized in [Fazzinga et al., 2016].

In this paper, we consider the probabilistic Bipolar Argumentation Framework (prBAF), where the bipolarity of BAFs is combined with the probabilistic modeling of the uncertainty of prAAFs, and characterize the complexity of reasoning on extensions. In our analysis, we start by observing that the introduction of supports in the deterministic case does not increase the complexity of verifying extensions, meaning that EXT over BAFs (for both supports' semantics) has the same complexity as over AAFs. Then, we show that allowing supports can introduce a new source of complexity when probabilities are considered: under the admissible and stable semantics, and under the paradigm IND, for which P-EXT is polynomial over prAAFs, the problem P-EXT becomes intractable over prBAFs. For these cases, we give an insight on this behavior by showing sufficient conditions restoring the polynomiality of P-EXT. Table 1 summarizes our results.

Related Work. [Cayrol and Lagasquie-Schiex, 2005] first introduced BAFs, where supports have the general "abstract" semantics of positive interactions between arguments. Later, three more specific interpretations for supports have been proposed: [Boella et al., 2010], [Nouioua and Risch, 2010] and [Oren and Norman, 2008] introduced the deductive, necessary, and evidential semantics for the support relation, respectively. In this paper, we focus on the abstract and deductive semantics, but our results also hold for necessary supports (as shown in [Cayrol and Lagasquie-Schiex, 2013], they are dual to deductive ones). [Cayrol and LagasquieSchiex, 2013] reviews the four different semantics for supports, and discusses the similarities and differences among these interpretations. [Cohen et al., 2012] introduces a more general framework that incorporates attacks, supports and a preference relation.In [Mart´ınez et al., 2006], subarguments in AAF have been introduced, that in [Cohen et al., 2014] have been shown to be closely related with the necessary support. Other related works are [Brewka and Woltran, 2010; Verheij, 2009] where, although supports are not mentioned, similar dependencies have been considered. A detailed survey over BAFs can be found in [Cohen et al., 2014].

As regards uncertainty in AAFs, the approaches based on probability theory can be classified in two categories: those adopting the classical constellations approach [Hunter, 2014;

Rienstra, 2012; Doder and Woltran, 2014; Dondio, 2014; Hunter, 2012; Li et al., 2011; Fazzinga et al., 2013; Fazzinga et al., 2015] and those adopting the recent epistemic one [Thimm, 2012; Hunter and Thimm, 2014b; Hunter and Thimm, 2014a]. The former category has the two subcategories EX [Rienstra, 2012; Dondio, 2014] and IND [Doder and Woltran, 2014; Li et al., 2011; Fazzinga et al., 2013; Fazzinga et al., 2015], described in the paper. The interested reader can find a more detailed comparative description of the two categories in [Hunter, 2013]. Furthermore, 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; Modgil, 2009; Dunne et al., 2011; Coste-Marquis et al., 2012]. Although these approaches have proved effective in different contexts, there is no common agreement on what kind of approach should be used in general. In this regard, [Hunter, 2012; Hunter, 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. Finally, recent works [Proietti, 2017; Polberg and Hunter, 2018] investigate the need for extending BAFs with probabilities.

2 Preliminaries

We now review Bipolar Abstract Argumentation Frameworks (BAFs) and the concepts of support, attack and defense, along with the most popular extensions' semantics over BAFs.

2.1 Bipolar Abstract Argumentation Frameworks

Definition 1 [BAF] A bipolar abstract argumentation framework (BAF) is a tuple F = 〈A,Ra,Rs〉, where A is a set of arguments, Ra ⊆ A × A is a defeat/attack relation and Rs ⊆ A×A is a support relation.

In the first proposal of BAF [Cayrol and Lagasquie-Schiex, 2005], supports are given an abstract semantics, that is the opposite of the traditional semantics of attack, inherited from classical AAFs. This was shown to make the combination of supports and attacks imply the so-called supported attacks 1 .

Definition 2 [Supported attack] Let F = 〈A,Ra,Rs〉 be a BAF, and a, b ∈ A. There is a supported attack from a to b iff there is a sequence a1R1 . . .Rn-1an, with n ≥ 2, where a1 = a, an = b, ∀i ∈ [1..n - 2] Ri = Rs, and Rn-1 = Ra.

Example 2 In the BAF in Figure 1, there is a supported attack from a to c. Also the three direct attacks (e, b), (b, c) and (f, d) are special cases of supported attack.

Besides the abstract, other semantics have been proposed for supports (see Related Work). In particular, we consider the well-established deductive semantics, first proposed in [Boella et al., 2010]. Here, "a supports b" is interpreted as a strong correlation between a and b, meaning that if a is acceptable, then b is acceptable too. As observed in [Cayrol and Lagasquie-Schiex, 2013], under this semantics, a new form of implicit attack, called d-attack, must be considered.

1 [Cayrol and Lagasquie-Schiex, 2005] discussed also indirect implicit attacks. W.l.o.g., as in [Cayrol and Lagasquie-Schiex, 2009], we disregard them, as they would not affect our results.

Definition 3 [d-attack] Given a BAF F = 〈A,Ra,Rs〉 and a, b ∈ A, there is a d-attack from a to b iff

• aRab, or
• there is an argument a′ such that there is a path from a to a′ consisting of only support edges, and a′ attacks b, or
• there is an argument a′ such that there is a path from b to a′ consisting of only support edges, and a attacks a′ .

Example below shows that d-attacks include supported attacks, but can be also of the form of supermediated attacks (described by the last point in Definition 3).

Example 3 Under the deductive semantics for supports, in the BAF of Figure 1, it is easy to see that the supported attacks reported in Example 2 are d-attacks. Further d-attacks are the supermediated attacks from e to a, and from f to c.

In order to analyze what changes when moving from one semantics of supports to the other , we partition BAFs into two classes: s-BAFs and d-BAFs, where only supported attacks and d-attacks are considered, respectively. From now on, we assume the presence of a BAF F = 〈A, Ra, Rs〉, and, when needed, we will specify whether F is an s- or a d- BAF.

Definition 4 [Set-support] A set S ⊆ A set-supports an argument a ∈ A iff there is an argument a′ ∈ S such that there is a path from a′ to a consisting of only support edges.

Definition 5 [Set-attack] Let F = 〈A,Ra,Rs〉 be an s-BAF (resp., d-BAF). A set S ⊆ A set-attacks a ∈ A iff there is a supported attack (resp., d-attack) from some b ∈ S to a.

Definition 6 [Set-defense] A set S ⊆ A set-defends an argument a ∈ A iff, ∀b ∈ A, if {b} set-attacks a then ∃c ∈ S such that {c} set-attacks b.

Example 4 Consider the BAF F in Figure 1. Independently from supports' semantics, {a, e} both set-supports and setattacks b, and also set-attacks c. If F is an s-BAF, then {a, e} does not set-defend c, since there is a supported attack from a to c, and no attack from e to a. Observe that {a, e} does not set-defend c if F is a d-BAF either.

2.2 Semantics

We first recall the notions of conflict-freeness and safety.

Definition 7 [Conflict-free and safe sets of arguments] A set of arguments S ⊆ A is:

• conflict-free iff ̸ ∃ a, b ∈ S such that {a} set-attacks b;
• safe iff ̸ ∃b ∈ A such that S set-attacks b and either S set-supports b or b ∈ S.

Example 5 If the BAF F in Figure 1 is an s-BAF, both {a, e}, and {f, c} are conflict-free but not safe, while both {a, b, f} and {a, b, d} are conflict-free and safe. If F is a d-BAF, both {a, e}, and {f, c} are not conflict-free, while both {a, b, f} and {a, b, d} are still conflict-free and safe.

All the most popular semantics of extensions of "standard" AAFs have been extended to the case of BAFs [Cayrol and Lagasquie-Schiex, 2005]. We start with the stable semantics.

Definition 8 [Stable extension] A set of arguments S ⊆ A is a stable extension iff S is conflict-free and ∀a ∈ A\S it holds that S set-attacks a.

Due to the presence of supports and the fact that, in BAFs, conflict-freeness and safety do not coincide, for some AAF's semantics, different variants are considered when moving to BAFs. This is the case of the admissible semantics.

Definition 9 [Admissible extension] A set S ⊆ A is

• a d-admissible extension iff S is conflict-free and setdefends all of its arguments;
• an s-admissible extension iff S is safe and set-defends all of its arguments;
• a c-admissible extension iff S is conflict-free, closed for Rs and set-defends all of its arguments.

In turn, the other semantics subsuming the admissible one are defined as follows. A set S ⊆ A is said to be:

• a d-complete (resp. s-complete, c-complete) extension iff S is d-admissible (resp., s-admissible, c-admissible) and S contains all the arguments set-defended by S;
• a d-grounded (resp. s-grounded, c-grounded) extension iff S is a minimal (w.r.t. ⊆) d-complete (resp. s-complete, c-complete) extension;
• a d-preferred (resp. s-preferred, c-preferred) extension iff S is a maximal (w.r.t. ⊆) d-complete (resp. s-complete, c-complete) extension;
• a d-ideal (resp. s-ideal, c-ideal) extension iff S is a maximal (w.r.t. ⊆) d-admissible (resp. s-admissible, c-admissible) extension and S is contained in every dpreferred (resp. s-preferred, c-preferred) extension.

We denote the set {d-ad, s-ad, c-ad, st, d-co, s-co, c-co, d-gr, c-gr, c-gr, d-pr, s-pr, c-pr, d-id, s-id, c-id} consisting of the above semantics as SEM (herein, st means stable, d-ad d-admissible, s-ad s-admissible, and so on).

Example 6 Consider the BAF in Figure 1. {a, b, f}, although conflict-free and safe, is not a d-ad extension for both s-BAF and d-BAF (since b is not set-defended). Furthermore, for the s-BAF case, {a, f} is a s-ad, s-gr and s-pr extension, {a, e, f} is a st, d-ad, d-gr, d-pr, and d-id extension, {f} is an s-id extension, {e, f} is a c-pr, c-gr and c-id extension.

For the d-BAF case we have: {e, f} is the unique stable extension, that is also c-preferred, c-grounded and c-ideal.

The fundamental problem of verifying whether a set S of arguments is an extension over a given BAF under a semantics sem ∈ SEM will be denoted as EXTsem(S). Given a BAF F = 〈A,Ra,Rs〉, a set S ⊆ A, and a semantics sem ∈ SEM, we define the boolean function ext(F, sem, S) returning true iff S is an extension under sem.

3 Probabilistic BAFs (prBAFs)

We now consider the extension of BAFs where uncertainty is addressed and modeled probabilistically as in "traditional" probabilistic AAFs - prAAFs. A probabilistic BAF (prBAF) F is a tuple F = 〈A,Ra,Rs,P〉, where F = 〈A,Ra,Rs〉 is a BAF and P is a probability distribution function (pdf) over the set PS = {α = 〈A′ ,R′a ,R′s 〉 |A′ ⊆ A∧ R′a ⊆

(A′ ×A′ )∩Ra∧R′s ⊆ (A′ ×A′ )∩Rs}. That is, the elements in PS(F), called possible scenarios or possible BAFs, are the alternative cases of dispute that may occur, and each of them is encoded by a BAF. Then, P assigns to each possible BAF the probability that it describes the actual dispute.

As happens with prAAFs, we consider two encodings of the pdf over the possible BAFs, namely EX and IND. That is, a prBAF F of form EX is a tuple 〈A,Ra,Rs, ⃗α, ⃗P〉, where A, Ra and Rs are sets of arguments, attacks and supports, respectively, while ⃗α ⊆ PS(F) is the sequence ⃗α = α1, . . . , αm of the possible BAFs that are assigned nonzero probability and ⃗P = P(α1), . . . , P(αm) are their probabilities. The size of a prBAF 〈A,Ra,Rs, ⃗α, ⃗P〉 of form EX is thus O((|A| + |Ra| + |Rs|) · (|⃗α| + | ⃗ P|)). Obviously, the form EX allows any pdf (encoding any correlation between arguments/attacks/supports) to be represented. Otherwise, when independence is assumed (thus, no correlation must be encoded), the more compact paradigm IND can be used. A prBAF of type IND is a tuple 〈A,Ra,Rs,PA,PR〉 where A = {a1, . . . , am}, Ra = {δ1, . . . , δn} and Rs = {σ1, . . . , σk} are the sets of arguments, attacks and supports, respectively, and PA = {P(a1), . . . , P(am)}, PR = {P(δ1), . . . , P(δn), P(σ1), . . . , P(σk)} are their marginal probabilities. The pdf P over the possible scenarios that is implied by the independence assumption and the marginal probabilities PA,PR is as follows. For each possible BAF α′ = 〈A′ ,R′a ,R′s 〉, the probability P(α′ ) is:

The size of a prBAF of type IND is O(|A| + |Ra| +Rs| + |PA|+|PR|). For both EX and IND, probabilities are assumed to be rationals, whose sizes contribute to | ⃗P|, |PA| and |PR|.

Example 7 Consider a prBAF F ′ of form EX, where A,Ra and Rs are those of Figure 1, and ⃗α = α1, α2, α3 and ⃗P = P(α1), P(α2), P(α3) are: α1 = 〈A,Ra,Rs〉, α2 = 〈A,Ra \ {(e, b)},Rs〉, α3 = 〈A \ {e},Ra \ {(e, b)},Rs〉, and P (α1) = 0.6, P (α2) = 0.2 and P (α3) = 0.2.

Consider now a prBAF F ′′ of form IND, where A,Ra and Rs are those of Figure 1, and PA and PR are the following: P(a) = P(b) = P(c) = P(d) = P(f) = 1, P(e) = 0.5, P(e, b) = 0.5 and the probabilities of the other supports and attacks are equal to 1. We have three possible scenarios, α1, α2 and α3, that are the same of the case of F ′ , but with probabilities: P (α1) = 0.25, P (α2) = 0.25, P (α3) = 0.5.

In what follows, given a prBAF F = 〈A,Ra,Rs,P〉 of any kind (thus, independently from the way P is encoded), we denote as F.⃗α = α1, . . . , αm the possible BAFs that are assigned non-zero probability by P, and as F. ⃗ P = P(α1), . . . , P(αm) their probabilities. For instance, if F is encoded as a prBAF of form EX, then F.⃗α and F. ⃗ P are exactly the terms ⃗α and ⃗ P in the tuple 〈A,Ra,Rs, ⃗α, ⃗P〉 encoding F. Analogously, if F is of form IND, then F.⃗α is the set of all the possible BAFs having non-zero probability definable over A,Ra and Rs, and F. ⃗ P is the pdf defined in Equation 1. The probabilistic versions of the two sub-classes s-BAF and d-BAF will be called s-prBAF and d-prBAF, respectively. Obviously, they can be of form IND or EX.

When switching to the probabilistic setting, the decision problem EXTsem(S) makes no sense, since a number of different scenarios are possible, and a set of arguments can be an extension in a some scenarios, but not in others. Thus, the most natural "translation" of the problem of examining the "reasonability" of a set of arguments S becomes the functional problem P-EXTsem(S) of evaluating the probability that S is an extension, according to the following definition.

Definition 10 (P-EXTsem(S) and P sem(S)) Given a prBAF F, a set S of arguments, and a semantics sem ∈ SEM, P-EXTsem(S) is the problem of computing the probability P sem F (S) that S is an extension under sem, i.e.

In the following, we will denote as P-EXTsem EX (S)(resp., PEXTsem IND (S)) the problem P-EXTsem(S) restricted to the case that the input prBAF is of form EX (resp., IND).

Example 8 Continuing examples 6 and 7, we now compute the probability that S = {a, e} is d-admissible in both the s-and d- prBAF cases, and for both the forms F ′ and F ′′ .

Case s-prBAF: S is d-admissible in both α1 and α2 (as e is missing in α3), thus P d-ad F ′ (S) = P(α1)+ P(α2) =0.8 and P d-ad F ′′ (S) = P(α1) +P(α2) = 0.5.

Case d-prBAF: S is d-admissible only in α2, as in α1 e dattacks a and in α3 e is missing, thus we have P d-ad F ′ (S) = P (α2) = 0.2 and P d-ad F ′′ (S) = P(α2) = 0.25.

4 Complexity Results

We now provide our main contribution: we characterize the complexity of P-EXTsem(S) over prBAFs for all the combinations of semantics of extensions, of supports (s- and dBAFs), and probabilistic paradigms (EX and IND). Table 1 summarizes our results: the variants d-, s-, and c- of the same semantics are grouped in the same row (for instance, "admissible" groups d-, s-, and c-admissible), as we will show that moving from one variant to the other does not affect the complexity. Before considering the probabilistic setting, we address the deterministic one, by discussing the complexity of EXTsem(S) over BAFs.

Proposition 1 For both s-BAFs and d-BAFs, EXTsem(S) is in P for sem ∈ {d-ad, s-ad, c-ad, st, d-co, s-co, c-co, d-gr, c-gr, c-gr}, is coNP-complete for sem∈ {d-pr, s-pr, c-pr} and is in θp 2 and coNP-hard for sem∈ {d-id, s-id, c-id}.

Proposition 1 follows from the fact that the conditions that must be checked to verify an extension in the presence of supports (for the three variants d-, s-, and c- ) require only polynomial computations on top of those needed in the absence of supports. This implies that the complexity of EXTsem(S) over BAFs is the same as over AAFs (second column of Table 1). We now characterize the complexity of P-EXTsem EX (S).

Theorem 1 For both s-prBAFs and d-prBAFs, PEXTsem EX (S) is in P for sem∈ {d-ad, s-ad, c-ad, st, d-co, s-co, c-co, d-gr, c-gr, c-gr}, and FP||NP -complete for sem∈ {d-pr, s-pr, c-pr, d-id, s-id, c-id}.

(Proof.) Evaluating the probability that S is an extension requires checking whether S is an extension over all the possible BAFs. Under EX, the number of possible scenarios is linear in the input size. Hence, P-EXTsem EX (S) is in P for all the semantics that are polynomial in the deterministic case. For the other semantics, membership in FP||NP follows from the fact that the check can be done in coNP (for the group "preferred") or with parallel invocations to NP oracles (for the group "ideal"). Hardness for FP||NP follows from the hardness for prAAF proved in [Fazzinga et al., 2016]. ✷

We now characterize the complexity of P-EXTsem IND (S).

Theorem 2 For any sem ∈ SEM, and for both s- and dprBAFs, P-EXTsem IND (S) is FP#P -complete.

(Proof.) The membership can be shown applying minor modifications to the TM used in Theorem 3.14 in [Fazzinga et al., 2015], where the membership in FP#P of the correspondent problem for prAAFs (thus, with no supports) was shown. For the hardness, we have to reason by cases. The case that sem is not "stable" or a variant of "admissible" is trivial, since it follows from the fact that the problem is FP#P -hard even when no supports occur [Fazzinga et al., 2015]. Otherwise, if sem ∈ {d-ad, s-ad, c-ad, st}, we consider two cases.

Case 1: the prBAF is an s-prBAF. We first prove the hardness for sem ∈ {d-ad,s-ad,c-ad}. It suffices to show a reduction from a #P-complete problem, since, for functional problems, #P- and FP#P - hardnesses coincide. We show a Cook reduction from #BP2DNF, the #P-complete problem of counting the satisfying assignments of a bipartite positive 2DNF formula. Specifically, given two disjoint sets of propositional variables X = {X1, . . . , Xn}, Y = {Y1, . . . , Ym}, and a BP2DNF formula φ = C1 ∨. . .∨Ck, where every clause Ci is of the form X ∧ Y , with X ∈ X and Y ∈ Y, we consider the s-prBAF F(φ) = 〈A, Ra, Rs, PA, PR〉 where:

• A = {a, b, c, d} ∪ {xi | Xi ∈X} ∪ {yi | Yi ∈Y};
• Ra ={〈c, xi〉 | Xi ∈X }∪{〈c, yi〉 | Yi ∈Y}∪{〈c, b〉, 〈b, d〉};
• Rs = {〈a, xi〉 |Xi ∈ X} ∪ {〈yj, b〉 | Yj ∈ Y} ∪ {〈xi, yj〉 |Xi ∧ Yj is a clause of φ};
• PA assigns probability 1 to every argument;
• PR assigns probability 1 to every defeat and to every support 〈xi, yj〉 such that Xi ∧Yj is in φ, and probability 1 2 to the other supports (i.e., those of form 〈a, xi〉 or 〈yj, b〉).

Let β be the bijection from the truth assignments for X1, . . . ,Xn, Y1, . . . , Ym to the possible BAFs of F(φ) with non-zero probability, such that, for each truth assignment t, β(t) = 〈A′ ,R′a ,R′s 〉 is the possible BAF where: i) 〈a, xi〉 ∈ R′s iff t(Xi) =true and ii) 〈yj, b〉 ∈ R′s iff t(Yj) =true.

Consider the set of arguments {c, d}. It is easy to see that, for each truth assignment t, the set {c, d} is d-/s-/c-admissible in β(t) iff t does not satisfy φ (otherwise, there would be a supported attack from a to d, and a is not attacked by c or d).

Hence, any instance φ of #BP2DNF can be reduced to an instance of P-EXTsem IND (S) by first constructing the prBAF

F(φ), and next returning 2n+m · (1 - P sem F(φ) ({c, d})) as the number of satisfying assignments of φ.

Reasoning analogously, the statement for the stable semantics can be proved by taking the same construction and returning 2n+m · (1 - P st F(φ) ({a, c, d})) (instead of 2n+m · (1P st F(φ) ({c, d}))) as the number of satisfying assignments of φ.

Case 2: the prBAF is an d-prBAF. We show a Cook reduction from the #P-complete problem #P2CNF of counting the satisfying assignments of a positive 2-CNF formula. Specifically, given a positive 2-CNF formula φ = C1 ∧. . .∧Ck over the set of propositional variables X = {X1, . . . ,Xn} where each clause Ch is of the form Xi ∨ Xj with X ∈ X , we consider the d-prBAF F(φ) = 〈A, Ra, Rs, PA, PR〉 where:

• A = {a} ∪ {xi | Xi ∈ X} ∪ {ch | Ch ∈ {C1, . . . , Ck}};
• Ra = {〈a, xi〉 |Xi ∈ X} ∪ {〈ch, a〉 |Ch ∈ {C1, . . . , Ck}};
• Rs = {〈ch, xi〉 | Xi occurs in the clause Ch};
• PA assigns probability 1.0 to the arguments a, c1, . . . , ck and probability 12 to the arguments x1, . . . , xn;
• PR assigns probability 1.0 to every attack and support.

Let β be the bijection from the truth assignments for X1, . . . ,Xn to the possible BAFs of F(φ) with non-zero probability such that, for each truth assignment t, we have that β(t) = 〈A′ ,R′a ,R′s 〉 is the possible BAF such that xi ∈ A′ iff t(Xi) =true. Consider the set of arguments {a}. It is easy to see that, for each truth assignment t, {a} is d-/s-/c-admissible or stable in β(t) iff t satisfies φ. This derives from the fact that β(t) contains an attack from a to xi iff t(Xi) =true. In turn, the existence of 〈a, xi〉 raises a supermediated attack from a to every cj such that Xi occurs in Cj, thus defending a from cj. Hence, any instance φ of #P2CNF can be reduced to an instance of P-EXTsem IND (S) by first constructing the prBAF F(φ), and next returning 2n+m · P sem F(φ) ({a}) as the number of satisfying assignments of φ. ✷

4.1 Tractable Cases for P-EXTsem IND (S)

The results above say that the combination of bipolarity and probabilities makes reasoning over extensions harder only for the form IND under the s-/d-/c-admissible and stable semantics, for which P-EXTsem(S) is polynomial in the absence of supports (see Table 1). Thus, finding conditions restoring the polynomiality is worth investigating, as this gives an insight on the new source of complexity introduced by combining probabilities and supports. With this aim, we focus on the form IND and show a restricted form of prBAFs (namely, C-bounded prBAFs) for which P-EXTsem(S) is polynomial. At the end of this section, we will show that the relevance of this restriction goes beyond the definition of a tractable class: our proof of tractability is based on introducing a general paradigm for computing extensions' probability that can enhance the efficiency even when the restriction does not hold.

Formally, given a prBAF F = 〈A, Ra, Rs, PA, PR〉, consider the sets: i) F.Ae = {a| ∃〈a, b〉 ∈ Rs ∨ ∃〈b, a〉 ∈ Rs} (called set of supp-arguments, as they are those involved in supports), and ii) F.Re = {〈a, b〉 ∈ (Ra ∪ Rs) | (a ∈ Ae∨b ∈ Ae} (called set of supp- attacks and supports, as they are attacks/supports incident to supp-arguments). Given this, for any constant C, F is said to be C-bounded if |F.Re| ≤ C (meaning that the number of supports and of attacks to/from arguments involved in supports is bounded by C).

Our strategy is based on the notions of contraction and completion. A contraction for a prBAF F = 〈A,Ra,Rs, PA, PR〉 is a prBAF F ∗ = 〈A∗ , R∗a , R∗s , P ∗A, P ∗R〉 where:

• A∗ ⊆ A and A \ A∗ ⊆ F.Ae;
• R∗a ⊆ Ra ∩ (A∗ × A∗ ) and Ra \ R∗a ⊆ F.Re;
• R∗s ⊆ Rs ∩ (A∗ ×A∗ );
• P ∗A(a) = 1 if a ∈ F.Ae and P ∗A(a) = PA(a) otherwise;
• P ∗R(〈a, b〉) = 1 if a ∈ F.Ae ∨ b ∈ F.Ae, and P ∗R(〈a, b〉) = PR(〈a, b〉) otherwise.

Basically, F ∗ 's supports are a subset of F's, and arguments (resp., attacks) are a subset of F's containing at least the non supp-arguments (resp., the non supp-attacks). Then, the probabilities are copied from those specified in F, except for those over supp- arguments and attacks, that are overwritten with 1. E(F) will denote the set of possible contractions of F. For F ∗ ∈ E(F), the probability of F ∗ given F is: P(F ∗ |F) = ∏a∈Ae PF ∗ (a) × ∏δ∈Re∩(A∗×A∗ ) PF ∗ (δ), where:

• if a∈A∗ , PF ∗(a)=PA(a); else, PF ∗(a)=1-PA(a);
• if δ ∈ R∗a∪R∗s , PF ∗(δ)=PR(δ); else,PF ∗(δ)=1-PR(δ).

As regards completions, their definition uses the function cert(F), returning the BAF consisting of all and only the certain arguments/attacks/supports of F (i.e., those having probability 1). Thus, the completion of F is the prBAF compl(F) = 〈A′ , R′a , R′s , P ′A, P ′R〉 where:

• A′ = A and R′s = Rs;
• R′a =Ra∪R′ , where R′ consists of the s- or the d- attacks of cert(F), depending on whether F is an s- or a d- prBAF;
• ∀a ∈ A, P ′A(a) = PA(a);
• ∀δ ∈ R′a , if δ ∈ R′ then P ′R(δ)=1, else P ′R(δ) = PR(δ).

Next lemma allows for decomposing the evaluation of P sem F (S) into evaluating P sem F ∗ (S) over each contraction F ∗ .

Lemma 1 Let F be a prBAF and S a set of its arguments. For sem ∈ {d-ad, s-ad, c-ad, st}, it holds that P sem F (S) = ∑F ∗∈E(F) P (F ∗ |F) × P sem F ∗ (S).

The following lemma provides a method for computing P sem F ∗ (S) for each F ∗ ∈ E(F), as it states that P sem F ∗ (S) can be computed by taking the prAAF F obtained by removing the supports from the completion of F ∗ , and then using over F any state-of-the-art algorithm for computing the extensions' probabilities over "traditional" prAAFs (that is polynomial for the semantics ad, st).

Lemma 2 Let F be a prBAF, F ∗ a contraction for F, F the prAAF obtained from compl(F ∗ ) by removing the supports, and S a set of arguments of F ∗ . Then:

• For sem ∈ {d-ad, st} P sem F ∗ (S) = P sem′ F (S), where sem′ ∈ {ad, st} respectively;
• P s-ad F ∗ (S) = 0 if S is not safe over cert(compl(F ∗ )); otherwise, P s-ad F ∗ (S) = P ad F (S);

Observe that lemmas 1 and 2 do not require that F is Cbounded: they state general properties that, on C-bounded prBAFs, can be exploited to compute P-EXTsem IND (S) efficiently (for what shown in the proof of Theorem 3).

Theorem 3 For sem ∈ {d-ad, s-ad, c-ad, st}, P-EXTsem IND (S) is in FP for both C-bounded s- and d- prBAFs.

Proof. Lemma 1 ensures that P sem F (S) can be computed as ∑F ∗∈E(F) P (F ∗ |F) × P sem F ∗ (S), where for each F ∗ ∈ E(F). Lemma 2 and the fact that computing P sem′ F (S) over a prAAF is feasible in polynomial time for sem′ ∈ {ad, st} [Fazzinga et al., 2015] in turn imply that P sem F ∗ (S) can be computed in polynomial time w.r.t. the size of F. It is easy to see that, since F is C-bounded, |E(F)| ≤ 2C , as the number of contractions is bounded by the number of subsets of F.Re. Thus, the sum in Lemma 1 consists of a constant number of polynomial time computable addends. ✷

Remark. The strategy used to prove the tractability of the Cbounded class can be applied also to non C-bounded prBAFs, where, even if it is not guaranteed to work in polynomial time, it is likely to perform better than an 'exhaustive' evaluation, as it requires only contractions to be enumerated.

5 Conclusions

We have characterized the computational complexity of evaluating extensions' probabilities over probabilistic BAFs. The most popular semantics of extensions and of supports have been considered, along with different probabilistic paradigms for encoding uncertainty. Interestingly, we have shown that, considering bipolarity does not do not increase the computational complexity, except for the case of admissible and stable semantics under the assumption of independence between the terms of the dispute. For this case, we have shown that the complexity explodes from FP to FP#P -complete, and islands of tractability have been detected.