Answer: Polynomial-time solvable.
Corollary 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf E is acyclic and F is ballot-monotonic and polynomial to compute then the opinion profile B∗at convergence of POD can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a DAG \(D=(R,A)\) and rational masses \(\mu_{r,b}\ge 0\) for roles \(r\in R\) and initial opinions \(b\in\{0,1\}\), with \(\sum_{r,b}\mu_{r,b}=1\), each member of role \(r\) is influenced by every member of each predecessor role \(u\) with \((u,r)\in A\). Starting from \(x_r^0=\mu_{r,1}\), let \(q_r=\mu_{r,0}+\mu_{r,1}\); at each step, role \(r\) adopts opinion \(1\) if predecessor opinion-1 mass is a strict majority, adopts \(0\) if it is a strict minority, and retains its current opinion mass on a tie. Compute the exact terminal opinion masses \(x_r^*\) and \(q_r-x_r^*\) for all roles.
Consider one unconstrained binary issue, so \(m=1\), and an explicitly given DAG \(D=(R,A)\), without self-loops. Types are pairs \((r,b)\in R\times\{0,1\}\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Unlisted types have mass zero, and \(\sum_{r,b}\mu_{r,b}=1\).
Set \(q_r=\mu_{r,0}+\mu_{r,1}\) and \(x_r^0=\mu_{r,1}\). Every member of role \(r\) is influenced by every member of each predecessor role, with influence measured by mass.
Updates are synchronous: let \(S_r^t=\sum_{(u,r)\in A}x_u^t\) and \(Q_r=\sum_{(u,r)\in A}q_u\). Set \(x_r^{t+1}=q_r\) if \(2S_r^t>Q_r\), set \(x_r^{t+1}=0\) if \(2S_r^t<Q_r\), and set \(x_r^{t+1}=x_r^t\) otherwise. Thus roles with no positive-mass influencers retain their current masses.
The required output is the exact eventual constant profile \((x_r^*,q_r-x_r^*)_{r\in R}\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L,|R|,|A|\).
Is exact computation of this terminal mass profile polynomial-time solvable, or is it NP-hard?
Known discrete result: finite-agent acyclic opinion diffusion has polynomial-time terminal-profile computation when aggregation is polynomial-time computable and invariant under replacing any input ballot by the aggregation output. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p989.pdf).
No result settling this exact support-encoded mass problem was identified in the literature search.
Exact computation is polynomial-time solvable. For \(m=1\), the process stabilizes after at most \(\min\{\tau,|R|\}-1\) synchronous rounds. Exact simulation has polynomial bit complexity, even when the masses have large binary-encoded denominators.
Let \(V=\{r\in R:q_r>0\}\), let \(k=|V|\), and let \(A_+=A\cap(V\times V)\). Since the total mass is \(1\), we have \(k\geq 1\). Each role in \(V\) accounts for at least one supported type, so \(k\leq\min\{\tau,|R|\}\).
First, \(0\leq x_r^t\leq q_r\) for every role and every time. This holds initially because \(x_r^0=\mu_{r,1}\leq q_r\), and each update either preserves the current value or replaces it by \(0\) or \(q_r\).
Consequently, if \(q_r=0\), then \(x_r^t=0\) at all times. Such a role contributes zero to every successor’s influence sums. Therefore the dynamics on \(V\) are exactly the dynamics on the induced DAG \(H=(V,A_+)\); every omitted role has terminal output \((0,0)\).
For \(r\in V\), define \(d(r)\) to be the maximum number of edges in a directed path of \(H\) ending at \(r\). A source has depth \(0\). Since \(H\) is a DAG on \(k\) vertices, \(d(r)\leq k-1\).
Lemma. For every \(r\in V\), \(x_r^t=x_r^{d(r)}\) for all \(t\geq d(r)\).
Proof. We use induction on depth.
If \(d(r)=0\), all predecessors of \(r\) in the original graph have zero mass. Hence \(S_r^t=Q_r=0\) at every time. Every update is a tie, so \(x_r^t=x_r^0\).
Now suppose \(d(r)=d>0\), and assume the assertion holds for every role of smaller depth. Each positive-mass predecessor \(u\) of \(r\) has \(d(u)\leq d-1\). Thus all predecessors’ values are constant from time \(d-1\) onward, and \(S_r^t\) has some constant value \(S\) for every \(t\geq d-1\).
There are three cases:
This completes the induction. \(\square\)
Therefore the entire profile is constant from time \(k-1\) onward. The proof explicitly accommodates persistent ties: they preserve the value reached during the preceding transient.
Write each listed positive mass as \(a_j/b_j\), where \(a_j,b_j\) are positive binary-encoded integers, for \(1\leq j\leq\tau\). This also covers dyadic masses.
Choose the common denominator \(P=\prod_{j=1}^{\tau}b_j\), and form the integer weights \(w_j=a_j(P/b_j)\). For each role, compute \(C_r=Pq_r\) and initialize \(Y_r^0=Px_r^0\) by summing the corresponding weights.
For each active role, precompute \(T_r=\sum_{(u,r)\in A_+}C_u\). Then perform exactly \(k-1\) synchronous rounds:
Dividing these integer comparisons by the positive number \(P\) gives precisely the prescribed update rule. Induction on time therefore proves \(Y_r^t=Px_r^t\).
Output \((Y_r^{k-1}/P,(C_r-Y_r^{k-1})/P)\) for each active role, and \((0,0)\) for each inactive role. By the stabilization lemma, this is the exact eventual constant profile. Fractions may optionally be reduced.
Let \(n=|R|\), \(a=|A|\), and \(a_+=|A_+|\).
The denominator does not cause exponential bit growth. Indeed, \(\log_2 P=\sum_j\log_2 b_j=O(L)\). Moreover, normalization gives \(\sum_r C_r=P\), while \(0\leq Y_r^t\leq C_r\). Since every predecessor set is a subset of the roles, \(T_r\leq P\) and \(Z_r^t\leq P\). Thus every integer used in the simulation has \(O(L)\) bits.
Common-denominator preprocessing takes \(O(\tau L^2)\) bit operations using elementary multiplication and division. Each round takes \(O(k+a_+)\) additions and comparisons on \(O(L)\)-bit integers. Writing the output, including optional fraction reduction, also takes polynomial time.
A conservative overall bit-operation bound is
\(O\bigl((n+a+\tau+k(k+a_+))L^2\bigr)\).
Using \(k\leq\min\{\tau,n\}\) and \(a_+\leq a\), this becomes
\(O\bigl((|R|+|A|+\tau+\min\{\tau,|R|\}(\min\{\tau,|R|\}+|A|))L^2\bigr)\).
This bound applies to the requested case \(m=1\) and uses the support size \(\tau\), without expanding masses into a population of individual agents.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: exact terminal-profile computation is polynomial-time solvable for \(m=1\). The stabilization argument handles ties, and the integer simulation has polynomial bit complexity. No major or minor issues were found.
The invariant \(0\leq x_r^t\leq q_r\) is justified by the initial conditions and each of the three update cases.
Consequently, \(q_r=0\) implies \(x_r^t=0\) at every time. Removing such a role removes only zero contributions from both the opinion sum and the total influencer mass. Thus the induced dynamics on \(V\) agree exactly with the original dynamics restricted to \(V\).
Normalization ensures \(k\geq1\). Each active role requires at least one listed positive-mass type, so \(k\leq\min\{\tau,|R|\}\). These claims correctly use support size rather than the number of possible types.
Assessment: Correct and complete.
The depth definition is valid because the induced graph \(H\) is a DAG. Every positive-mass predecessor of a role of depth \(d\) has depth at most \(d-1\).
The induction establishes precisely the claimed time bound:
There is no off-by-one error: a comparison using predecessor values at time \(d-1\) determines the role’s value at time \(d\).
Since every depth is at most \(k-1\), the whole profile is constant from time \(k-1\). The case \(k=1\) is covered: the sole active role has no positive-mass predecessor and requires zero simulation rounds.
Assessment: Correct and complete, including persistent ties and the smallest admissible support.
The common denominator \(P\) is positive and divisible by every listed denominator. Hence every weight \(w_j\), role mass \(C_r\), and initial opinion mass \(Y_r^0\) is an integer.
The scaled comparison is exact: \(Z_r^t=PS_r^t\) and \(T_r=PQ_r\), so multiplying by \(P>0\) preserves strict inequalities and equality. The three integer updates therefore implement the prescribed rational updates exactly.
Using separate current and next arrays correctly preserves synchronous semantics. Performing \(k-1\) rounds is sufficient by the proved stabilization bound.
The output fractions have the required numerators and denominator. Inactive roles correctly receive \((0,0)\). Reduction is optional because unreduced fractions still represent the exact requested masses.
Assessment: Correct and complete.
The denominator bound is valid: the bit length of a product is at most the sum of the factors’ bit lengths, up to a constant. Those denominator encodings are included in \(L\), so \(P\) has \(O(L)\) bits.
Normalization gives \(\sum_r C_r=P\). The invariant gives \(0\leq Y_r^t\leq C_r\). A predecessor set contains distinct roles, so both \(T_r\) and \(Z_r^t\) are at most \(P\). The comparison value \(2Z_r^t\) needs at most one additional bit. Thus all simulation arithmetic uses \(O(L)\)-bit integers.
The preprocessing estimate \(O(\tau L^2)\) is valid with elementary integer multiplication and division. Each round uses \(O(k+a_+)\) additions and comparisons, and there are \(k-1\) rounds. Writing the explicitly requested profile for all roles is polynomial; optional fraction reduction is also polynomial.
The stated overall bound
\[
O\bigl((n+a+\tau+k(k+a_+))L^2\bigr)
\]
is conservative and sufficient. Substituting \(k\leq\min\{\tau,n\}\) and \(a_+\leq a\) yields the displayed bound in the requested parameters. The restriction to \(m=1\) is stated explicitly; no result for variable \(m\) is claimed.
Assessment: Correct. Large denominator values do not invalidate the polynomial bit-complexity bound.
The proof establishes both eventual constancy and exact polynomial-time computation for the specified support encoding. It does not rely on the cited discrete theorem, so no theorem application or external hypothesis remains to be checked.
No additional clarification or 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.