Answer: polynomial-time solvable
Proposition 16 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven PSC(AF), the ideal extension Eid can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a common finite argument set \(A\) and a finite support \(T\), each type \(t\) supplies a framework \(AF_t=(A,R_t)\), a query \(q_t\), \(P_t=PSC(AF_t)\), and a positive binary-rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Compute exactly \(M=\sum_{t\in T}\mu_t\mathbf{1}[q_t\in E_{\mathrm{id}}(AF_t)]\).
Let \(A\) be a common finite argument set with \(m=|A|\geq 1\). A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types.
Each type \(t\in T\) explicitly supplies \(AF_t=(A,R_t)\), where \(R_t\subseteq A\times A\) may include self-attacks, a query \(q_t\in A\), a set \(P_t\subseteq A\), and a mass \(\mu_t\in\mathbb{Q}_{>0}\), with \(\sum_{t\in T}\mu_t=1\).
A set is admissible if it is conflict-free and defends every member: each attacker of a member is attacked by some member. Preferred extensions are inclusion-maximal admissible sets; \(E_{\mathrm{id}}(AF)\) is the unique inclusion-maximal admissible set contained in every preferred extension.
Define \(PSC(AF)=\{a\in A:\text{no admissible set attacks }a\}\), where a set attacks an argument if one of its members attacks that argument. The supplied sets are promised to satisfy \(P_t=PSC(AF_t)\); checking this promise is outside the task.
Compute exactly, as a reduced binary rational, \(M=\sum_{t\in T}\mu_t\mathbf{1}[q_t\in E_{\mathrm{id}}(AF_t)]\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is exact computation of \(M\) polynomial-time in \(m,\tau,L\), or is it NP-hard?
Known discrete result: given a framework and its preferred super-core, its ideal extension can be computed in polynomial time. No separate complexity classification for the distributional computation is assumed here.
1. Result. Exact computation of \(M\) is polynomial-time in \(m,\tau,L\). An explicit bit-complexity bound is \(O(\tau m^3+L^3)\).
We first give a direct algorithm for the ideal extension using the promised set \(PSC(AF)\), and then bound the cost of exact rational aggregation.
2. Characterizing admissible sets contained in every preferred extension.
Fix a framework \(AF=(A,R)\), and write \(P=PSC(AF)\). We claim that, for every admissible set \(H\),
\[
H\subseteq P
\quad\Longleftrightarrow\quad
H\text{ is contained in every preferred extension}.
\]
Here and below, a set attacks an argument when one of its members attacks that argument.
To prove the forward implication, suppose \(H\subseteq P\), and let \(E\) be a preferred extension. Since \(E\) is admissible, the definition of \(P\) implies that \(E\) does not attack any member of \(H\).
Furthermore, \(H\) cannot attack any member of \(E\). Indeed, if \(h\in H\) attacked \(e\in E\), admissibility of \(E\) would provide a member of \(E\) attacking \(h\), contradicting the preceding paragraph.
Thus there are no attacks between \(E\) and \(H\). Both sets are conflict-free, so their union is conflict-free. Each member of their union is defended by the admissible set to which it belongs. Consequently, \(E\cup H\) is admissible. Maximality of \(E\) now gives \(H\subseteq E\).
For the reverse implication, suppose \(H\) is contained in every preferred extension. If an admissible set \(K\) attacked some \(h\in H\), extend \(K\) to an inclusion-maximal admissible set \(E\). Such an extension exists because \(A\) is finite; it is a preferred extension. By hypothesis, \(h\in E\), while \(E\) also contains a member of \(K\) attacking \(h\). This contradicts conflict-freeness of \(E\). Hence no admissible set attacks any member of \(H\), proving \(H\subseteq P\).
It follows that the ideal extension is precisely the inclusion-maximal admissible set contained in \(P\). The next construction finds a greatest such set.
3. Computing the ideal extension by pruning.
Define
\[
U=\{a\in P:\text{there is no }b\in P\text{ with }(a,b)\in R\}.
\]
Every admissible set \(H\subseteq P\) is contained in \(U\): otherwise a member of \(H\) would attack an argument of \(P\), contradicting the defining property of \(P\).
Also, \(U\) is conflict-free. Indeed, no member of \(U\) attacks any argument of \(P\), and \(U\subseteq P\). This includes the exclusion of self-attacks.
Start with \(S_0=U\), and repeatedly set
\[
S_{i+1}
=
\{a\in S_i:
\text{for every }b\in A\text{ with }(b,a)\in R,
\text{ some }c\in S_i\text{ satisfies }(c,b)\in R\}.
\]
The sequence decreases. Every strict decrease removes at least one argument, so it reaches a fixed point \(S_*\) after at most \(m\) strict decreases.
We verify its two required properties.
Therefore \(S_*\) is the greatest admissible subset of \(P\). By Section 2, it is the ideal extension.
For the running time, use an adjacency matrix. Computing \(U\) takes \(O(m^2)\) time. In each pruning round, first mark every argument attacked by \(S_i\), then check the attackers of each argument in \(S_i\). Each of these operations takes \(O(m^2)\) time. There are at most \(m+1\) rounds, including the final equality check, giving \(O(m^3)\) time per type.
Applying this construction to each supplied \(P_t\) computes all indicators \(b_t=\mathbf{1}[q_t\in E_{\mathrm{id}}(AF_t)]\) in \(O(\tau m^3)\) time. The algorithm uses the promise and does not attempt to verify it.
4. Exact rational aggregation and bit complexity.
Write each supplied mass as \(\mu_t=n_t/d_t\), where \(n_t,d_t\) are positive integers encoded in binary. They need not already be relatively prime. Define \(D=\prod_{t\in T}d_t\) and \(N=\sum_{t\in T}b_t n_t(D/d_t)\). Each division \(D/d_t\) is exact, and \(M=N/D\).
The bit length of \(D\) is at most the sum of the bit lengths of the input denominators, hence is \(O(L)\). Moreover, positivity and normalization of the masses imply \(0\leq M\leq1\), so \(0\leq N\leq D\). Every partial sum forming \(N\) also lies between \(0\) and \(D\). Thus the aggregation involves only integers with \(O(L)\) bits.
Using schoolbook multiplication and long division, forming \(D\) and \(N\) takes \(O(\tau L^2)\) bit operations. Compute \(g=\gcd(N,D)\) and output the binary integers \(N/g\) and \(D/g\). For \(N=0\), this gives \(0/1\).
The Euclidean algorithm uses \(O(L)\) remainder steps: every two steps reduce the positive remainder by at least a factor of two. Each step costs \(O(L^2)\) with long division, giving the sufficient bound \(O(L^3)\) for reduction.
Since the support is explicitly listed, \(\tau\leq L\). Including input preprocessing, the total bit-complexity bound is therefore \(O(\tau m^3+L^3)\), and the reduced output has \(O(L)\) bits.
The computation visits only the \(\tau\) supplied types. No enumeration of other possible types is required.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The characterization of admissible subsets of \(PSC(AF)\), the pruning algorithm, and the exact rational aggregation are sound. The stated bound \(O(\tau m^3+L^3)\) is a valid polynomial upper bound. No major or minor mathematical issues were found.
The claimed equivalence is explicitly restricted to admissible sets \(H\), as required.
For the forward implication:
All hypotheses used here are present.
For the reverse implication:
The equivalence is correct. It identifies the same family of admissible candidates in the definition of the ideal extension.
The assertion that every admissible \(H\subseteq P\) lies in \(U\) is justified: if a member of \(H\) attacked any argument of \(P\), the admissible set \(H\) would itself contradict that argument’s membership in \(PSC(AF)\).
The conflict-freeness of \(U\) also follows directly. Every member of \(U\) has no outgoing attack to any member of \(P\), and \(U\subseteq P\). This excludes attacks between distinct members and self-attacks.
The initialization therefore preserves every admissible candidate while supplying a conflict-free set.
The update only removes members, so \(S_{i+1}\subseteq S_i\). There can be at most \(m\) strict decreases. Including the test establishing stabilization, the bound of \(m+1\) rounds is valid.
At stabilization:
The induction proving greatestness is valid:
Consequently, \(S_*\) contains every admissible subset of \(P\). Combined with its own admissibility and the equivalence from Section 2, this identifies \(S_*\) as the ideal extension.
The argument also covers \(P=\varnothing\), \(U=\varnothing\), unattacked arguments, and frameworks containing self-attacks.
With an adjacency matrix:
Together with at most \(m+1\) rounds, this gives \(O(m^3)\) per type and \(O(\tau m^3)\) across the explicitly listed support. Input parsing and matrix preparation fit within the stated total bound.
The promise \(P_t=PSC(AF_t)\) is used exactly where needed. The algorithm does not assume that checking this promise is part of the task.
The formula \(M=N/D\) is correct because each \(d_t\) divides the product \(D\). It does not require the input fractions to be reduced.
The product \(D\) has at most the sum of the denominator bit lengths, so its size is \(O(L)\). Positivity and normalization give \(0\leq N\leq D\). Each summand and each partial sum are nonnegative and bounded by \(D\), so the numerator computation also stays within \(O(L)\)-bit integers.
There are \(O(\tau)\) multiplications, exact divisions, and additions. The stated schoolbook bound \(O(\tau L^2)\) is therefore sufficient.
The Euclidean-algorithm bound is valid: positive remainders decrease by at least a factor of two over every two steps, giving \(O(L)\) steps. Charging \(O(L^2)\) per division yields the claimed sufficient bound \(O(L^3)\).
Dividing by \(\gcd(N,D)\) produces a reduced fraction. The case \(N=0\) correctly produces \(0/1\); the case \(N=D\) produces \(1/1\).
Finally, explicit support encoding ensures \(\tau\leq L\), so the aggregation cost is absorbed by \(O(L^3)\). The reduced output has \(O(L)\) bits.
None. The proof establishes polynomial-time exact computation under the specified explicit-support representation and supplied-set promise.
⟨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.