Answer: \(\mathrm{NP}\)-complete
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a society graph G and a preferred can- didate p, deciding whether there is an order of asynchronous diffusion steps which results in p being a Plurality winner in the converged election is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), voter types \(T\) with complete rankings \(\rho_t\), a society graph \(G=(T,E)\), a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), and target \(p\), repeatedly select a type \(t\) and, whenever a neighbor \(u\) satisfies \(\mu_u>\frac{1}{2}\sum_{z\in N[t]}\mu_z\), move all mass \(\mu_t\) to \(u\); decide whether some legal update order reaches a stabilized distribution \(\bar{\mu}\) in which \(p\) is a Plurality winner.
Given \(m\geq 2\) candidates \(C\) and a target \(p\in C\), a society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings \(\rho_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
The society graph \(G=(T,E)\) is simple and undirected, with an edge exactly when the two rankings differ by one adjacent swap. Its vertices, edges, and rankings remain fixed throughout diffusion, including vertices whose mass becomes zero. Write \(N(t)\) for the open neighborhood and \(N[t]=N(t)\cup\{t\}\).
Starting from \(x=\mu\), an asynchronous update selects \(t\). If some \(u\in N(t)\) satisfies \(x_u>\tfrac12\sum_{z\in N[t]}x_z\), simultaneously replace \(x_u\) by \(x_u+x_t\) and \(x_t\) by zero; otherwise nothing changes. Mass cannot be split.
A distribution is stabilized when every update leaves it unchanged. The decision problem asks whether some finite legal update sequence reaches a stabilized distribution in which \(p\) is a Plurality winner, with ties accepted and votes weighted by mass.
Is this decision problem solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For integer voter counts, choosing an asynchronous update order that makes the target a Plurality winner is \(\mathrm{NP}\)-hard; the corrected full version strengthens this to strong \(\mathrm{NP}\)-hardness ([verified result](https://arxiv.org/pdf/2010.00651)).
No result explicitly addressing the normalized binary-rational mass formulation was identified in the search.
The problem is \(\mathrm{NP}\)-complete. Normalizing integer voter counts preserves the entire diffusion process, including stabilization and Plurality ties.
Here “binary-rational” may mean rational numbers whose numerators and denominators are encoded in binary. The conclusion also holds if masses are required to be dyadic rationals; this restriction is addressed below.
For a fixed society graph, let \(U_t(x)\) denote the distribution obtained by selecting vertex \(t\).
First, the absorbing neighbor, when one exists, is unique. Indeed, write \(S=\sum_{z\in N[t]}x_z\). If two distinct neighbors \(u,v\) both satisfied the strict-majority condition, then \(x_u+x_v>S\), contradicting \(x_u+x_v\leq S\).
For every positive scalar \(\alpha\), we have
\(U_t(\alpha x)=\alpha U_t(x)\).
To verify this, observe that
\[
\]
\(x_u>\frac12\sum_{z\in N[t]}x_z\)
holds exactly when
\(\alpha x_u>\frac12\sum_{z\in N[t]}\alpha x_z\).
Thus scaling preserves whether an absorbing neighbor exists and its identity. If absorption occurs, the new recipient mass is \(\alpha x_u+\alpha x_t=\alpha(x_u+x_t)\); all other coordinates also agree with the scaled update.
Induction on the length of an update sequence therefore proves that executing the same sequence from \(x\) and \(\alpha x\) produces distributions related by the factor \(\alpha\) at every step.
Two consequences follow:
We use the established integer-count hardness theorem: deciding whether some asynchronous diffusion order makes the target a Plurality winner in the converged election is strongly \(\mathrm{NP}\)-hard. Its corrected construction uses distinct supported rankings with positive integer weights and the graph induced by adjacent swaps. The underlying definitions use the same strict closed-neighborhood majority rule and accept tied winners. Thus this theorem concerns the integer version of the present problem, rather than diffusion on an arbitrary graph. See [Sections 3–4 and Theorem 1 of the corrected full paper](https://arxiv.org/pdf/2010.00651).
Take an instance from that hard family, with integer weights \(w_t>0\). Define
\(W=\sum_{t\in T}w_t\)
and
\(\mu_t=w_t/W\).
Keep all candidates, rankings, vertices, and edges unchanged.
These masses are positive and satisfy \(\sum_t\mu_t=1\). By Section 1, every update sequence from \(w\) corresponds exactly to the same sequence from \(\mu\), with every intermediate distribution divided by \(W\). In particular, the integer instance admits a stabilized distribution where \(p\) wins if and only if the normalized instance does.
The transformation has polynomial encoding length. If \(b\) is the maximum binary length of an input weight, then \(W<\tau 2^b\), so its binary length is at most \(b+\lceil\log_2\tau\rceil+1\). Each output fraction \(w_t/W\) consequently has polynomial length, and all fractions can be computed in polynomial time. Reducing fractions, if required by the encoding, also takes polynomial time.
This is a polynomial many-one reduction and proves \(\mathrm{NP}\)-hardness.
A changing update must have a positive source mass. Its recipient has positive mass as well, because it satisfies a strict-majority inequality over nonnegative masses.
Consequently, every changing update decreases the number of positive-mass vertices by exactly one: the source becomes zero, and the already-positive recipient remains positive. Furthermore, a zero-mass vertex can never receive mass, since it cannot satisfy the strict-majority condition.
Starting with \(\tau\) positive vertices, there can therefore be at most \(\tau-1\) changing updates. Any updates that leave the distribution unchanged can be deleted from a sequence without altering subsequent states. Hence every successful instance has a certificate consisting of at most \(\tau-1\) selected vertices.
We can verify this certificate using exact polynomial-time arithmetic. Write each initial mass as \(\mu_t=a_t/b_t\), with positive binary-encoded integers \(a_t,b_t\), and set
\(D=\prod_{t\in T}b_t\)
and
\(A_t=a_t(D/b_t)\).
The binary length of \(D\) is at most the sum of the denominator lengths, hence is \(O(L)\). Since the masses sum to one, \(\sum_t A_t=D\).
Simulate diffusion on these integer weights. At every stage the weights are nonnegative integers summing to \(D\), so every weight has \(O(L)\) bits. A majority test is simply
\(2A_u>\sum_{z\in N[t]}A_z\).
After simulating the certificate, check stabilization explicitly: for every vertex \(t\) with \(A_t>0\) and every \(u\in N(t)\), require
\(2A_u\leq\sum_{z\in N[t]}A_z\).
Updates at zero-mass vertices already leave the distribution unchanged. Finally, compute all Plurality scores and check that the target’s score is at least every other score.
The graph itself can be computed by comparing every pair of listed rankings for a single adjacent swap, in polynomial time in \(m,\tau,L\). Thus certificate verification is polynomial, proving membership in \(\mathrm{NP}\).
A direct normalization by \(W\) need not be dyadic. Nevertheless, hardness still follows from the strong integer-count theorem.
Use its hard family, whose total integer weight \(W\) is polynomially bounded in the source-instance length. Let \(Q\) be the smallest power of two satisfying \(Q\geq W\), and put \(h=Q-W\). Add \(h\) new candidates \(d_1,\ldots,d_h\) and \(h\) isolated ranking vertices, each of integer weight one.
Here is an explicit realization of the required graph. Append the common suffix \(d_1,\ldots,d_h\) to every original ranking. Fix two distinct original candidates \(a,b\). Give new vertex \(i\) the ranking beginning \(d_i,a,b\), followed by all remaining candidates in any fixed order.
These new vertices are isolated:
Appending a common suffix preserves exactly the original adjacent-swap edges. It also preserves the original first candidates and therefore their scores. Each new candidate has the constant integer score one.
At any stabilized original distribution, an original winner has positive integer score, hence score at least one. Thus, if \(p\) originally wins, it still wins after adding the new candidates, with ties accepted. Conversely, winning against the enlarged candidate set implies winning against the original candidates. Isolation ensures that the added vertices do not affect diffusion or stabilization.
The augmented total weight is \(Q\). Dividing all weights by \(Q\) now gives positive dyadic masses summing to one. Because \(Q<2W\) and \(W\) is polynomially bounded, the number of added candidates and rankings, and their explicit encodings, are polynomially bounded.
Therefore the dyadic restriction is also \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes $\mathrm{NP}$-completeness for normalized binary-encoded rational masses, including the restriction to dyadic masses. I found no mathematical gaps requiring correction.
The uniqueness argument is correct. For a nonnegative state $x$, the closed-neighborhood sum $S$ includes both distinct neighbors $u,v$. Consequently, $x_u+x_v\leq S$, whereas two strict majorities would imply $x_u+x_v>S$.
For every $\alpha>0$, multiplication by $\alpha$ preserves each strict-majority comparison. It therefore preserves both the existence and identity of the absorbing neighbor. The coordinate update also commutes with scaling, proving
$$
U_t(\alpha x)=\alpha U_t(x).
$$
This includes zero-mass sources and updates that change nothing.
Induction correctly extends this identity to every finite update sequence. The stated consequences for stabilization and Plurality comparisons follow directly. In particular, strict inequalities remain strict, and score ties remain ties.
Assessment: Correct.
The external theorem is applicable. The paper’s Sections 3.1–3.3 define tied winners, vertices corresponding to supported rankings, adjacent-swap edges, and the same strict closed-neighborhood absorption rule. Section 4 defines convergence through the absence of nonredundant updates. Theorem 1 concerns choosing an asynchronous order that makes the target a Plurality winner in the converged election. Its correction footnote explicitly states that the revised construction realizes the required graph and uses polynomially bounded weights. These match the hypotheses asserted by the prover. [Corrected full paper, Sections 3–4 and Theorem 1](https://arxiv.org/pdf/2010.00651).
The normalization $\mu_t=w_t/W$ preserves positivity and makes the total mass one. Because the graph and rankings remain unchanged, scaling invariance gives the claimed equivalence in both directions, including the final stabilization requirement.
The encoding estimate is valid: if each weight has at most $b$ bits, then $W<\tau 2^b$. Thus each numerator and denominator has polynomial bit length. Integer summation, fraction construction, and optional reduction to lowest terms take polynomial time.
Assessment: Correct polynomial many-one reduction.
Every changing update has a positive source. Its recipient must already be positive, since a zero coordinate cannot exceed half a nonnegative neighborhood sum. Thus exactly one positive coordinate disappears in each changing update.
A zero-mass vertex cannot subsequently receive mass. Starting with $\tau$ positive coordinates, at most $\tau-1$ changing updates are possible. Removing unchanged updates preserves all subsequent states because updates depend only on the current state and selected vertex. Therefore every successful sequence yields a certificate of the stated length. The case $\tau=1$ is covered by an empty certificate.
The common-denominator construction is exact:
$$
D=\prod_t b_t,\qquad A_t=a_t(D/b_t),\qquad \sum_t A_t=D.
$$
The product has $O(L)$ bits. During simulation, each coordinate lies between zero and $D$, so arithmetic remains polynomial in the input length. The integer majority test is precisely the original test after positive scaling.
The final stabilization check is necessary and sufficient. At a positive source, any qualifying neighbor would produce a change; at a zero source, every update leaves the state unchanged. The Plurality check correctly accepts ties.
Pairwise testing of explicitly listed rankings for a single adjacent swap also takes polynomial time.
Assessment: Correct $\mathrm{NP}$ membership proof.
The prover correctly recognizes that direct normalization need not produce dyadic fractions.
Its padding construction preserves the original induced graph. Appending the same suffix preserves adjacent swaps among original candidates; a swap involving the suffix cannot transform one extended original ranking into another.
The isolation arguments are valid in both directions because adjacency is undirected:
The new rankings are distinct from each other and from all extended original rankings. The assumption $m\geq2$ supplies the required distinct candidates $a,b$.
Each added candidate has constant integer score one. An original winning target has positive integer score and hence score at least one, so padding preserves its winning status with ties accepted. Conversely, winning in the enlarged election implies winning against every original candidate. Isolation also preserves the correspondence between stabilized states.
Polynomially bounded weights and polynomially many vertices in the cited hard family imply polynomially bounded total weight $W$. Hence $h=Q-W<W$ gives polynomially many added candidates and rankings. Their explicit encodings remain polynomial in size.
Normalization by the power of two $Q$ produces dyadic masses. The case $h=0$ needs no added vertices and is already covered.
Assessment: Correct dyadic hardness proof. Section 3 supplies membership in $\mathrm{NP}$ for this restriction as well.
The output resolves the assigned question and supports its stronger $\mathrm{NP}$-completeness claim. No additional mathematical clarification 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.