Answer: \(\mathrm{NP}\)-hard for every fixed \(\varepsilon>0\) and every \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\).
Theorem 4(1) — class: hardness
For fixed \(\varepsilon>0\) and \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\), an instance is a finite supported type set \(T\), a directed attack relation \(R\subseteq T\times T\), positive rational masses \(\mu_t\) summing to one, and a target type \(t^\star\). Each type occupies a measurable interval \(I_t\) of mass \(\mu_t\), with occurrences attacking according to \(R\); extensions obey the measurable lift of the paper's Dung semantics. Promise that some single type \(b\) has \(T\setminus\{b\}\) bipartite and \(\mu_b\le\varepsilon\). Decide whether a \(\sigma\)-extension contains positive mass of \(t^\star\).
Fix \(\varepsilon>0\) and \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\), denoting admissible, complete, preferred, semi-stable and stable semantics.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) counts supported types, not all possible types. Additional input consists of a directed relation \(R\subseteq T\times T\) and a target \(t^\star\in T\).
Partition \(U=[0,1)\) into consecutive half-open intervals \(I_t\) of lengths \(\mu_t\). Every occurrence in \(I_s\) attacks every occurrence in \(I_t\) exactly when \((s,t)\in R\); self-attacks are allowed.
Extensions are Lebesgue-measurable subsets of \(U\) satisfying the named Dung semantics pointwise, with all maximality comparisons restricted to measurable sets and using literal set inclusion. For semi-stable semantics, the range \(S^+\) consists of \(S\) and every occurrence attacked by an occurrence in \(S\), and is inclusion-maximal among ranges of measurable admissible sets.
Promise that there exists \(b\in T\) with \(\mu_b\le\varepsilon\) such that \(T\setminus\{b\}\) partitions into two sets containing no internal attacks. The witness \(b\) is not supplied. Decide whether some measurable \(\sigma\)-extension \(S\) satisfies \(\lambda(S\cap I_{t^\star})>0\), where \(\lambda\) is Lebesgue measure.
For each fixed \(\varepsilon\) and \(\sigma\), is this promised decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Express running times in the support size \(\tau\) and total input bit length \(L\); there is no separate candidate parameter \(m\).
Discrete credulous acceptance is \(\mathrm{NP}\)-hard for every listed semantics even when the minimum number of arguments whose deletion leaves a bipartite framework is exactly one. [Verified source](https://www.ijcai.org/Proceedings/11/Papers/177.pdf).
No result settling this precise continuous problem was identified in the literature search.
For every fixed \(\varepsilon>0\) and every \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\), the promised decision problem is \(\mathrm{NP}\)-hard.
The proof establishes an exact correspondence with finite credulous acceptance. In particular, the correspondence respects pointwise semantics, literal inclusion, and measurable competitors.
Let \(F=(T,R)\) be the finite framework on the supported types. For \(E\subseteq T\), define
\(A(E)=\{t\in T:\text{some }s\in E\text{ satisfies }(s,t)\in R\}\),
\(E^+=E\cup A(E)\),
\(D(E)=\{t\in T:\text{for every }s\text{ with }(s,t)\in R,\text{ some }r\in E\text{ satisfies }(r,s)\in R\}\),
and
\(\widehat E=\bigcup_{t\in E}I_t\).
Thus \(D(E)\) is the set of types defended by \(E\). Every \(\widehat E\) is measurable.
For a measurable \(S\subseteq U\), define its presence set
\(E(S)=\{t\in T:S\cap I_t\ne\varnothing\}\).
This definition uses nonemptiness, not positive measure: a selected occurrence of measure zero still attacks pointwise.
For every measurable \(S\), writing \(E=E(S)\), the occurrences attacked by \(S\) are exactly \(\widehat{A(E)}\), and the occurrences defended by \(S\) are exactly \(\widehat{D(E)}\). Consequently,
\(S^+=S\cup\widehat{A(E)}\),
and \(S\) is admissible if and only if \(E\) is admissible in \(F\).
Proof. An occurrence of type \(t\) is attacked by \(S\) exactly when \(S\) contains an occurrence of some type \(s\) with \((s,t)\in R\). This gives the attack identity.
Fix an occurrence of type \(t\). For every attacker type \(s\), every occurrence in \(I_s\) attacks it. Such an attacker occurrence is attacked by \(S\) exactly when some represented type \(r\in E\) attacks \(s\). Each \(I_s\) is nonempty because its mass is positive. Hence defence is precisely the condition defining \(D(E)\).
Likewise, \(S\) is conflict-free exactly when no pair of represented types attacks, including self-attacks. Equivalently, \(E\cap A(E)=\varnothing\). All selected occurrences are defended exactly when \(E\subseteq D(E)\). These are precisely finite admissibility. \(\square\)
In particular, if \(S\) is admissible, its saturation \(\widehat{E(S)}\) is an admissible measurable superset.
For \(\sigma\in\{\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\), the measurable \(\sigma\)-extensions are exactly the sets \(\widehat E\) where \(E\) is a finite \(\sigma\)-extension of \(F\).
Proof for complete semantics. If \(S\) is complete, its selected occurrences are defended. Defence is constant throughout each type interval, by Lemma 1. Completeness therefore requires every represented interval to be included in full, so \(S=\widehat E\).
For a saturated set, admissibility and inclusion of every defended occurrence are equivalent to finite admissibility and \(D(E)\subseteq E\). Thus completeness is equivalent in the two frameworks.
Proof for preferred semantics. An unsaturated admissible \(S\) has the strictly larger measurable admissible superset \(\widehat{E(S)}\), so it cannot be preferred.
If \(E\) is not finite preferred, a finite admissible strict superset \(B\supsetneq E\) yields the measurable admissible strict superset \(\widehat B\supsetneq\widehat E\).
Conversely, suppose a measurable admissible \(Q\) strictly contains \(\widehat E\). Its presence set \(B=E(Q)\) is admissible by Lemma 1. Because \(\widehat E\) already contains all occurrences of each type in \(E\), strict containment requires \(B\supsetneq E\). Therefore finite preferredness also implies measurable preferredness.
Proof for semi-stable semantics. Suppose \(S\) is admissible and unsaturated, with presence set \(E\). Conflict-freeness gives \(E\cap A(E)=\varnothing\). Every occurrence in \(\widehat E\setminus S\) is consequently outside \(S^+=S\cup\widehat{A(E)}\). Saturation therefore strictly increases the range:
\(S^+\subsetneq(\widehat E)^+=\widehat{E^+}\).
Thus every measurable semi-stable extension is saturated.
If a finite admissible \(B\) satisfies \(E^+\subsetneq B^+\), its saturation provides a strictly larger measurable range.
Conversely, suppose a measurable admissible \(Q\) satisfies
\(\widehat{E^+}\subsetneq Q^+\).
Let \(B=E(Q)\). Lemma 1 gives finite admissibility of \(B\) and
\(Q^+\subseteq\widehat{B^+}\).
Hence \(\widehat{E^+}\subsetneq\widehat{B^+}\). Since all intervals are nonempty and pairwise disjoint, this implies \(E^+\subsetneq B^+\). Finite and measurable range maximality are therefore equivalent.
Proof for stable semantics. A stable set is conflict-free. For its presence set \(E\), conflict-freeness gives \(E\cap A(E)=\varnothing\). Any omitted occurrence of a represented type is therefore neither selected nor attacked. Stability forces saturation.
For a saturated conflict-free set, \((\widehat E)^+=U\) holds exactly when \(E^+=T\), which is finite stability. \(\square\)
For every listed semantics,
\(\exists\text{ measurable }\sigma\text{-extension }S\text{ with }\lambda(S\cap I_{t^\star})>0\)
if and only if
\(\exists\text{ finite }\sigma\text{-extension }E\text{ of }F\text{ with }t^\star\in E\).
For admissible semantics, the forward direction follows from Lemma 1: positive measure implies presence. For the reverse direction, saturate the finite admissible extension.
For the other semantics, apply Lemma 2. Whenever \(t^\star\in E\),
\(\lambda(\widehat E\cap I_{t^\star})=\mu_{t^\star}>0\).
Thus positive masses affect neither the acceptance answer nor the finite semantics governing it.
Let \(F=(X,R)\) be a finite framework and let \(Z\) be a disjoint set of new isolated arguments. Write \(H\) for the framework on \(X\cup Z\), retaining exactly the attacks of \(F\).
Every subset of \(H\) has the form \(E=A\cup B\), with \(A\subseteq X\) and \(B\subseteq Z\). Directly from isolation,
These identities give the following extension descriptions.
For admissible semantics, \(B\) is arbitrary. For complete semantics, completeness forces \(B=Z\), and its remaining condition is precisely completeness of \(A\).
For preferred semantics, maximality forces \(B=Z\), since any omitted isolated argument can be added admissibly. Once \(B=Z\), maximality is equivalent to preferredness of \(A\).
For semi-stable semantics, omitting any isolated argument permits a strict range increase, so again \(B=Z\). Ranges then all contain exactly the same new set \(Z\); their inclusion comparisons reduce to those in \(F\).
For stable semantics, stability forces \(B=Z\), and the remaining requirement is \(A_F^+=X\).
Consequently, adding isolated arguments preserves credulous acceptance of every original argument under every listed semantics.
The supplied hardness theorem states that finite credulous acceptance is \(\mathrm{NP}\)-hard for every listed semantics on frameworks whose minimum deletion distance to bipartiteness is exactly one. Here bipartiteness means partitionability into two conflict-free sets, exactly as required by the present promise. This is Theorem 4(1) of [Ordyniak and Szeider, *Augmenting Tractable Fragments of Abstract Argumentation*](https://www.ijcai.org/Proceedings/11/Papers/177.pdf).
Fix \(\varepsilon>0\). Choose a fixed nonnegative integer \(K\) such that \(2^{-K}\le\varepsilon\). Because \(\varepsilon\) is fixed, \(K\) is a constant of the reduction.
Take a finite hardness instance \((F,x^\star)\), with \(n=|X|\). Let
\(N=2^{\max\{K,\lceil\log_2 n\rceil\}}\).
Add \(N-n\) isolated arguments, obtaining \(H\). Construct the society with:
These masses are positive dyadic rationals, sum to one, and satisfy \(\mu_t\le\varepsilon\).
Since \(F\) has deletion distance one to bipartiteness, there exists an original argument \(b\) such that \(F-b\) has the required partition. Place all new isolated arguments into either part. This proves that \(H-b\) also has the required partition, while \(\mu_b\le\varepsilon\). The reduction does not need to identify or supply \(b\).
Moreover,
\(\tau=N\le 2\max\{n,2^K\}=O_\varepsilon(n)\).
Each mass requires \(O(\log\tau)\) bits. With an explicit adjacency matrix, the output length is \(O(\tau^2+\tau\log\tau)\), and the construction takes polynomial time in these quantities.
By Section 3, padding preserves the finite acceptance answer. By Section 2, passing from types to occurrences preserves that answer. Therefore the constructed promised society is a yes-instance exactly when the original finite instance is a yes-instance.
This proves \(\mathrm{NP}\)-hardness for every fixed \(\varepsilon\) and every listed \(\sigma\).
The correspondence also gives finite decision procedures. Parse the input and enumerate the \(2^\tau\) type subsets. In an adjacency-matrix implementation, admissibility, completeness, stability and ranges each require \(O(\tau^2)\) operations per subset.
Thus admissible, complete and stable acceptance can be decided in
\(O(2^\tau\tau^2+L^{O(1)})\).
The same bound holds for preferred acceptance: an argument belongs to some preferred extension exactly when it belongs to some admissible set. Indeed, in a finite framework any admissible set has an inclusion-maximal admissible superset.
For semi-stable acceptance, enumerate all admissible sets and compare their ranges pairwise. This gives the sufficient bound
\(O(4^\tau\tau^2+L^{O(1)})\).
These algorithms are valid on the promised inputs without finding the deletion witness. All bounds use the supported type count \(\tau\) and total input bit length \(L\); no additional candidate parameter is needed.
⟨structured verdict parsed — rendered above⟩
The claimed classification is proved: for every fixed \(\varepsilon>0\) and every listed semantics, the promised continuous decision problem is \(\mathrm{NP}\)-hard. No major or minor mathematical issues were found.
The presence set \(E(S)\) correctly records nonempty intersections, including those of measure zero. This matches the task’s pointwise attacks and literal inclusion comparisons. Replacing nonemptiness by positive measure would not justify the subsequent correspondence; the prover avoids that error.
Every saturation \(\widehat E\) is measurable because it is a finite union of the given intervals. Positive masses ensure that all intervals are nonempty, which is needed both for the defence correspondence and for recovering type-set inclusion from inclusion of saturated sets.
All assertions in this lemma are correct.
Consequently, saturation preserves admissibility and produces a measurable superset. The argument also covers the empty set.
Complete semantics. Every selected occurrence is defended, and defence is constant throughout its type interval. Completeness therefore forces the whole represented interval into the extension. For saturated sets, the remaining completeness condition is exactly \(D(E)\subseteq E\), together with finite admissibility. Both directions are established.
Preferred semantics. An unsaturated admissible set has a strict measurable admissible superset obtained by saturation, so it cannot be preferred. For saturated sets, the proof correctly handles both directions of maximality. In particular, any strict measurable superset must represent an additional type because the original represented intervals are already included in full.
Semi-stable semantics. The critical strict-inclusion argument is valid. Conflict-freeness ensures that omitted occurrences of represented types are not already attacked. Hence saturation strictly enlarges the range whenever the admissible set is unsaturated, even if the omitted occurrences have measure zero.
The converse comparison with an arbitrary measurable competitor is also valid: from
\(\widehat{E^+}\subsetneq Q^+\subseteq\widehat{B^+}\),
strict inclusion of the outer saturated sets follows. Nonempty, disjoint intervals then give \(E^+\subsetneq B^+\). This verifies maximality against all measurable admissible competitors, as required.
Stable semantics. An omitted occurrence of a represented type is neither selected nor attacked, by conflict-freeness. Stability therefore forces saturation. For saturated conflict-free sets, covering the universe by the range is equivalent to \(E^+=T\).
No assumption that extensions are initially saturated is used improperly.
The corollary is correct for every listed semantics.
For admissible semantics, positive target measure implies target presence, and Lemma 1 supplies a finite admissible set containing the target. Conversely, saturating a finite admissible set containing the target gives target measure \(\mu_{t^\star}>0\).
For the other semantics, Lemma 2 supplies the exact correspondence directly. The proof does not claim that every admissible measurable extension is saturated; it only uses saturation to construct a suitable witness.
The three displayed identities for admissibility, defence, and range are correct.
The extension descriptions follow from those identities:
Once all isolated arguments are included where required, maximality and range comparisons reduce to the original framework. Credulous acceptance of the original target is therefore preserved.
The citation is accurate. Theorem 4(1) states the required hardness for all five semantics at deletion distance exactly one. The source defines bipartiteness as partitionability into two conflict-free sets, matching the task’s promise. Its definition of semi-stable semantics also uses range maximality among admissible sets. These checks validate the cited theorem’s applicability. [Ordyniak and Szeider, *Augmenting Tractable Fragments of Abstract Argumentation*](https://www.ijcai.org/Proceedings/11/Papers/177.pdf).
The reduction satisfies every input requirement:
The bound \(N\le2\max\{n,2^K\}=O_\varepsilon(n)\) is correct. Because \(K\) is fixed, the output size and construction time are polynomial in the source input length. The two established acceptance-preservation results give the required equivalence of yes-instances and no-instances.
The stated exhaustive-search bounds are valid. The finite admissibility, completeness, stability, and range checks can each be implemented in \(O(\tau^2)\) operations per subset.
The preferred-acceptance shortcut is justified by finiteness: every admissible set has an inclusion-maximal admissible superset. Pairwise range comparisons among the admissible subsets give the stated sufficient semi-stable bound.
Thus the bounds
\(O(2^\tau\tau^2+L^{O(1)})\) for admissible, complete, preferred, and stable acceptance, and
\(O(4^\tau\tau^2+L^{O(1)})\) for semi-stable acceptance, are consistent with the proof. They use the supported type count and total input length, with no separate candidate parameter.
The prover establishes hardness, without claiming completeness or unconditional exclusion from \(\mathrm{P}\). This resolves the classification requested by the task.
Repair feedback: None required.
⟨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.