Answer: For each fixed \(\sigma\in\{st,pr,co,ad\}\), the decision problem is \(\mathrm{NP}\)-complete. An exact algorithm takes \(O(2^{\tau-|C|}\tau^2L^2)=O(2^{m-|C|}m^2L^2)\) bit operations.
Theorem 12 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor any AF F and any semantics σ ∈{pr, co, ad}, N F st,U = V F st,U and N F σ,U = V F ad,U. The following AFs prove that the (ss, U)-characteristic is not adequately characterized by the (st, U)- or (ad, U)-values. F ∶ a1 a2 a3 a4 G ∶ a1 a2 a3 a4 The (st, U)-value of {a1} equals 2 because first, ∣R(F)↓{a1,a2}∣+ ∣st(F, {a1, a2})∣= 2 and second, there is no other superset C of {a1}, s.t. ∣R(F)↓C∣+∣st(F, C)∣< 2. In case of admissible semantics we deduce V F ad,⪯N W ({a1}) = 0 since {a1} is admissible in F. On the other hand N F ss,U({a1}) ≠0 since {a1} and all its proper supersets are not semi-stable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a baseline attack relation \(R\subseteq T\times T\), a target \(C\subseteq T\), and \(\sigma\in\{st,pr,co,ad\}\), choose a relation \(R'\) and a \(\sigma\)-extension \(E\) of \((T,R')\) with \(C\subseteq E\) minimizing \(\sum_{(t,u)\in R\triangle R'}\mu_t\mu_u\). Each type-pair edit applies uniformly to all ordered argument-instance pairs in that block.
A society is given by its support: a nonempty list \(T\) of \(\tau\) argument types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; there is no separate candidate universe, so \(m=\tau\). Let \(L\) be the total input bit length.
The input also specifies an attack relation \(R\subseteq T\times T\), a target \(C\subseteq T\), a binary-rational budget \(B\geq0\), and \(\sigma\in\{st,pr,co,ad\}\), denoting standard Dung stable, preferred, complete, and admissible semantics.
An edit chooses any \(R'\subseteq T\times T\), allowing attack additions and deletions, including self-attacks, while keeping \(T\) and its masses fixed. Each ordered type-pair edit applies uniformly to the entire corresponding block of argument-instance pairs.
Extensions are subsets \(E\subseteq T\) evaluated under the named semantics on \((T,R')\); membership includes an entire type, and masses affect only edit costs. Define \(w(R,R')=\sum_{(t,u)\in R\triangle R'}\mu_t\mu_u\). Decide whether some such \(R'\) has a \(\sigma\)-extension \(E\) with \(C\subseteq E\) and \(w(R,R')\leq B\).
For each fixed \(\sigma\in\{st,pr,co,ad\}\), is this decision problem in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).
For unrestricted discrete modifications with unit attack-edit costs, the minimum enforcement cost has a local minimization characterization; preferred, complete, and admissible enforcement costs coincide.
For the discrete fixed-argument version, non-strict enforcement within a unit-edit budget is \(\mathrm{NP}\)-complete under all four semantics ([Wallner, Niskanen, and Järvisalo](https://www.cs.helsinki.fi/u/mjarvisa/papers/wallner-niskanen-jarvisalo.aaai16.pdf)). No result explicitly treating this normalized mass-product cost model was located.
For each fixed \(\sigma\in\{st,pr,co,ad\}\), the problem is \(\mathrm{NP}\)-complete. Hardness holds even with equal dyadic masses, a target of size three, and a positive budget permitting exactly one ordered-pair edit.
An exact deterministic algorithm runs in
\[
O\!\left(2^{\tau-|C|}\tau^2L^2\right)
=
O\!\left(2^{m-|C|}m^2L^2\right)
\]
bit operations using elementary integer arithmetic. Here \(m=\tau\), as stipulated; there is no additional candidate-universe parameter.
I prove the complexity classification and the algorithm below.
For an attack relation \(S\subseteq T\times T\), a set \(E\subseteq T\) is conflict-free if \(S\cap(E\times E)=\varnothing\). It defends \(x\) if every attacker of \(x\) is attacked by some member of \(E\).
The four semantics are:
A stable set is admissible: every attacker of a member of \(E\) lies outside \(E\), and stability supplies a counterattack.
Lemma. Every admissible set in a finite framework is contained in a preferred extension, and every preferred extension is complete.
Proof. Finiteness gives an inclusion-maximal admissible superset \(P\) of any admissible set.
To prove that \(P\) is complete, suppose that \(P\) defends \(x\notin P\). First, no member \(p\in P\) can attack \(x\): defense of \(x\) would require a member of \(P\) attacking \(p\), contradicting conflict-freeness.
Also, \(x\) cannot attack a member \(p\in P\). Defense of \(p\) would then require a member of \(P\) attacking \(x\), which was just excluded. Finally, \(x\) cannot attack itself, because defense of \(x\) would again require an attack from \(P\) to \(x\).
Thus \(P\cup\{x\}\) is conflict-free. It defends its members because \(P\) already defends both its own members and \(x\). This contradicts maximality of \(P\). Consequently, \(P\) contains every argument it defends and is complete. \(\square\)
It follows, for every fixed edited relation \(R'\), that
\[
\exists E\in ad(T,R'):\ C\subseteq E
\quad\Longleftrightarrow\quad
\exists E\in co(T,R'):\ C\subseteq E
\quad\Longleftrightarrow\quad
\exists E\in pr(T,R'):\ C\subseteq E.
\]
Therefore, the feasible edited relations—and hence their minimum costs—coincide for admissible, complete, and preferred non-strict enforcement. This conclusion holds for the given weighted costs.
The degenerate case \(C=\varnothing\) is always a yes-instance for these three semantics, even at budget zero. The hardness construction below uses a nonempty target and a positive budget.
Fix a nonempty candidate set \(E\subseteq T\). Define
\[
D(E)=\sum_{(t,u)\in R\cap(E\times E)}\mu_t\mu_u,
\qquad
a(E)=\min_{t\in E}\mu_t.
\]
For each \(v\notin E\), define
\[
I_E(v)=\sum_{\substack{u\in E\\(v,u)\in R}}\mu_u,
\qquad
H_E(v)=
\begin{cases}
1,&\text{if some }t\in E\text{ satisfies }(t,v)\in R,\\
0,&\text{otherwise}.
\end{cases}
\]
The minimum costs of making this particular \(E\) admissible or stable are respectively
\[
\Phi_{ad}(E)
=
D(E)+
\sum_{\substack{v\notin E\\H_E(v)=0}}
\mu_v\min\{I_E(v),a(E)\},
\]
and
\[
\Phi_{st}(E)
=
D(E)+
\sum_{\substack{v\notin E\\H_E(v)=0}}
\mu_v a(E).
\]
Proof. Every original attack inside \(E\times E\), including every self-attack on a member of \(E\), must be deleted. This costs exactly \(D(E)\).
Consider \(v\notin E\). If \(H_E(v)=1\), retaining an existing attack from \(E\) to \(v\) provides the required counterattack, at no additional cost.
Suppose \(H_E(v)=0\). To make \(E\) admissible, there are precisely two possibilities:
For stability, the second possibility is mandatory.
The attack pairs involved for different outside vertices are disjoint, and they are disjoint from \(E\times E\). Attacks with both endpoints outside \(E\) affect neither condition and can be retained. Thus the local lower bounds add, and the described edits attain them. \(\square\)
Set \(\Phi_{ad}(\varnothing)=0\) and \(\Phi_{st}(\varnothing)=+\infty\), since \(T\) is nonempty. The global optimum is therefore
\[
\operatorname{OPT}_{\sigma}
=
\begin{cases}
\displaystyle\min_{C\subseteq E\subseteq T}\Phi_{ad}(E),
&\sigma\in\{ad,co,pr\},\\[6pt]
\displaystyle\min_{C\subseteq E\subseteq T}\Phi_{st}(E),
&\sigma=st.
\end{cases}
\]
There are \(2^{\tau-|C|}\) candidate sets. Each formula takes \(O(\tau^2)\) arithmetic operations.
For exact bit complexity, write \(\mu_t=p_t/q_t\), and let
\[
Q=\prod_{t\in T}q_t,
\qquad
A_t=Q\mu_t.
\]
The integers \(Q\) and \(A_t\) have \(O(L)\) bits. Multiplying costs by \(Q^2\) makes the formulas integral: for example,
\[
Q^2\Phi_{ad}(E)
=
\sum_{(t,u)\in R\cap(E\times E)}A_tA_u
+
\sum_{\substack{v\notin E\\H_E(v)=0}}
A_v\min\!\left\{
\sum_{\substack{u\in E\\(v,u)\in R}}A_u,\
\min_{t\in E}A_t
\right\}.
\]
Budget comparison uses integer cross-multiplication. All these integers have \(O(L)\) bits, so elementary arithmetic gives the claimed
\[
O\!\left(2^{\tau-|C|}\tau^2L^2\right)
\]
bit-operation bound, including preprocessing.
For stable semantics, guess \(R'\) and \(E\). Check \(C\subseteq E\), conflict-freeness, and whether \(E\) attacks every outside type.
For admissible semantics, instead check whether every attacker of a member of \(E\) is attacked by \(E\). Both semantic checks take \(O(\tau^2)\) Boolean operations.
Compute the edit cost exactly using the integer scaling above. Its verification takes \(O(\tau^2L^2)\) bit operations. The certificate contains \(O(\tau^2)\) bits for \(R'\) and \(O(\tau)\) bits for \(E\).
For complete and preferred semantics, an admissible witness containing \(C\) suffices by the lemma. Thus all four decision problems belong to \(\mathrm{NP}\); checking preferred maximality is unnecessary.
I give a polynomial reduction from \(3\)-SAT.
Let \(\varphi\) have variables \(x_1,\ldots,x_d\) and clauses \(K_1,\ldots,K_r\). Construct a framework \(F_\varphi\) with:
Its attacks are exactly:
Claim. If \(\varphi\) is satisfiable, \(F_\varphi\) has a stable extension containing \(q\). Conversely, if \(F_\varphi\) has an admissible set containing \(q\), then \(\varphi\) is satisfiable.
Proof. Given a satisfying assignment, take \(q\) together with the one true literal argument for each variable. This set is conflict-free. It attacks every omitted literal through the mutual literal attacks, and every clause argument through a true literal in that clause. Hence it is stable.
Conversely, let \(E\) be admissible and contain \(q\). Clause arguments cannot belong to \(E\), because they self-attack. Since each \(c_j\) attacks \(q\), defense of \(q\) requires some member of \(E\) attacking \(c_j\). Such a member must be a literal occurring in \(K_j\).
Conflict-freeness prevents \(E\) from containing both literals of any variable. Assign each selected literal to be true, and assign unrepresented variables arbitrarily. Every clause has a selected true literal, so this assignment satisfies \(\varphi\). \(\square\)
Let \(n\) be the number of arguments in \(F_\varphi\). Take three disjoint copies, with distinguished arguments \(q_1,q_2,q_3\). Add isolated arguments until the total number \(N\) is a power of two. Choosing the least such power gives
\[
3n\leq N<6n.
\]
Use these \(N\) arguments as the support and assign
\[
\mu_t=\frac1N
\quad\text{for every }t,
\qquad
C=\{q_1,q_2,q_3\},
\qquad
B=\frac1{N^2}.
\]
These masses are positive dyadic rationals summing to one. Every ordered-pair edit costs exactly \(1/N^2\), so the budget allows at most one edit, including an addition, deletion, or self-attack edit. The construction has polynomial encoding length.
If \(\varphi\) is satisfiable, choose a stable extension containing \(q_i\) in each copy and include every isolated padding argument. Their union is stable in the original relation. It is also preferred and complete: stability prevents any conflict-free proper superset, and the lemma makes every preferred extension complete. Thus all four enforcement instances are yes-instances with zero edits.
Conversely, suppose an edited relation within budget has a \(\sigma\)-extension \(E\) containing \(C\). At most one ordered pair was edited. Its two endpoints belong to at most two of the three copies. Therefore, some copy has no edited pair incident to any of its vertices.
That copy retains its original internal attacks and has no attacks to or from other components. Every extension under any of the four semantics is admissible. Restrict \(E\) to the untouched copy:
The restriction is consequently an admissible set containing that copy’s distinguished argument. The preceding claim implies that \(\varphi\) is satisfiable.
This proves \(\mathrm{NP}\)-hardness for each fixed semantics under the stated positive-budget restriction.
The classification agrees with Proposition 2 of [Wallner, Niskanen, and Järvisalo](https://www.cs.helsinki.fi/u/mjarvisa/papers/wallner-niskanen-jarvisalo.aaai16.pdf), which establishes \(\mathrm{NP}\)-completeness for unit-cost non-strict enforcement. The reduction above directly verifies hardness under normalized dyadic mass-product costs.
| Fixed semantics | Complexity | Exact deterministic bit-operation bound |
|---|---|---|
| \(st\) | \(\mathrm{NP}\)-complete | \(O(2^{\tau-|C|}\tau^2L^2)\) |
| \(pr\) | \(\mathrm{NP}\)-complete | \(O(2^{\tau-|C|}\tau^2L^2)\) |
| \(co\) | \(\mathrm{NP}\)-complete | \(O(2^{\tau-|C|}\tau^2L^2)\) |
| \(ad\) | \(\mathrm{NP}\)-complete | \(O(2^{\tau-|C|}\tau^2L^2)\) |
Thus none admits a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\). The local cost characterization makes a fixed candidate set tractable; choosing a suitable superset of \(C\) remains \(\mathrm{NP}\)-hard.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed classification. For each of the four fixed semantics, the decision problem is \(\mathrm{NP}\)-complete. The semantic equivalence, weighted local cost formulas, exact arithmetic bounds, and positive-budget reduction are correct. No major or minor mathematical issues were found.
The proof uses precisely the permitted model:
Neither the algorithm nor the reduction introduces a separate candidate universe or changes the support during editing. Padding belongs to the construction of the input instance, which is permitted.
The definitions of admissible, complete, preferred, and stable extensions are standard and correct.
The argument that stability implies admissibility is valid: conflict-freeness puts every attacker of an extension member outside the extension, and stability ensures that this attacker is counterattacked.
The lemma is also proved correctly:
Thus the asserted existential equivalence for admissible, complete, and preferred extensions containing \(C\) holds for each fixed edited relation. Equality of their feasible edited relations, and hence minimum costs, follows independently of the particular cost weights.
The empty-target observation for these three semantics is correct.
The formulas correctly account for all necessary modifications for a fixed nonempty \(E\).
Internal attacks. Every original attack in \(E\times E\) must be deleted. This includes self-attacks, and its cost is exactly \(D(E)\).
Outside vertices already attacked by \(E\). When \(H_E(v)=1\), retaining an existing counterattack suffices for admissibility and satisfies the relevant stability requirement. Deleting internal attacks does not remove this counterattack.
Outside vertices not attacked by \(E\). When \(H_E(v)=0\), the two admissibility alternatives are exhaustive:
Their minimum costs are respectively \(\mu_v I_E(v)\) and \(\mu_v a(E)\). A single added counterattack handles every attack from \(v\) into \(E\). For stability, an attack from \(E\) to \(v\) is mandatory.
The decomposition is valid because the relevant ordered pairs for distinct outside vertices are disjoint and do not overlap \(E\times E\). Attacks entirely outside \(E\) do not affect whether this particular \(E\) is admissible or stable.
Therefore both local formulas give attainable lower bounds and are exact.
Minimizing the fixed-set costs over all \(E\supseteq C\) correctly gives the enforcement optimum.
For complete and preferred semantics, this uses the previously established equality of feasible edited relations; it does not incorrectly assert that the candidate \(E\) itself must be complete or preferred.
The empty-set conventions are correct:
The case \(E=T\) is also handled: there are no outside-vertex contributions, and deleting all internal attacks suffices.
There are exactly \(2^{\tau-|C|}\) candidate supersets.
For each candidate, the internal attack sum and the outside-vertex data can be computed in \(O(\tau^2)\) arithmetic operations.
The common-denominator scaling is valid:
Elementary integer multiplication and division therefore support the stated bound of \(O(2^{\tau-|C|}\tau^2L^2)\) bit operations, including preprocessing. Replacing \(\tau\) with \(m\) is legitimate because the task stipulates \(m=\tau\).
The proposed certificate has polynomial length.
Stable verification requires conflict-freeness and coverage of all outside vertices. Admissibility verification requires checking that every attacker of an extension member is attacked by the extension. Both can be checked in \(O(\tau^2)\) Boolean operations.
Exact edit-cost verification is polynomial under the stated rational encoding.
For complete and preferred semantics, an admissible witness is sufficient because the decision problem asks for the existence of an extension containing \(C\). The lemma justifies this certificate without requiring verification of preferred maximality.
Thus membership in \(\mathrm{NP}\) is established for all four semantics.
Both directions of the framework claim are correct.
For a satisfying assignment, the selected literals together with \(q\) form a conflict-free set. They attack every omitted literal and every clause argument, so the set is stable.
Conversely, an admissible set containing \(q\):
The resulting consistent partial assignment extends to a satisfying assignment. The stated attack list supplies all the restrictions used in this reasoning.
The padding and budget calculations are correct:
In the satisfiable direction, the union of the three stable extensions and all padding vertices is stable. Its preferred and complete status follows as stated.
In the converse direction, one edited ordered pair touches vertices in at most two copies. Hence one copy remains completely untouched, including its separation from other components.
Restricting an admissible extension to that copy preserves admissibility: every attacker of a retained member lies in the copy, and any defender attacking that attacker must also lie in the copy. The restriction contains the corresponding distinguished argument, so the framework claim applies.
This establishes hardness even under the claimed positive-budget restriction.
The cited Proposition 2 does state \(\mathrm{NP}\)-completeness of unit-cost non-strict enforcement for admissible, complete, preferred, and stable semantics. Its fixed-argument, arbitrary attack-edit setting matches the comparison made in the output. [Wallner, Niskanen, and Järvisalo, Proposition 2](https://www.cs.helsinki.fi/u/mjarvisa/papers/wallner-niskanen-jarvisalo.aaai16.pdf).
The normalized mass-product classification does not depend on importing that result: the output supplies its own reduction and membership proof.
Combining these establishes all four claimed \(\mathrm{NP}\)-completeness results. The qualification about polynomial-time algorithms unless \(\mathrm{P}=\mathrm{NP}\) is correct.
No additional clarification or mathematical 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.