Answer: \(\mathrm{NP}\)-complete
Theorem 4(a) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatea. CAGR∗is NP–complete. b. SAGR∗is coNP–complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of argumentation-framework types \(G_t=(A_t,R_t)\), each containing a common query argument \(p\), binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(q\in(0,1]\), decide whether \(\sum_{t:\exists S\in E_{\mathrm{GR}^*}(G_t),\ p\in S}\mu_t\ge q\).
A society is given by its support: a list of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type is a finite argumentation framework \(G_t=(A_t,R_t)\), explicitly encoded, with \(R_t\subseteq A_t\times A_t\) and a common query argument \(p\in A_t\); self-attacks are allowed.
A full resolution \(\gamma\) deletes exactly one directed attack from every mutually attacking pair of distinct arguments, and deletes no other attacks. Write \(G_t^\gamma=(A_t,R_t\setminus\gamma)\); if there are no such pairs, the empty resolution is permitted.
Let \(\mathrm{GE}(H)\) denote the standard grounded extension of an argumentation framework \(H\). Define \(E_{\mathrm{GR}^*}(G_t)\) as the inclusion-minimal members of \(\{\mathrm{GE}(G_t^\gamma):\gamma\text{ is a full resolution}\}\).
The input also contains a binary-rational threshold \(q\in(0,1]\). Let \(m=\max_t|A_t|\) and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is deciding whether \(\sum_{t:\exists S\in E_{\mathrm{GR}^*}(G_t),\ p\in S}\mu_t\ge q\) solvable in polynomial time, or is it NP-hard?
For a single finite argumentation framework, credulous acceptance under resolution-based grounded semantics is NP-complete, and checking whether a proposed set is an extension is polynomial-time solvable. No separate continuous-side result is assumed here.
The decision problem is \(\mathrm{NP}\)-complete under the two single-framework results supplied in the question. Hardness already holds for support size \(\tau=1\), and also for \(\tau=2\) with distinct types, equal masses, and threshold \(q=1\).
Consequently, a polynomial-time algorithm exists if and only if \(\mathrm{P}=\mathrm{NP}\).
Call a type \(t\) accepting if there exists \(S\in E_{\mathrm{GR}^*}(G_t)\) with \(p\in S\). Let \(B\) be the set of accepting types. The required condition is \(\sum_{t\in B}\mu_t\ge q\).
A certificate consists of:
The verifier checks that, for each \(t\in J\), \(p\in S_t\) and \(S_t\in E_{\mathrm{GR}^*}(G_t)\). Extension membership is polynomial-time decidable by the supplied premise. Finally, it checks \(\sum_{t\in J}\mu_t\ge q\) using exact rational arithmetic.
Soundness. Every verified type belongs to \(B\), so \(J\subseteq B\). Positivity of the masses gives \(\sum_{t\in B}\mu_t\ge\sum_{t\in J}\mu_t\ge q\).
Completeness. If the input satisfies the required condition, choose \(J=B\) and, for every \(t\in B\), choose an extension witnessing acceptance. This certificate passes all checks. No certificate of rejection is needed for the remaining types.
Encoding each \(S_t\) by its characteristic vector gives a certificate of length \(O(\tau m+\tau)\), polynomial in \(L\) because the support and its frameworks are explicitly listed.
Write the encoded rationals as \(\mu_t=a_t/b_t\) and \(q=c/d\), with positive denominators. Set \(D=d\prod_{t=1}^{\tau}b_t\). The threshold comparison is equivalent to the integer comparison
\(\sum_{t\in J}a_t(D/b_t)\ge c(D/d)\).
The bit length of \(D\) is \(O(L)\): its logarithm is at most the sum of the bit lengths of the encoded denominators. Since the masses sum to \(1\) and \(q\le1\), the integer weights, threshold, and partial sums also have \(O(L)\) bits. Schoolbook multiplication and division therefore suffice for an arithmetic running time of \(O((\tau+1)L^2)\).
After indexing argument names and constructing adjacency matrices, let \(O(m^c)\) bound the supplied extension-membership algorithm, for some fixed constant \(c\), enlarged if necessary to cover matrix processing. Input preprocessing can be performed in \(O(L^2+\tau m^2)\) time. Thus the nondeterministic verification time is
\(O\bigl(\tau m^c+(\tau+1)L^2\bigr)\).
This proves membership in \(\mathrm{NP}\), including the binary-rational arithmetic.
Given an instance \((G,p)\) of single-framework credulous acceptance under resolution-based grounded semantics, construct a society consisting of the single type \(G\), with mass \(1\), and set \(q=1\).
Its accepting mass is \(1\) precisely when \(p\) belongs to some member of \(E_{\mathrm{GR}^*}(G)\); otherwise it is \(0\). Hence the constructed society satisfies the threshold precisely when the original instance is accepting.
The construction is polynomial-time, preserves the explicit framework encoding, and satisfies every society-input requirement. The supplied single-framework \(\mathrm{NP}\)-completeness result therefore proves \(\mathrm{NP}\)-hardness.
The preceding reduction uses singleton support. The hardness persists for two distinct types through the following padding lemma.
Lemma. Let \(G^+\) be obtained from \(G\) by adding a fresh argument \(z\), its self-attack \((z,z)\), and no attacks between \(z\) and the original arguments. Then, viewing sets of original arguments as subsets of the enlarged argument set,
\(E_{\mathrm{GR}^*}(G^+)=E_{\mathrm{GR}^*}(G)\).
Proof. A self-attack is not a mutually attacking pair of distinct arguments. Thus adding \(z\) creates no additional resolution choices, and full resolutions of \(G\) and \(G^+\) correspond exactly.
Fix a corresponding resolution. For a framework \(H\), write its characteristic function as
\(F_H(X)=\{a:\text{ for every }b\text{ attacking }a,\text{ some }c\in X\text{ attacks }b\}\).
The grounded extension of a finite framework is obtained by iterating \(F_H\) from the empty set until stabilization.
For every \(X\) containing only original arguments, defense of any original argument is unchanged by the padding. Moreover, \(z\notin F_{(G^+)^\gamma}(X)\): its attacker is \(z\), and no original argument attacks \(z\). Consequently,
\(F_{(G^+)^\gamma}(X)=F_{G^\gamma}(X)\).
Starting from the empty set, induction shows that the grounded iterations coincide and never contain \(z\). Therefore corresponding resolutions have identical grounded extensions. Their families of grounded extensions are identical, so their inclusion-minimal members are identical as well. This proves the lemma.
Now construct a society with types \(G\) and \(G^+\), each of mass \(1/2\), and threshold \(q=1\). They are distinct because their argument sets have different cardinalities. By the lemma, either both types accept \(p\), giving accepting mass \(1\), or neither does, giving accepting mass \(0\).
This is another polynomial-time reduction, proving hardness for \(\tau=2\), equal masses, and a fixed threshold.
The supplied polynomial extension-membership algorithm also yields a direct exact algorithm. For each type, enumerate all subsets \(S\subseteq A_t\) containing \(p\), and test whether \(S\in E_{\mathrm{GR}^*}(G_t)\). Record whether any test succeeds, then compare the total accepting mass with \(q\).
There are at most \(2^m\) candidate sets per type. Using the same constant \(c\) as above, the deterministic running time is
\(O\bigl(\tau\,2^m m^c+(\tau+1)L^2\bigr)\).
Thus explicit support permits polynomial certificate verification and exact aggregation, while the single-framework acceptance problem supplies the hardness.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The argument establishes \(\mathrm{NP}\)-completeness using the two single-framework results explicitly supplied in the question. No major or minor mathematical issues were found.
The prover uses the supplied results for the same semantics defined in the task:
These results are premises of the task, so their proofs need not be reproduced. The prover does not assume a separate complexity result for the society problem.
The certificate and verifier are valid.
Soundness: Successful extension checks imply \(J\subseteq B\), where \(B\) is the set of all accepting types. Since every mass is positive, the displayed inequality
\[
\sum_{t\in B}\mu_t\ge\sum_{t\in J}\mu_t\ge q
\]
is valid.
Completeness: If the society satisfies the threshold, choosing \(J=B\) and one witnessing extension for each accepting type produces a valid certificate. All choices are finite, and every witness has at most \(m\) membership bits.
The certificate bound \(O(\tau m+\tau)\) is polynomial in \(L\) under the explicit input encoding. Certificates of rejection for unselected types are unnecessary: soundness needs only a sufficient accepting mass.
The arithmetic calculation is correct.
The integer \(D=d\prod_{t=1}^{\tau}b_t\) is positive and divisible by every relevant denominator. Consequently, multiplying the threshold inequality by \(D\) gives exactly the stated integer comparison.
The bit length of \(D\) is \(O(L)\), since the encoded denominator lengths contribute to the total input length. Moreover,
\[
0<a_t(D/b_t)=\mu_tD\le D,\qquad 0<c(D/d)=qD\le D.
\]
Every partial sum over distinct supported types is at most \(D\), because the masses are positive and sum to \(1\). Thus all compared integers have \(O(L)\) bits.
Constructing the product, computing the exact quotients and products, and accumulating the selected weights fits the claimed schoolbook bound \(O((\tau+1)L^2)\).
After indexing argument names, the frameworks admit adjacency-matrix representations of size \(O(m^2)\). A fixed polynomial bound \(O(m^c)\) for extension checking is justified by the supplied premise, with \(c\) enlarged to cover matrix processing. The stated verification bound
\[
O\bigl(\tau m^c+(\tau+1)L^2\bigr)
\]
therefore follows.
The reduction is correct and satisfies all input restrictions.
A society containing only \(G\), with mass \(1\) and threshold \(1\), has accepting mass \(1\) exactly when the original credulous-acceptance instance is positive; otherwise its accepting mass is \(0\).
Singleton support satisfies the distinctness condition automatically. Both the mass and threshold are permitted binary rationals. The construction preserves the framework and query and has polynomial size.
This is a polynomial-time many-one reduction from the supplied \(\mathrm{NP}\)-complete problem. Together with membership, it establishes \(\mathrm{NP}\)-completeness.
The additional lemma is correct.
The grounded fixed-point characterization invoked here applies to finite frameworks, including frameworks with self-attacks.
The padded and original frameworks have different argument-set cardinalities and thus are distinct types. Equal masses \(1/2\) and threshold \(1\) satisfy the input requirements. The lemma ensures that both types accept together or reject together, validating the second reduction.
Enumerating all subsets containing \(p\) is exhaustive for credulous acceptance. Each type has at most \(2^m\) candidates, and the supplied extension checker decides each candidate correctly. The stated bound
\[
O\bigl(\tau\,2^m m^c+(\tau+1)L^2\bigr)
\]
is valid, with preprocessing absorbed by the existing terms.
The conclusion that a polynomial-time algorithm exists if and only if \(\mathrm{P}=\mathrm{NP}\) follows from \(\mathrm{NP}\)-completeness.
No additional clarification or repair is needed.
⟨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.