Answer: \(\Sigma_2^p\)-complete under polynomial-time many-one reductions, hence NP-hard.
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePCAsst (resp. PSAsst, NCAsst, and NSAsst) is Σp 2-complete (resp. Σp 3-complete, Πp 3-complete, and Πp 2- complete). Compared with the results for the other seman- tics (Baumeister et al. 2018), it turns out that deciding PCA and NCA for sst is more costly than for any other seman- tics, while deciding PSAsst and NSAsst costs the same as deciding PSApr and NSApr, respectively. Moreover, the re- sults of Theorems 5 and 6 complement those in Table 2, showing that, though problems DS, TS, and FS under sst and pr have the same complexity, these semantics behave differently under credulous reasoning.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicit finite support \(\{(\Delta_t,g_t)\}_{t=1}^{\tau}\) of claimant-case types with rational masses \(\mu_t\ge 0\) summing to \(1\), compute \(M=\sum_{t=1}^{\tau}\mu_t\,\mathbf{1}[\mathrm{PCA}_{\mathrm{sst}}(\Delta_t,g_t)]\), the population share whose queried literal is possibly credulously accepted under semi-stable semantics; equivalently, for rational \(q\in[0,1]\), decide whether \(M\ge q\). Each \(\Delta_t\) is an explicitly represented incomplete argumentation framework, and completions remain internal possibilities within each type.
A society is given by its support: the list of \(\tau\) claimant-case types \((\Delta_t,g_t)\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each explicitly represented incomplete argumentation framework is \(\Delta_t=\langle A_t,B_t,R_t,T_t\rangle\): disjoint certain and uncertain argument sets \(A_t,B_t\), and disjoint certain and uncertain attack sets \(R_t,T_t\subseteq(A_t\cup B_t)^2\). The query \(g_t\) is an argument in \(A_t\cup B_t\) or its negation.
A completion is \(\Lambda=\langle A',R'\rangle\) with \(A_t\subseteq A'\subseteq A_t\cup B_t\) and \(R_t\cap(A'\times A')\subseteq R'\subseteq(R_t\cup T_t)\cap(A'\times A')\).
Use standard Dung semi-stable semantics. For an extension \(E\) of a completion, its fulfillment is \(F_t(E,\Lambda)=E\cup\{\neg a:\exists b\in E,\ (b,a)\in R'\}\cup\{\neg a:a\in B_t\setminus A'\}\).
Define \(\mathrm{PCA}_{\mathrm{sst}}(\Delta_t,g_t)\) to hold precisely when some completion \(\Lambda\) has a semi-stable extension \(E\) with \(g_t\in F_t(E,\Lambda)\). Completions are internal possibilities, with no probabilities assigned to them.
Given also a binary rational \(q\in[0,1]\), decide whether \(M=\sum_{t=1}^{\tau}\mu_t\mathbf{1}[\mathrm{PCA}_{\mathrm{sst}}(\Delta_t,g_t)]\ge q\). Let \(m=\max_t|A_t\cup B_t|\) and \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this population-share threshold problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a single incomplete argumentation framework and queried literal, possible credulous acceptance under semi-stable semantics is \(\Sigma_2^p\)-complete ([Alfano et al.](https://www.researchgate.net/publication/357016535_Incomplete_Argumentation_Frameworks_Properties_and_Complexity_Technical_Report)). No result specifically treating the stated distribution over claimant-case types was located.
The population-share threshold problem is \(\Sigma_2^p\)-complete under polynomial-time many-one reductions, and therefore NP-hard. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
The hardness already holds for \(\tau=1\). The upper bound below addresses arbitrary explicitly listed supports and binary rational masses.
Fix a completion \(\Lambda=\langle V,H\rangle\). For \(E\subseteq V\), define its attacked set and range by
\(E_H^+=\{a\in V:\exists b\in E,\ (b,a)\in H\}\) and
\(\rho_\Lambda(E)=E\cup E_H^+\).
A set \(E\) is conflict-free if no attack has both endpoints in \(E\). It defends \(a\in V\) if every attacker of \(a\) is attacked by some member of \(E\). It is complete if it is conflict-free, defends every member of \(E\), and contains every argument it defends.
These conditions can be checked in \(O((m+1)^3)\) time by directly examining arguments and attacks.
Under standard Dung semi-stable semantics, \(E\) is semi-stable precisely when it is complete and no complete extension \(D\) satisfies
\(\rho_\Lambda(E)\subsetneq\rho_\Lambda(D)\).
The maximality is by set inclusion, not by cardinality.
Thus, after checking completeness of \(E\), failure of semi-stability has a polynomial-size certificate: a complete extension \(D\) with strictly larger range.
The additional conditions in the task are also polynomial-time checkable:
This verification uses exactly the task’s fulfillment definition, including negations of omitted uncertain arguments.
Write \(\mu_t=a_t/b_t\) and \(q=c/d\), with positive denominators. Define the common denominator
\(K=d\prod_{t=1}^{\tau}b_t\),
and the integer weights
\(w_t=a_t(K/b_t)\) and \(h=c(K/d)\).
Then, for every subset \(S\subseteq\{1,\ldots,\tau\}\),
\(\sum_{t\in S}\mu_t\ge q\) holds exactly when
\(\sum_{t\in S}w_t\ge h\).
The bit length of \(K\) is \(O(L)\), because the denominator encodings are part of the total input. Moreover, the hypotheses \(\sum_t\mu_t=1\) and \(q\in[0,1]\) imply
\(\sum_t w_t=K\) and \(0\le h\le K\).
All these integers therefore have \(O(L)\) bits.
Using ordinary integer multiplication and division, the weights can be computed in \(O(L^3)\) bit operations. Subsequent subset-weight comparisons are polynomial-time. No numerical approximation is required.
Let
\(Y=\{t:\mathrm{PCA}_{\mathrm{sst}}(\Delta_t,g_t)\}\).
Because every mass is positive,
\(\sum_{t\in Y}\mu_t\ge q\)
is equivalent to the existence of a subset \(S\subseteq Y\) satisfying
\(\sum_{t\in S}\mu_t\ge q\).
Indeed, the forward implication uses \(S=Y\); the reverse implication follows from positivity of the masses.
An existential certificate consists of:
The deterministic checks verify the weight threshold, each completion, completeness of each \(E_t\), and fulfillment of each query.
The remaining condition is universal: for every selected index \(t\) and every \(D\subseteq V_t\), either \(D\) is not complete in \(\Lambda_t\), or
\(\rho_{\Lambda_t}(E_t)\not\subsetneq\rho_{\Lambda_t}(D)\).
This is a polynomial-time predicate over the existential certificate and a universally quantified pair consisting of an index and an argument subset. The existential certificate has length
\(O(\tau(m^2+m+1))\),
and the universal pair needs
\(O(m+\log(\tau+1))\)
bits. Both lengths are polynomial in \(L\), since the frameworks and support are explicitly represented.
Using the existential-universal characterization of \(\Sigma_2^p\), this proves membership. For completeness, the certificate equivalence is exact:
For \(q=0\), the empty subset supplies a certificate, as expected.
The supplied single-framework result states that possible credulous acceptance under semi-stable semantics is \(\Sigma_2^p\)-complete. This is also stated in Theorem 6 of [Alfano et al.’s technical report](https://www.researchgate.net/publication/357016535_Incomplete_Argumentation_Frameworks_Properties_and_Complexity_Technical_Report).
Given an instance \((\Delta,g)\) of that problem, construct the society
\(\tau=1\), \((\Delta_1,g_1)=(\Delta,g)\), \(\mu_1=1\), and \(q=1/2\).
This is a valid support with a positive binary rational mass summing to one. Its population share is
\(M=\mathbf 1[\mathrm{PCA}_{\mathrm{sst}}(\Delta,g)]\).
Therefore,
\(M\ge 1/2\) if and only if
\(\mathrm{PCA}_{\mathrm{sst}}(\Delta,g)\).
The reduction copies the framework and adds only constant-size data. It is polynomial-time and establishes \(\Sigma_2^p\)-hardness.
Hardness also persists with two distinct support types and equal masses. Add a fresh certain argument \(z\) whose only attack is \((z,z)\), and query \(z\). Its only conflict-free set is empty; that set is complete and semi-stable, so the query is never fulfilled. Giving this type and the original type mass \(1/2\), with \(q=1/2\), again makes the threshold equivalent to the original acceptance question.
Together with Section 3, this proves \(\Sigma_2^p\)-completeness.
A direct exact algorithm also gives a useful parameter bound.
For type \(t\), put \(n_t=|A_t\cup B_t|\), \(b_t=|B_t|\), and \(u_t=|T_t|\). There are at most
\(2^{b_t+u_t}\)
completions: choose the uncertain arguments, then choose the uncertain attacks whose endpoints are present. Since \(b_t\le m\) and \(u_t\le m^2\), this is at most \(2^{m+m^2}\).
For each completion:
Step 3 can be implemented without comparing every pair of extensions. Index subsets by bit masks and let \(H(U)\) indicate whether \(U\) occurs as a complete-extension range. Compute
\(C(S)=\sum_{U\supseteq S}H(U)\)
using the subset dynamic program that starts with \(C=H\) and, for each argument \(i\), performs
\(C(S)\leftarrow C(S)+C(S\cup\{i\})\)
for every \(S\) omitting \(i\).
After processing the arguments, the recurrence sums exactly over all supersets. An occurring range \(S\) is maximal precisely when \(C(S)=1\): its own occurrence contributes one, and any strict superset would contribute another. The counters have at most \(m+1\) bits.
Consequently, each completion takes
\(O(2^m(m+1)^3)\)
bit operations. Computing all acceptance indicators and then comparing their exact weighted sum with \(q\) takes
\(O\!\left(\tau\,2^{m^2+2m}(m+1)^3+L^3\right)\)
bit operations.
Thus, fixed \(m\) yields polynomial time in \(\tau,L\); unrestricted \(m\) gives the \(\Sigma_2^p\)-complete problem proved above. Throughout, completions are existential possibilities, with no probabilities assigned to them.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The argument establishes \(\Sigma_2^p\)-completeness under polynomial-time many-one reductions, hence NP-hardness, for the explicitly listed support representation in USER_TASK.
I found no major or minor mathematical issues requiring repair. The stated polynomial-time consequence is correctly conditional: a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
The definitions of conflict-freeness, defense, and completeness are correct. Requiring conflict-freeness, defense of every member, and inclusion of every defended argument gives precisely a complete extension.
The characterization of semi-stable extensions is also correct: they are complete extensions whose ranges are maximal by set inclusion among complete-extension ranges. The prover correctly distinguishes inclusion maximality from maximum cardinality.
Consequently, once completeness of \(E\) has been verified, a complete extension \(D\) satisfying
\(\rho_\Lambda(E)\subsetneq\rho_\Lambda(D)\)
certifies failure of semi-stability. Such a certificate has polynomial length, and its validity is polynomial-time checkable.
The fulfillment checks agree exactly with the task:
In particular, omitted uncertain arguments are handled without treating completions as probabilistic events.
The claimed \(O((m+1)^3)\) verification bound is a valid conservative bound for direct examination of the explicitly represented framework after indexing its arguments.
Finding: Correct.
The common denominator
\(K=d\prod_{t=1}^{\tau}b_t\)
is divisible by every mass denominator and by the threshold denominator. Therefore, the definitions of \(w_t\) and \(h\) produce integers, and multiplication by the positive number \(K\) preserves the threshold comparison exactly.
The bit-length claim is correct: the logarithm of a product is the sum of the logarithms of its factors, and those denominator encodings are included in \(L\).
The input promises imply
\(\sum_t w_t=K\) and \(0\le h\le K\).
Because the weights are positive, each individual weight is at most \(K\). Thus the weights, threshold, and subset sums all have \(O(L)\) bits.
The \(O(L^3)\) arithmetic bound is conservative and valid using ordinary multiplication and exact division, since there are at most \(O(L)\) encoded support entries.
Finding: Correct; binary rational masses introduce no hidden numerical approximation or exponential arithmetic cost.
The crucial equivalence is valid:
\(M\ge q\) holds exactly when some subset of accepting types has total mass at least \(q\).
The forward direction chooses all accepting types. The reverse direction uses positivity of the masses. Thus the certificate need not establish that excluded types fail acceptance.
The existential certificate contains a selected subset and an independent completion-extension witness for each selected type. Its stated size,
\(O(\tau(m^2+m+1))\),
is sufficient to encode argument selections, attack selections, and extension memberships. Explicit representation ensures this is polynomial in \(L\).
After the deterministic checks, the remaining condition is precisely the absence of a complete extension with a strictly larger range in any selected completion. Quantifying universally over a selected index and a candidate subset checks all such competitors. The candidate subset and index require only
\(O(m+\log(\tau+1))\)
bits.
This gives the required existential-universal polynomial-time predicate. Both directions of the certificate equivalence are explicitly justified.
The boundary case \(q=0\) is correctly handled by the empty selection. The same reasoning applies at \(q=1\); no additional exception is needed.
Finding: Correct. The upper bound addresses arbitrary explicitly listed supports.
The external result is stated with the relevant problem and complexity class. Theorem 6 of the linked [Alfano et al. technical report](https://www.researchgate.net/publication/357016535_Incomplete_Argumentation_Frameworks_Properties_and_Complexity_Technical_Report) confirms \(\Sigma_2^p\)-completeness of possible credulous acceptance under semi-stable semantics. Its hardness already follows from ordinary complete-framework credulous acceptance, so the task’s additional fulfillment rule for omitted uncertain arguments creates no obstacle to applicability.
The reduction uses one support type, mass \(1\), and threshold \(1/2\). These values satisfy every input promise. Since the resulting share is either \(0\) or \(1\), its threshold answer equals the original acceptance answer exactly.
The construction copies the framework and adds constant-size data, establishing the claimed polynomial-time many-one reduction.
The optional two-type construction also checks out. The auxiliary type is the fresh singleton framework with the self-attacking certain argument \(z\). Its only conflict-free set is empty; the empty set does not defend \(z\), so it is complete and semi-stable. The positive query \(z\) is never fulfilled. Freshness ensures that this type is distinct from the original type.
Finding: Correct. Hardness already holds for \(\tau=1\).
There are at most \(2^{b_t+u_t}\) completions: argument choices contribute at most \(2^{b_t}\), and uncertain attack choices contribute at most \(2^{u_t}\). Attacks with absent endpoints only reduce the number of distinct valid completions.
Enumerating complete extensions requires at most \(2^m\) subset checks per completion.
The range calculation uses a Boolean occurrence indicator \(H(U)\), rather than the number of extensions realizing \(U\). This distinction makes the maximality criterion correct: for an occurring range \(S\), \(C(S)=1\) means that its own range is the only occurring superset.
The stated dynamic program computes the superset sums. Its counters are at most \(2^m\), so \(m+1\) bits suffice. Its arithmetic cost is within the claimed per-completion bound
\(O(2^m(m+1)^3)\).
Multiplying by the completion bound and summing over types gives exactly the reported conservative bound:
\(O(\tau\,2^{m^2+2m}(m+1)^3+L^3)\).
Finding: Correct. Fixed \(m\) yields polynomial time in \(\tau,L\), consistently with hardness when \(m\) is unrestricted.
No repair is required. The proof establishes the target classification, accounts for exact rational arithmetic, respects the fulfillment definition, and supplies running times in the requested parameters.
⟨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.