Answer: Exact computation is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions for both \(C=\mathrm{ODDFREE}\) and \(C=\mathrm{EVENFREE}\text{-}4\), already for \(\tau=1\) and also for \(\tau=2\) with equal masses.
Proposition 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSkeptical acceptance for preferred seman- tics is ΠP 2-hard even for AFs F with btwC(F) = 0 for C ∈{ODDFREE, EVENFREE-4}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(C \in \{\text{ODDFREE},\text{EVENFREE-4}\}\). Given a finite support of types \((F_i,a_i)\), each with \(\operatorname{btw}_C(F_i)=0\), and positive binary-rational masses \(\mu_i\) summing to \(1\), compute exactly \(Q=\sum_i \mu_i\,\mathbf{1}[a_i\text{ belongs to every preferred extension of }F_i]\).
Fix \(C\in\{\mathrm{ODDFREE},\mathrm{EVENFREE}\text{-}4\}\). An argumentation framework is \(F=(A,R)\), with \(A\) finite and nonempty and \(R\subseteq A\times A\); self-attacks are allowed. Use standard Dung preferred semantics, denoted \(\operatorname{pref}(F)\).
The class \(\mathrm{ODDFREE}\) excludes directed simple cycles of odd length, including self-loops; \(\mathrm{EVENFREE}\text{-}4\) excludes directed simple cycles of even length at least \(4\).
A \(C\)-backdoor is a set \(S\subseteq A\) such that the induced framework \(F-S\) lies in \(C\). Let \(U_F\) be the underlying simple undirected graph. The torso \(G_F^S\) has vertex set \(S\), with distinct vertices adjacent if adjacent in \(U_F\) or both adjacent to the same connected component of \(U_F-S\).
Define \(\operatorname{btw}_C(F)=\min_{S:\,F-S\in C}\operatorname{tw}(G_F^S)\), using \(\operatorname{tw}(\varnothing)=-1\).
A society is given by its support: a list of \(\tau\) distinct types \((F_i,a_i)\), with \(a_i\in A_i\), each having positive binary-rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
Frameworks are explicitly encoded, and every type is promised to satisfy \(\operatorname{btw}_C(F_i)=0\); no backdoor is supplied. Set \(m=\max_i|A_i|\), and let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
Compute exactly the rational \(Q=\sum_{i=1}^{\tau}\mu_i\mathbf{1}[\forall E\in\operatorname{pref}(F_i),\ a_i\in E]\).
Is exact computation of \(Q\) polynomial-time solvable in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, for each fixed choice of \(C\)?
For a single framework satisfying \(\operatorname{btw}_C(F)=0\), skeptical preferred acceptance is \(\Pi_2^{\mathrm P}\)-hard for both choices of \(C\). [Source](https://cdn.aaai.org/ojs/20501/20501-13-24514-1-2-20220628.pdf)
No result specifically addressing this explicitly supported, mass-weighted computation was located.
For each fixed \(C\in\{\mathrm{ODDFREE},\mathrm{EVENFREE}\text{-}4\}\), exact computation of \(Q\) is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. Hardness already holds for \(\tau=1\), and also holds for \(\tau=2\) with two distinct types of mass \(1/2\).
Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Write \(b(F,a)=1\) when every preferred extension of \(F\) contains \(a\), and write \(b(F,a)=0\) otherwise.
Recall that \(E\subseteq A\) is admissible if it is conflict-free and defends every member: for every \(x\in E\) and every attacker \(y\) of \(x\), some member of \(E\) attacks \(y\). A preferred extension is an inclusion-maximal admissible set. Because \(A\) is finite and the empty set is admissible, preferred extensions exist.
Proposition 4 of the cited paper states that deciding \(b(F,a)\) is \(\Pi_2^{\mathrm P}\)-hard even when \(\operatorname{btw}_C(F)=0\), for each of the two classes in the question. Its torso and backdoor definitions agree with those here. Its proof uses frameworks outside \(C\) having a one-argument \(C\)-backdoor; that backdoor has a singleton torso of treewidth \(0\). Thus the convention \(\operatorname{tw}(\varnothing)=-1\) does not invalidate the exact-zero promise. [Proposition 4, *Tractable Abstract Argumentation via Backdoor-Treewidth*](https://cdn.aaai.org/ojs/20501/20501-13-24514-1-2-20220628.pdf)
We use this supplied hardness theorem; the transfer to weighted computation is proved below.
Fix either class \(C\). Given a promised single-framework instance \((F,a)\), construct the society consisting solely of type \((F,a)\), with mass \(\mu_1=1\).
This is a valid input:
The resulting value is exactly \(Q=b(F,a)\). Therefore, one call to an exact-\(Q\) oracle decides skeptical preferred acceptance by testing whether its output equals \(1\).
The transformation takes time linear in the input encoding length. It has \(\tau=1\), \(m=|A|\), and total length \(L\) linear in the single-framework input length.
For completeness, the given \(\Pi_2^{\mathrm P}\)-hardness implies the requested \(\mathrm{NP}\)-hardness: \(\mathrm{NP}\subseteq\Pi_2^{\mathrm P}\), since an existential polynomial-time certificate condition can be preceded by an unused universal quantifier. Composing the single-framework hardness reduction with the construction above gives a polynomial-time Turing reduction from every language in \(\mathrm{NP}\) to exact computation of \(Q\).
This settles the classification. The singleton support is an allowed restriction of the intended problem, rather than a change to its interpretation.
To show that the conclusion survives a non-singleton support, let \(F^+\) be obtained from \(F\) by adding one fresh, unattacked argument \(z\), with no incident attacks.
First, \(\operatorname{pref}(F^+)=\{E\cup\{z\}:E\in\operatorname{pref}(F)\}\). Indeed, adjoining \(z\) preserves admissibility, so every maximal admissible set of \(F^+\) contains \(z\). Removing \(z\) preserves admissibility as well. A proper admissible enlargement on either side would give a proper admissible enlargement on the other side, establishing the claimed correspondence. Hence \(b(F^+,a)=b(F,a)\).
Second, \(\operatorname{btw}_C(F^+)=0\). Choose a \(C\)-backdoor \(S\) of \(F\) whose torso has treewidth \(0\). Adding an isolated argument creates no directed cycles, so \(F^+-S\in C\), and the torso on \(S\) is unchanged. Thus \(\operatorname{btw}_C(F^+)\leq0\).
To obtain equality, the original promise implies \(F\notin C\): otherwise the empty backdoor would give value \(-1\). The forbidden cycle in \(F\) remains in \(F^+\), so \(F^+\notin C\). Its backdoors are therefore nonempty, and their torsos have nonnegative treewidth. This proves equality.
Now use the two types \((F,a)\) and \((F^+,a)\), each of mass \(1/2\). They are distinct because their frameworks have different numbers of arguments. Their weighted value is \(Q=(b(F,a)+b(F^+,a))/2=b(F,a)\).
This again gives a one-call reduction, now with \(\tau=2\), \(m=|A|+1\), and \(L\) polynomial in the original input length.
An exact algorithm can compute each bit \(b_i=b(F_i,a_i)\) and then sum the corresponding masses. The arithmetic introduces only polynomial overhead.
Specifically, write each input mass as \(\mu_i=p_i/d_i\), with positive integers encoded in binary. Let \(D=\prod_i d_i\). Then \(Q=N/D\), where \(N=\sum_i b_i p_i(D/d_i)\).
The bit length of \(D\) is at most the sum of the denominator bit lengths, hence is \(O(L)\). Moreover, \(0\leq N\leq D\), because the masses sum to \(1\). Products, exact divisions, summation, and reduction by a greatest common divisor therefore take polynomial time in \(\tau,L\); a conservative bound is \(O(\tau L^3)\) bit operations. The exact output has \(O(L)\) bits.
A direct algorithm for the acceptance bits is also available. For a framework with \(n\leq m\) arguments:
Each admissibility test uses polynomial time in \(n\). Thus this gives exact computation in time \(O(\tau\,3^m\operatorname{poly}(m)+\tau L^3)\), without finding or verifying backdoors.
The polynomial arithmetic overhead cannot remove the hardness: even at constant support size, exact \(Q\) reveals the hard acceptance bit.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly for both fixed choices of \(C\). The singleton-support reduction establishes the requested \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions. The additional two-type reduction and exponential-time algorithm are also correct. No major or minor mathematical issues were found.
The definition of admissibility correctly includes both conflict-freeness and defense against every attacker. It applies when self-attacks are allowed: an argument attacking itself cannot belong to a conflict-free set.
Preferred extensions are correctly defined as inclusion-maximal admissible sets. Since the empty set is admissible and the framework is finite, at least one such maximal set exists. Thus the universal quantifier defining \(b(F,a)\) does not rely on an empty family of preferred extensions.
Assessment: Correct.
[Proposition 4 of the cited paper](https://cdn.aaai.org/ojs/20501/20501-13-24514-1-2-20220628.pdf) states precisely the required skeptical preferred acceptance hardness for both classes at backdoor-treewidth zero. Its backdoor and torso definitions match those used in the task.
The paper’s proof explicitly asserts backdoor size one for its reduction frameworks, for both classes. This supports the prover’s treatment of the empty-graph convention: these frameworks lie outside \(C\), so an empty backdoor is unavailable, while the exhibited singleton backdoor has torso treewidth zero. The exact-zero promise therefore survives the convention \(\operatorname{tw}(\varnothing)=-1\).
The theorem concerns explicitly presented frameworks and does not require a supplied backdoor. Its hypotheses match the instances used here.
Assessment: Correct and adequately cited. Re-proving the supplied hardness theorem is unnecessary.
The constructed society satisfies every input restriction:
The identity \(Q=b(F,a)\) follows directly from the definition of the weighted sum. Comparing the exact oracle output with one decides skeptical preferred acceptance.
The construction has linear encoding overhead and fixes \(\tau=1\). Because frameworks are explicitly encoded, \(m\) is bounded by the input length. Consequently, a runtime polynomial in \(m,\tau,L\) would give a polynomial-time algorithm for the source problem.
The inclusion \(\mathrm{NP}\subseteq\Pi_2^{\mathrm P}\) is correctly justified by an unused initial universal quantifier. Composing the source hardness reduction with the one-call oracle construction yields the requested polynomial-time Turing hardness.
Assessment: Correct. This section alone settles the target classification.
The preferred-extension correspondence under addition of an isolated argument is valid. Every maximal admissible set contains \(z\), because adjoining \(z\) preserves admissibility. Removing \(z\) also preserves admissibility, and proper admissible enlargements correspond in both directions. Hence the acceptance bit for the original queried argument is preserved.
The backdoor-treewidth argument establishes both required inequalities:
Thus \(\operatorname{btw}_C(F^+)=0\). The types are distinct even if framework identity were interpreted up to isomorphism, because their argument counts differ. Equal masses yield the asserted identity \(Q=b(F,a)\).
Assessment: Correct. The additional restriction to two distinct types is genuinely established.
The common-denominator construction is valid. Its denominator has bit length at most the sum of the input denominator bit lengths, up to an immaterial additive constant, hence \(O(L)\).
The mass normalization and positivity give \(0\leq N\leq D\). Intermediate products and partial sums also have polynomially bounded bit lengths. Exact division, summation, multiplication, and greatest-common-divisor reduction therefore require polynomial arithmetic overhead. The stated conservative bound \(O(\tau L^3)\) is valid with standard binary integer arithmetic.
The output-size claim of \(O(L)\) bits is also correct.
Assessment: Correct.
Enumerating all subsets and recording admissibility is sufficient. Marking an admissible set whenever it has an admissible proper superset correctly distinguishes inclusion-maximal admissible sets.
The pair count is correct: the number of pairs satisfying \(E\subsetneq T\) is \(3^n-2^n\), which is fewer than \(3^n\). Admissibility tests and subset bookkeeping take polynomial time per relevant operation.
The resulting bound
\[
O(\tau\,3^m\operatorname{poly}(m)+\tau L^3)
\]
is a valid exponential upper bound. The algorithm does not need to find or verify backdoors, which is appropriate for the promised input problem.
Assessment: Correct.
There are no unjustified substantive steps, false statements, missing hypotheses, or unresolved edge cases. No additional clarification is needed to make the argument verifiable. The hardness conclusion is conditional only in the usual sense: it excludes a polynomial-time algorithm unless \(\mathrm P=\mathrm{NP}\).
⟨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.