Answer: For \(\mathrm{gr}\), the mass-threshold problem is in \(P\). For \(\mathrm{co}\) and \(\mathrm{pr}\), it is NP-hard, already for \(\tau=1\), mass \(1\), and threshold \(1\).
Theorem 4 — class: hardness
Given a well-formed EAAF \(\Delta=\langle A,\Omega,\Psi,\Phi\rangle\), \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr}\}\), rational masses \(\mu_a\ge 0\) with \(\sum_{a\in A}\mu_a=1\) over stakeholder types \(t=(\Delta,a)\), and a rational threshold \(\theta\), decide whether \(\sum_{a\in A}\mu_a e_\sigma(\Delta,a)\ge\theta\), where \(e_\sigma(\Delta,a)=1\) exactly when the paper's \(\mathrm{EA}_\sigma\) predicate accepts a.
An epistemic abstract argumentation framework is \(\Delta=\langle A,\Omega,\Psi,\Phi\rangle\), with finite nonempty \(A\) and pairwise disjoint standard, weak epistemic, and strong epistemic attack relations \(\Omega,\Psi,\Phi\subseteq A\times A\). Put \(m=|A|\). No directed cycle may contain an epistemic attack; each epistemic argument (a target of \(\Psi\cup\Phi\)) has exactly one incoming attack, which is epistemic.
For a nonempty candidate world view \(W\subseteq 2^A\) and any \(S\subseteq A\), define \(D_W(S)=\{b\in A:(\exists a\in S\;(a,b)\in\Omega)\lor(\exists T\in W\;\exists a\in T\;(a,b)\in\Phi)\lor(\forall T\in W\;\exists a\in T\;(a,b)\in\Psi)\}\).
Define \(C_W(S)=\{b\in A:\forall a\in A,\;[(a,b)\in\Omega\Rightarrow a\in D_W(S)]\land[(a,b)\in\Phi\Rightarrow\forall T\in W\;a\in D_W(T)]\land[(a,b)\in\Psi\Rightarrow\exists T\in W\;a\in D_W(T)]\}\).
A \(W\)-complete set satisfies \(S\cap D_W(S)=\varnothing\) and \(S=C_W(S)\). A \(W\)-preferred (respectively \(W\)-grounded) set is inclusion-maximal (respectively inclusion-minimal) among all \(W\)-complete subsets of \(A\).
A subframework \(\Delta'\) is obtained by deleting any subset of epistemic arguments together with all arguments reachable from them, and restricting all attack relations. Write \(W|_{\Delta'}=\{S\cap A':S\in W\}\).
For \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr}\}\), the unique \(\sigma\)-world view \(W_\sigma\) satisfies, for every such subframework, that every member of \(W|_{\Delta'}\) is \(W|_{\Delta'}\)-\(\sigma\), and no strictly larger candidate world view \(Q\) on \(\Delta'\) has every member \(Q\)-\(\sigma\). All predicates on subframeworks use their restricted relations.
The society is given by its support: a list of \(\tau\) distinct types \((\Delta,a)\), where \(a\) is epistemic, with positive binary rational masses \(\mu_a\) summing to \(1\); unlisted arguments have mass zero. All types share the input framework. Here \(\tau\) is support size, not the number of possible types. Set \(e_\sigma(\Delta,a)=1\) iff \(a\in S\) for every \(S\in W_\sigma\), and zero otherwise; for epistemic arguments, existential and universal acceptance coincide. Masses do not alter the world view.
Given also \(\theta\in\mathbb Q\), the mass-threshold problem decides whether \(\sum_{a:\mu_a>0}\mu_a e_\sigma(\Delta,a)\ge\theta\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is the mass-threshold problem in \(P\), or is it NP-hard, for each fixed \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr}\}\)?
Discrete epistemic acceptance is in \(P\) for \(\mathrm{gr}\), \(\Theta_2^p\)-hard and in \(\Delta_2^p\) for \(\mathrm{co}\), and \(\Pi_2^p\)-hard and in \(\Delta_3^p\) for \(\mathrm{pr}\). [Acceptance bounds](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p409.pdf)
A later semantics for general frameworks agrees with this semantics when no cycle contains an epistemic attack. [Semantic extension](https://www.ijcai.org/proceedings/2024/0355.pdf)
No result for this exact rational-mass threshold problem was located in the literature search.
The mass-threshold problem is in \(P\) for grounded semantics and NP-hard for both complete and preferred semantics. More precisely:
| Fixed semantics | Mass-threshold complexity |
|---|---|
| \(\mathrm{gr}\) | In \(P\) |
| \(\mathrm{co}\) | \(\Theta_2^p\)-hard and in \(\Delta_2^p\) |
| \(\mathrm{pr}\) | \(\Pi_2^p\)-hard and in \(\Delta_3^p\) |
Hardness already holds with support size \(\tau=1\), mass \(1\), and threshold \(1\).
The proof below gives a direct grounded algorithm and transfers the supplied discrete acceptance bounds for the other semantics.
List the supported arguments as \(a_1,\ldots,a_\tau\), and write \(\mu_{a_i}=p_i/q_i\), with positive integers \(p_i,q_i\). Write \(\theta=u/v\), where \(v>0\).
Once the acceptance bits \(e_i=e_\sigma(\Delta,a_i)\) are known, put
\(B=\prod_{i=1}^{\tau}q_i,\qquad N=\sum_{i=1}^{\tau}e_i p_i(B/q_i).\)
The threshold condition is exactly
\(vN\ge uB.\)
The bit length of \(B\) is \(O(L)\), since the denominator encodings form part of the input. Moreover, \(0\le N\le B\), because the masses sum to \(1\). All integers used above therefore have \(O(L)\) bits, including the final products.
Using schoolbook multiplication and division, exact aggregation and comparison take \(O(\tau L^2)\) bit operations. Thus binary rational masses introduce only polynomial overhead.
For completeness, thresholds \(\theta\le0\) always give a yes-instance, and thresholds \(\theta>1\) always give a no-instance. The substantive range is \(0<\theta\le1\).
Let \(R=\Omega\cup\Psi\cup\Phi\), temporarily treating every attack as an ordinary attack. Define
\(R^+(X)=\{b\in A:\exists a\in X\;(a,b)\in R\},\)
\(F(X)=\{b\in A:\forall a\;((a,b)\in R\Rightarrow a\in R^+(X))\}.\)
Starting with \(G_0=\varnothing\), iterate \(G_{i+1}=F(G_i)\).
Both \(R^+\) and \(F\) are monotone. Consequently, the sequence \(G_i\) is increasing and stabilizes after at most \(m\) strict increases. Denote its fixed point by \(G\).
We verify that \(G\) is conflict-free. For \(x\in G\), let \(r(x)\) be its first iteration of appearance. Suppose an attack \((x,y)\in R\) has both endpoints in \(G\), and choose such an attack minimizing \(r(x)+r(y)\). Since \(y\in F(G_{r(y)-1})\), its attacker \(x\) is attacked by some \(z\in G_{r(y)-1}\). Then \((z,x)\) is another attack internal to \(G\), but
\(r(z)+r(x)<r(y)+r(x),\)
contradicting minimality. Hence \(G\cap R^+(G)=\varnothing\).
For the singleton candidate \(W=\{G\}\), the definitions give
\(D_{\{G\}}(G)=R^+(G),\qquad C_{\{G\}}(G)=F(G)=G.\)
Thus \(G\) is \(\{G\}\)-complete.
We prove a stronger statement.
Lemma. Suppose a candidate \(Q\) contains \(G\), and every member of \(Q\) is \(Q\)-complete. Then every \(Q\)-complete set contains \(G\).
Proof. Let \(\mathcal H\) be the family of all \(Q\)-complete sets. In particular, \(Q\subseteq\mathcal H\). We prove simultaneously, by induction, that \(G_i\subseteq H\) for every \(H\in\mathcal H\).
The base case is immediate. Assume the assertion holds for \(G_i\), and take \(b\in G_{i+1}\).
If \(b\) is epistemic, all its incoming attacks are epistemic. Consequently, membership of \(b\) in \(C_Q(H)\) is independent of \(H\): the relevant clauses quantify over \(Q\), not over \(H\). Since \(b\in G=C_Q(G)\), it follows that \(b\in C_Q(H)=H\).
If \(b\) is not epistemic, every incoming attack \((a,b)\) is standard. Because \(b\in F(G_i)\), each such \(a\) is attacked through \(R\) by some \(c\in G_i\). The induction hypothesis puts \(c\) in every \(H\in\mathcal H\), hence also in every member of \(Q\). Therefore:
Thus every standard attacker of \(b\) belongs to \(D_Q(H)\), giving \(b\in C_Q(H)=H\).
This completes the induction and proves the lemma. \(\square\)
Apply the lemma first to \(Q=\{G\}\). Every \(\{G\}\)-complete set contains \(G\), so \(G\) is its unique inclusion-minimal complete set.
Now suppose \(Q\supsetneq\{G\}\) and every member of \(Q\) is \(Q\)-grounded. The lemma applies because grounded sets are complete. Every \(Q\)-complete set contains \(G\), and \(G\) itself is \(Q\)-complete. Hence an inclusion-minimal \(Q\)-complete set must equal \(G\), forcing \(Q=\{G\}\), a contradiction. This proves the required candidate maximality.
Let \(A'\) be the surviving argument set of an allowed subframework. It is closed under predecessors: if \(y\in A'\) and \((x,y)\in R\), then \(x\in A'\). Otherwise, deletion of \(x\) would also delete its reachable argument \(y\).
Write \(F'\) for the ordinary defense operator on the restricted graph. Predecessor closure implies, for every \(X\subseteq A\),
\(F'(X\cap A')=F(X)\cap A'.\)
Indeed, both attackers of a surviving argument and attackers of those attackers survive. Iteration therefore gives restricted grounded fixed point \(G'=G\cap A'\).
The preceding singleton argument applies within this subframework as well. Thus \(\{G\}\) satisfies both world-view conditions on every allowed subframework. By the stipulated uniqueness,
\(W_{\mathrm{gr}}=\{G\}.\)
Consequently, \(e_{\mathrm{gr}}(\Delta,a)=1\) exactly when \(a\in G\).
Each iteration computes \(R^+(G_i)\) and then scans the attacks to compute \(F(G_i)\), using \(O(m^2)\) graph operations. There are \(O(m)\) iterations.
Including support lookup and exact rational comparison, a conservative bound, charging \(O(\log(m+1))\) per graph operation, is
\(O\!\left(m^3\log(m+1)+\tau L^2\right).\)
This proves membership in \(P\).
The cited acceptance theorem concerns epistemic target arguments under precisely the well-formed, plain-form restrictions used here: no cycle contains an epistemic attack, and each epistemic target has one incoming attack. Its acceptance predicate agrees with \(e_\sigma\), because existential and universal acceptance coincide for epistemic arguments. Thus the supplied hardness bounds apply to the required input domain. See [Alfano et al., Definition 2 and Theorem 4](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p409.pdf).
For either fixed semantics, map an epistemic acceptance instance \((\Delta,a)\) to the mass-threshold instance with:
This construction preserves every framework restriction, uses positive masses summing to \(1\), and adds only constant-size numeric data. Its threshold condition is
\(\sum_{b:\mu_b>0}\mu_b e_\sigma(\Delta,b)\ge1 \quad\Longleftrightarrow\quad e_\sigma(\Delta,a)=1.\)
It is therefore a polynomial-time many-one reduction.
For complete semantics, it transfers \(\Theta_2^p\)-hardness. Since \(NP\subseteq\Theta_2^p\), this implies NP-hardness.
For preferred semantics, it transfers \(\Pi_2^p\)-hardness. Since \(NP\subseteq\Pi_2^p\), this also implies NP-hardness.
For general support, run the supplied discrete acceptance algorithm on each of the \(\tau\) supported arguments, then perform the exact aggregation proved above.
For complete semantics, these computations use an \(NP\) oracle; for preferred semantics, they use a \(\Sigma_2^p\) oracle. Polynomially many such computations preserve membership in \(\Delta_2^p\) and \(\Delta_3^p\), respectively.
More explicitly, if \(p_\sigma(m,L)\) bounds the polynomial oracle running time of one discrete acceptance computation, the resulting oracle running time is
\(O\!\left(\tau p_\sigma(m,L)+\tau L^2\right).\)
These upper bounds do not assert ordinary polynomial-time solvability for the two hard cases.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The grounded algorithm, singleton hardness reductions, and oracle upper bounds are valid. No major or minor mathematical issues were found.
The construction with \(\tau=1\), mass \(1\), and threshold \(1\) preserves all promises and has precisely the same yes-instances as epistemic acceptance. It is a polynomial many-one reduction. Both class inclusions used to infer NP-hardness are correct.
No repair or additional clarification is needed. The result depends on semantics, with no demonstrated dependence on numeric representation; accordingly, the JSON records the established hardness rather than a representation-based split.
⟨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.