Answer: Exact computation is NP-hard for every fixed \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr},\mathrm{st}\}\), even with \(\tau=1\) and no attacks or supports. A polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor σ ∈{gr, co, st, pr}, PrA[σ] is FP#P-hard, even for acyclic CPBAFs and for any chosen PDF. The high computational complexity of PrA[σ] and PrEA[σ], even for the very simple setting of acyclic CPBAF, suggests that one would need to focus on finding efficient algorithms that solve the problem approximately. Next, we present a complete picture of the approximability landscape of our problems, under different semantics and approxima- tion schemes, where the definition of the latter is as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite list of types \(t\), binary rational masses \(\mu_t\) summing to \(1\), a shared argument set \(A\), a goal \(g\in A\), a semantics \(\sigma\), and for each type a CPBAF \(\Delta_t\) with world probabilities \(I_t\) and a fixed extension-selection distribution \(\rho_t(E\mid w)\), compute \(M^\sigma(g)=\sum_t\mu_t\sum_{w\in pw(\Delta_t)}I_t(w)\sum_{\substack{E\in\sigma(w)\g\in E}}\rho_t(E\mid w)\).
A society is given by its support: the list of the \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not possible types. Let \(A\) be a shared argument set, \(m=|A|\geq1\), \(g\in A\), and \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr},\mathrm{st}\}\).
Each type has a conditional probabilistic bipolar argumentation framework \(\Delta_t=(A,R_t,S_t,P_t)\), with disjoint attack and necessary-support relations \(R_t,S_t\subseteq A\times A\). Each argument or edge \(x\) has one propositional condition \(C_{t,x}\) and a binary rational probability \(p_{t,x}\in(0,1]\); edge conditions include both endpoints. The dependency graph, with an edge from each atom in \(C_{t,x}\) to \(x\), is acyclic.
Generate a world in dependency order: if \(C_{t,x}\) is false, omit \(x\); otherwise include it with probability \(p_{t,x}\). These conditional draws define \(pw(\Delta_t)\) and its world distribution \(I_t\); neither worlds nor their probabilities are explicitly enumerated.
For a world \(w=(B,R,S)\) and \(E\subseteq B\), let \(D_w(E)\) be the least set containing all arguments attacked by \(E\) and all arguments on support cycles, and closed under outgoing supports. Let \(C_w(E)\) be the least fixed point of \(X\mapsto\{a\in B:(\forall b\,((b,a)\in R\Rightarrow b\in D_w(E)))\land(\forall c\,((c,a)\in S\Rightarrow c\in X))\}\).
Complete extensions satisfy \(E\cap D_w(E)=\varnothing\) and \(E=C_w(E)\); preferred extensions are inclusion-maximal complete extensions; stable extensions are preferred extensions satisfying \(E\cup D_w(E)=B\); the grounded extension is the inclusion-least complete extension. Write \(\sigma(w)\) for the corresponding extension set.
Each type supplies a Boolean circuit taking the incidence vectors of \(w,E\) and outputting a binary numerator and positive denominator for \(\rho_t(E\mid w)\). On every positive-probability world, these values are promised nonnegative, zero outside \(\sigma(w)\), and to sum to one over \(\sigma(w)\); thus such worlds must have an extension, including when \(\sigma=\mathrm{st}\). Let \(L\) be the total input bit length, including formulas and circuits.
Define \(M^\sigma(g)=\sum_{t=1}^{\tau}\mu_t\sum_{w\in pw(\Delta_t)}I_t(w)\sum_{E\in\sigma(w):\,g\in E}\rho_t(E\mid w)\).
Is exact computation of \(M^\sigma(g)\) polynomial-time in \(m,\tau,L\), or is it NP-hard, for each fixed \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr},\mathrm{st}\}\)?
Single-framework probabilistic acceptance is \(\mathrm{FP}^{\#\mathrm P}\)-hard for all four semantics, even for acyclic frameworks and any fixed extension-selection distribution. [Verified hardness result](https://ojs.aaai.org/index.php/AAAI/article/download/38961/42923).
No separate classification for this support-encoded mass formulation was located.
Exact computation of \(M^\sigma(g)\) is NP-hard for every fixed \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr},\mathrm{st}\}\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
This holds even with one listed type, no attacks or supports, and a unique extension in every world. The following direct reduction verifies all the promises in the question; it does not require transferring the representation assumptions of the cited [single-framework hardness result](https://ojs.aaai.org/index.php/AAAI/article/download/38961/42923).
Let \(\varphi(z_1,\ldots,z_n)\) be a CNF formula, with \(n\geq1\). Satisfiability remains NP-complete under this restriction.
Construct a society with \(\tau=1\) and \(\mu_1=1\). Its argument set and relations are
\(A=\{a_1,\ldots,a_n,g\},\qquad R_1=S_1=\varnothing.\)
Assign the following conditions and probabilities:
Here \(\top\) denotes the constant true condition. All probabilities satisfy the required bounds. The only possible dependency edges are from arguments \(a_i\) to \(g\), so the dependency graph is acyclic. The conditions on edges are vacuous because there are no edges.
For an assignment \(u=(u_1,\ldots,u_n)\in\{0,1\}^n\), define
\(B_u=\{a_i:u_i=1\}\cup G_u,\)
where \(G_u=\{g\}\) if \(\varphi(u)=1\), and \(G_u=\varnothing\) otherwise. The corresponding world is \(w_u=(B_u,\varnothing,\varnothing)\).
The arguments \(a_i\) are included by independent unconditional draws, each with probability \(\tfrac12\). After those draws, the presence of \(g\) is deterministic. Thus
\(I_1(w_u)=2^{-n}.\)
Different assignments give different worlds because their incidence vectors on \(a_1,\ldots,a_n\) differ. These are exactly all positive-probability worlds.
Consider any world \(w=(B,\varnothing,\varnothing)\), and any \(E\subseteq B\).
There are no attacked arguments, support cycles, or outgoing supports. Hence
\(D_w(E)=\varnothing.\)
In the operator defining \(C_w(E)\), both universal conditions are vacuously true for every \(a\in B\). Consequently, that operator maps every \(X\subseteq B\) to \(B\), and its least fixed point is
\(C_w(E)=B.\)
The complete-extension requirements therefore hold precisely when \(E=B\): the condition \(E=C_w(E)\) forces this equality, and \(B\cap D_w(B)=\varnothing\) verifies conflict-freeness.
It follows explicitly that:
Thus, for every chosen semantics,
\(\sigma(w)=\{B\}.\)
This also covers the case \(B=\varnothing\).
Supply a circuit whose denominator is always \(1\), and whose numerator is \(1\) exactly when the incidence vector of \(E\) equals the argument-incidence vector of \(w\); otherwise its numerator is \(0\).
Equality of these \(m=n+1\) bits is computable by a circuit of size \(O(m)\). On every positive-probability world \(w=(B,\varnothing,\varnothing)\), it therefore defines
\(\rho_1(E\mid w)=1\) if \(E=B\), and \(\rho_1(E\mid w)=0\) otherwise.
By Section 2, this circuit is nonnegative, vanishes outside \(\sigma(w)\), and sums to one over \(\sigma(w)\). In particular, the stable-extension existence promise is satisfied.
The entire constructed instance has bit length polynomial in the encoding length of \(\varphi\).
Write \(\#\mathrm{SAT}(\varphi)\) for the number of assignments satisfying \(\varphi\). Since the unique extension of \(w_u\) is \(B_u\), and \(g\in B_u\) precisely when \(\varphi(u)=1\), the definition of societal acceptance gives
\(M^\sigma(g)=\sum_{u\in\{0,1\}^n}2^{-n}\mathbf{1}[\varphi(u)=1]=\dfrac{\#\mathrm{SAT}(\varphi)}{2^n}.\)
In particular,
\(\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad M^\sigma(g)>0.\)
Therefore, an exact-computation algorithm yields a satisfiability decision procedure by constructing this instance, making one call, and testing whether the returned rational is positive. This proves NP-hardness under a polynomial-time, one-call reduction for each fixed semantics. More strongly, multiplying the result by \(2^n\) recovers \(\#\mathrm{SAT}(\varphi)\), establishing \(\#\mathrm P\)-hardness under polynomial-time oracle reductions.
The reduced fraction has numerator and denominator of \(O(n)\) bits, so this hardness already occurs on instances with polynomial-size exact outputs.
⟨structured verdict parsed — rendered above⟩
The reduction settles the requested classification: exact computation is NP-hard for each of the four fixed semantics. All construction and promise checks are valid. There is one minor omission in the optional stronger claim of $\#\mathrm P$-hardness.
The prover uses CNF satisfiability with $n\geq1$, which remains NP-complete. The constructed society has $\tau=1$, mass $\mu_1=1$, and $m=n+1$. Its conditions consist of $n$ constant formulas and one copy of $\varphi$ with renamed variables. The probabilities and mass have constant-size binary rational encodings. Thus the construction has polynomial input length.
Every probability lies in $(0,1]$. The only dependency edges run from some $a_i$ to $g$, so the dependency graph is acyclic. Empty attack and support relations are disjoint, and the endpoint-condition requirement is vacuous.
The unconditional draws for the $a_i$ give each assignment probability $2^{-n}$. Conditional on those draws, $g$ is present exactly when $\varphi$ is true, because its inclusion probability is $1$. Different assignments produce different argument-incidence vectors. Consequently, the enumerated $w_u$ are exactly the positive-probability worlds, each with the stated probability.
For every $E\subseteq B$, the absence of attacks and supports gives $D_w(E)=\varnothing$. Both universal conditions in the fixed-point operator are vacuously true, so the operator is the constant map with value $B$. Its unique fixed point, and therefore its least fixed point, is $B$.
Hence completeness holds exactly for $E=B$. This extension is the least complete extension and the unique inclusion-maximal complete extension. It also satisfies the stable coverage condition. Therefore $\sigma(w)=\{B\}$ for every specified semantics. The reasoning remains valid when $B=\varnothing$.
Comparing the argument-incidence vectors of $E$ and $w$ requires $O(m)$ gates. The proposed numerator is either $0$ or $1$, and the denominator is the positive constant $1$.
On every positive-probability world, the circuit assigns weight $1$ to the unique extension $B$ and $0$ to every other candidate. Nonnegativity, vanishing outside the extension set, normalization, and stable-extension existence all follow. Ignoring the edge-incidence inputs causes no problem because all generated worlds have empty relations.
The unique extension contains $g$ exactly for satisfying assignments. Substitution into the definition therefore gives
$$
M^\sigma(g)=2^{-n}\#\mathrm{SAT}(\varphi).
$$
No selection weights or type masses are omitted: both relevant weights equal $1$. In particular, positivity is equivalent to satisfiability.
The construction followed by one exact-computation call and a rational positivity test decides CNF satisfiability. The prover correctly identifies this as a polynomial-time one-call reduction. It establishes the requested NP-hardness for each fixed semantics and the consequence that a polynomial-time exact algorithm would imply $\mathrm P=\mathrm{NP}$.
The output-size observation is also correct: before reduction to lowest terms, the numerator is at most $2^n$ and the denominator is $2^n$. Reduction cannot increase their bit lengths.
Multiplication by $2^n$ correctly recovers $\#\mathrm{SAT}(\varphi)$ in polynomial time. Calling this $\#\mathrm P$-hardness additionally invokes the standard completeness theorem for counting satisfying assignments of CNF formulas, without explicitly stating it.
Minimum clarification: state that counting satisfying assignments of CNF formulas is $\#\mathrm P$-complete under polynomial-time oracle reductions. This is an expositional omission; it does not affect the requested NP-hardness result.
There are no blocking issues or substantive mathematical gaps.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.