Answer: All three decision problems are \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even for equal positive dyadic masses. Verification is \(\mathrm{coNP}\)-complete. None is in \(\mathrm{P}\) unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate• V erσ is coNP-complete for σ ∈{c-pr, c-ss}. • Both CAc-pr andSAc-pr are ΘP 2 -hard and in ∆P 2 . • Both CAc-ss andSAc-ss are ΘP 2 -complete. It turns out that, under standard complexity assumptions, computing credulous and skeptical acceptance under the car- dinality based semantics c-pr and c-ss is easier than under classical maximal-set semantics pr and ss.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of participant-argument types \(T\), an attack relation \(R\subseteq T\times T\), binary-rational masses \(\mu_t>0\) summing to \(1\), and a goal type \(g\), consider the complete extensions of the AF \((T,R)\). For a complete extension \(E\), let \(D(E)=\{t\in T:\exists u\in E,\ (u,t)\in R\}\), \(U(E)=T\setminus(E\cup D(E))\), and \(u_\mu(E)=\sum_{t\in U(E)}\mu_t\). Decide whether a supplied \(E\) minimizes \(u_\mu\) among complete extensions, whether some such minimizing extension contains \(g\), or whether every such minimizing extension contains \(g\).
A society is given explicitly by its support \(T\): the list of \(\tau=|T|\geq 1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Support size counts listed types, not all possible types.
An explicitly listed attack relation \(R\subseteq T\times T\), allowing self-attacks, defines a Dung argumentation framework. Extensions are ordinary Dung complete extensions \(E\subseteq T\); membership accepts the whole type.
Define \(D(E)=\{t\in T:\exists s\in E,\ (s,t)\in R\}\), \(U(E)=T\setminus(E\cup D(E))\), and \(u_\mu(E)=\sum_{t\in U(E)}\mu_t\). Retain every complete extension minimizing \(u_\mu\), including all ties.
Consider three decision problems: whether a supplied set \(S\subseteq T\) is a retained extension; whether some retained extension contains a supplied goal \(g\in T\); and whether every retained extension contains \(g\). Verification rejects sets that are not complete extensions.
Write running times in \(m=|R|\), \(\tau\), and the total binary input length \(L\).
For each of these three decision problems, is it in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
For discrete arguments, minimizing the number of undecided arguments gives \(\mathrm{coNP}\)-complete verification and \(\Theta_2^P\)-complete credulous and skeptical acceptance. [Source](https://www.ijcai.org/proceedings/2022/0349.pdf)
No separate complexity classification for arbitrary rational masses was verified.
All three problems are \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even when all masses are equal dyadic rationals. Thus none has a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
For arbitrary binary-encoded rational masses, we additionally obtain:
| Problem | Proven classification |
|---|---|
| Whether a supplied set is retained | \(\mathrm{coNP}\)-complete; hence \(\mathrm{NP}\)-hard under polynomial-time Turing reductions |
| Whether some retained extension contains the goal | \(\Theta_2^{\mathrm P}\)-hard and in \(\mathrm{P}^{\mathrm{NP}}\) |
| Whether every retained extension contains the goal | \(\Theta_2^{\mathrm P}\)-hard and in \(\mathrm{P}^{\mathrm{NP}}\) |
The bounds on acceptance do not assert an exact complexity classification for arbitrary rational masses. They do settle the requested hardness question.
Define the set of arguments defended by a set \(E\) as
\(\operatorname{Acc}(E)=\{t\in T:\text{every }s\text{ with }(s,t)\in R\text{ belongs to }D(E)\}\).
Under ordinary Dung semantics, \(E\) is complete exactly when
\(E\cap D(E)=\varnothing\quad\text{and}\quad E=\operatorname{Acc}(E)\).
Consequently, completeness can be checked in \(O(m+\tau)\) graph operations:
This procedure includes self-attacks and types with no attackers.
Every finite Dung framework has a grounded extension, which is complete. Since the explicitly listed set \(T\) is finite, there is at least one complete extension, and the minimum objective value exists.
Write each input mass as \(\mu_t=p_t/q_t\), with positive integers encoded in binary. Set
\(Q=\prod_{t\in T}q_t,\qquad w_t=p_t(Q/q_t)\).
Then every \(w_t\) is a positive integer, and normalization gives
\(\sum_{t\in T}w_t=Q\).
For any set \(E\), define
\(W(E)=\sum_{t\in U(E)}w_t\).
We have \(u_\mu(E)=W(E)/Q\). Hence minimizing \(u_\mu\) is exactly equivalent to minimizing \(W\), including all ties.
The integers \(Q\) and \(w_t\) have \(O(L)\) bits: the bit length of a product is bounded by the sum of the bit lengths of its factors. Using schoolbook integer arithmetic, they can be computed in \(O(\tau L^2)\) bit operations. Subsequently, evaluating \(W(E)\), once \(U(E)\) is known, takes \(O(\tau L)\) bit operations.
Thus large denominator values do not require expanding the society into individual units.
The cited paper defines *cardinality semi-stable* extensions as complete extensions minimizing the number of undecided arguments. Its Theorem 4 states that verification is \(\mathrm{coNP}\)-complete and that both credulous and skeptical acceptance are \(\Theta_2^{\mathrm P}\)-complete for this semantics. Its definition of undecided arguments is exactly \(T\setminus(E\cup D(E))\). [Alfano et al., Definition 4 and Theorem 4](https://www.ijcai.org/proceedings/2022/0349.pdf)
Here is a polynomial-size reduction that also ensures the masses are dyadic.
Let \((A,R)\) be a discrete framework with \(n=|A|\geq 1\). Choose the least power of two \(N\) satisfying \(N\geq n\). Add a set \(I\) of \(N-n\) fresh isolated arguments, and define the society by
\(T=A\cup I,\qquad \mu_t=1/N\quad(t\in T)\),
with exactly the original attacks \(R\). We have \(n\leq N<2n\), so the construction has polynomial size. The masses are positive dyadic rationals and sum to one.
The complete extensions of the padded framework are exactly
\(\{E\cup I:E\text{ is a complete extension of }(A,R)\}\).
Indeed, every isolated argument has no attackers, so every set defends it. Completeness therefore requires all of \(I\) to be accepted. Isolated arguments neither attack original arguments nor introduce new attackers, so conflict-freeness and defense on \(A\) remain exactly as in the original framework.
Furthermore,
\(D_T(E\cup I)=D_A(E),\qquad U_T(E\cup I)=U_A(E)\).
Consequently,
\(u_\mu(E\cup I)=|U_A(E)|/N\).
Multiplication by the fixed positive factor \(1/N\) preserves every objective comparison and every tie. Thus the retained extensions are exactly the padded cardinality semi-stable extensions.
For verification, map an original supplied set \(S\) to \(S\cup I\). The correspondence preserves both completeness and retention, so verification in the society model is \(\mathrm{coNP}\)-hard.
For either acceptance problem, keep the original goal \(g\in A\). Since \(g\in E\cup I\) exactly when \(g\in E\), credulous and skeptical acceptance both inherit \(\Theta_2^{\mathrm P}\)-hardness. In particular, they are \(\mathrm{NP}\)-hard, because \(\mathrm{NP}\subseteq\Theta_2^{\mathrm P}\).
Finally, \(\mathrm{coNP}\)-hardness implies the requested Turing \(\mathrm{NP}\)-hardness for verification. For any language \(B\in\mathrm{NP}\), its complement belongs to \(\mathrm{coNP}\), so it reduces to verification. One verification-oracle query followed by negation decides membership in \(B\).
This proves the requested hardness classification for all three problems.
The complement of verification has a polynomial-time certificate procedure.
If the supplied set \(S\) is not complete, the deterministic completeness check establishes rejection. Otherwise, non-retention means that there exists a complete extension \(F\) with
\(W(F)<W(S)\).
The certificate is the \(\tau\)-bit membership vector of \(F\). Completeness and the strict integer comparison are checkable in polynomial time.
Therefore verification belongs to \(\mathrm{coNP}\). Together with Section 2, this proves \(\mathrm{coNP}\)-completeness for arbitrary rational masses.
Consider the threshold predicate
\(\mathcal{B}(k):\quad\text{there exists a complete extension }E\text{ with }W(E)\leq k\).
It belongs to \(\mathrm{NP}\): guess \(E\), check completeness, and evaluate its integer objective.
Let
\(W^*=\min\{W(E):E\text{ is complete}\}\).
Because \(0\leq W(E)\leq Q\), binary search using \(\mathcal{B}\) finds \(W^*\) with \(O(\log(Q+1))=O(L)\) adaptive \(\mathrm{NP}\)-oracle queries.
Once \(W^*\) is known:
Each existential question belongs to \(\mathrm{NP}\). Thus both acceptance problems belong to \(\mathrm{P}^{\mathrm{NP}}\), using \(O(L)\) oracle queries.
For equal masses, the objective has only \(\tau+1\) possible cardinality values, giving \(O(\log(\tau+1))\) queries instead. That shorter search does not follow for arbitrary rational masses.
A deterministic algorithm for all three problems enumerates the \(2^\tau\) subsets of the listed support, checks completeness, and evaluates the complete extensions.
During enumeration it maintains the minimum objective. For acceptance it also maintains whether the goal appears in some or every extension attaining the current minimum; these flags are reset whenever a smaller value is found.
With indexed graph access, a conservative bound charging logarithmic cost for graph indices is
\(O\!\left(\tau L^2+2^\tau\bigl((m+\tau)\log(\tau+1)+\tau L\bigr)\right)\).
The preprocessing term performs the exact rational-to-integer conversion. The per-subset terms perform the graph checks and integer summation. Storage is polynomial in \(m+\tau+L\), because extensions can be processed individually.
The oracle algorithms above use polynomial deterministic work in \(m,\tau,L\); their threshold and final-query witnesses can each be checked in
\(O\!\left((m+\tau)\log(\tau+1)+\tau L\right)\)
after preprocessing.
These bounds depend on the number \(\tau\) of explicitly listed types, never on an ambient space of possible types or on a numerical expansion of the masses. In particular, fixed \(\tau\) gives polynomial running time in \(L\); hardness concerns unbounded listed support.
⟨structured verdict parsed — rendered above⟩
The prover resolves all three decision problems correctly. Each is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already on instances with equal positive dyadic masses. The additional upper bounds for arbitrary rational masses are also justified.
No major or minor mathematical issues were found.
The characterization
\[
E\cap D(E)=\varnothing,\qquad E=\operatorname{Acc}(E)
\]
is exactly ordinary Dung completeness: the first condition gives conflict-freeness, and the second requires acceptance of precisely the arguments defended by \(E\).
The described attack scans compute these conditions correctly. In particular:
The claimed \(O(m+\tau)\) graph-operation bound is valid with indexed membership arrays. The later running-time statement explicitly charges for graph indices.
The invoked existence theorem is stated with its relevant hypothesis: every finite Dung framework has a complete grounded extension. Here \(T\) is finite, so the optimization domain is nonempty. Consequently, both the minimum and the skeptical quantification over retained extensions are well-defined.
The conversion
\[
Q=\prod_{t\in T}q_t,\qquad w_t=p_t(Q/q_t)
\]
is valid because every \(q_t\) divides \(Q\). Positivity of the input masses gives positive integer weights. Normalization yields
\[
\sum_{t\in T}w_t=Q.
\]
Thus \(W(E)/Q=u_\mu(E)\), and the common positive denominator preserves strict comparisons, equality, and every tie.
The bit-length bounds are correct. The total bit length of the denominators bounds the bit length of their product, and the numerators and intermediate products also have \(O(L)\) bits. The stated \(O(\tau L^2)\) preprocessing bound is conservative for schoolbook multiplication and division. Summing at most \(\tau\) weights costs \(O(\tau L)\) bit operations.
The argument does not require denominators to be small, coprime, or written in lowest terms.
The citation matches the claimed result. Definition 4 selects complete extensions minimizing the cardinality of the undecided set, and Theorem 4 gives \(\mathrm{coNP}\)-complete verification and \(\Theta_2^{\mathrm P}\)-complete credulous and skeptical acceptance for that semantics. The paper’s undecided set agrees with the task’s definition. [Alfano et al., Definition 4 and Theorem 4](https://www.ijcai.org/proceedings/2022/0349.pdf)
The prover therefore invokes the appropriate theorem, rather than a theorem about ordinary semi-stable extensions selected by set inclusion.
For \(n\geq1\), the least power of two \(N\geq n\) satisfies \(n\leq N<2n\). Hence the number of added arguments is linear in the original support size, and the equal masses \(1/N\) have polynomial-length encodings.
The complete-extension correspondence is justified in both directions. Every isolated argument must belong to every complete extension because it is defended by every set. Its addition changes neither attacks nor defense among original arguments.
The identities
\[
D_T(E\cup I)=D_A(E),\qquad U_T(E\cup I)=U_A(E)
\]
follow from isolation and mandatory acceptance of \(I\). Consequently,
\[
u_\mu(E\cup I)=|U_A(E)|/N.
\]
This preserves all minimizers, including ties. Mapping \(S\) to \(S\cup I\) also preserves rejection of noncomplete candidates. Keeping the original goal preserves both existential and universal acceptance.
The restriction to nonempty source frameworks does not undermine hardness: empty frameworks contribute no nontrivial acceptance instances and only a trivial verification case.
The distinction between many-one hardness and Turing hardness is handled correctly.
For acceptance, inherited \(\Theta_2^{\mathrm P}\)-hardness implies the requested \(\mathrm{NP}\)-hardness because \(\mathrm{NP}\subseteq\Theta_2^{\mathrm P}\).
For verification, the prover correctly uses complementation: a reduction of the complement of an arbitrary \(\mathrm{NP}\) language to verification, followed by negating one oracle answer, gives a polynomial-time Turing reduction. No unwarranted many-one \(\mathrm{NP}\)-hardness claim is made.
The verification complement has exactly the stated alternatives: the candidate is noncomplete, or a complete extension has strictly smaller objective. The latter has a polynomial-size certificate with polynomial-time verification. This establishes membership in \(\mathrm{coNP}\).
The threshold predicate belongs to \(\mathrm{NP}\). Since objectives are integers between \(0\) and \(Q\), binary search uses \(O(\log(Q+1))=O(L)\) queries. The final existential queries correctly test membership or nonmembership of the goal among extensions attaining the minimum. Negating the latter answer correctly decides skeptical acceptance.
Thus both acceptance problems belong to \(\mathrm P^{\mathrm{NP}}\). The prover appropriately refrains from claiming an exact classification for arbitrary masses.
The exhaustive algorithm correctly processes all \(2^\tau\) candidate sets and retains acceptance flags for every extension attaining the current minimum. Resetting those flags when a smaller value appears preserves the intended treatment of ties.
The stated bound accounts for preprocessing, completeness checks, and exact objective evaluation. Polynomial storage is sufficient because candidates can be processed individually.
The oracle bounds are explicitly oracle bounds, not ordinary polynomial-time algorithms. The concluding distinction between fixed \(\tau\) and unbounded listed support is correct.
No mathematical repair or additional clarification is needed. The proof establishes the requested hardness classification and the stated supplementary bounds.
⟨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.