Answer: Polynomial-time solvable: \(p_R(\mu)=0\) when \(r+b=0\), and \(p_R(\mu)=r/(r+b)\) otherwise, using binary numerator–denominator encoding.
Corollary 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet 𝐺 be a complete graph and consider the asynchronous (pull) voter model with agnostic states, with initial state 𝑆0. Let 𝛾 denote the proportion of red nodes among the gnostic ones.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(r,b,a\ge 0\) with \(r+b+a=1\), define the asynchronous complete-mixing pull process on every finite lift satisfying \(Nr,Nb,Na\in\mathbb{Z}\). Compute the common probability \(p_R(\mu)\) that the lift reaches red consensus; when \(r+b>0\), \(p_R(\mu)=\frac{r}{r+b}\), while \(r+b=0\) yields no consensus.
A society \(\mu\) is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. The types are red, blue, and agnostic, with masses \(r,b,a\geq 0\) satisfying \(r+b+a=1\); omitted types have mass zero. Here \(m=2\) is the number of opinion colours, \(\tau\leq 3\) is the support size, and \(L\) is the total input bit length.
For every positive integer \(N\) with \(Nr,Nb,Na\in\mathbb Z\), a finite lift has these numbers of nodes in the three initial states. For \(N\geq 2\), each step independently chooses a node uniformly and then a different node uniformly; the first copies the second's state if it is red or blue, and otherwise remains unchanged. A single-node lift remains unchanged.
Red consensus means that every node is red, including consensus already present initially. Let \(p_R(\mu)\) denote the common probability of eventually reaching red consensus across all finite lifts; an all-agnostic lift never reaches an opinion consensus and has red-consensus probability zero. The computational output is an exact binary rational.
Is exact computation of \(p_R(\mu)\) polynomial-time in \(m,\tau,L\), or is it NP-hard?
The discrete complete-graph result gives red-consensus probability equal to the initial fraction of red nodes among non-agnostic nodes. [Verified extended version](https://arxiv.org/html/2502.15029v1#S3.SS1) establishes this for every finite lift with a non-agnostic node, so it already determines the lift-defined quantity as \(r/(r+b)\) when \(r+b>0\). Consequently, the stated continuous question is already settled by the anchor.
Exact computation is polynomial-time solvable. If \(r+b=0\), then \(p_R(\mu)=0\); otherwise,
\(p_R(\mu)=r/(r+b)\).
This agrees with [Corollary 3.3 of the cited extended version](https://arxiv.org/html/2502.15029v1#S3.SS1), which treats the asynchronous complete-graph process. Below is a self-contained proof, including the boundary cases and bit complexity.
An exact rational output is understood as a numerator and positive denominator written in binary.
Fix an admissible lift with \(N\geq 2\), initially containing at least one non-agnostic node. A non-agnostic node never becomes agnostic, so an opinion remains present at every time.
From any current configuration, choose a non-agnostic node \(j\). Consider the next \(N-1\) steps in which every other node, in a fixed order, copies \(j\). Node \(j\) is never updated during this sequence, so its colour remains fixed. At the end, every node has its colour.
Every specified ordered pair has probability \(1/[N(N-1)]\). Independence therefore gives this sequence probability
\(\varepsilon_N=[N(N-1)]^{-(N-1)}>0\).
Let \(T\) be the first time of red or blue consensus, including time zero. Conditional on any history without consensus, the probability of reaching consensus within the next \(N-1\) steps is at least \(\varepsilon_N\). Iterating this bound gives
\(\mathbb P(T>k(N-1))\leq(1-\varepsilon_N)^k\)
for every nonnegative integer \(k\). The right-hand side tends to zero. Thus \(T\) is finite almost surely.
Let \(R_t,B_t,A_t\) be the three node counts after \(t\) steps, and put \(C_t=R_t+B_t\). Because an opinion is initially present and cannot disappear into the agnostic state, \(C_t\geq 1\). Define
\(X_t=R_t/C_t\).
Condition on the complete history through time \(t\), and abbreviate the current counts by \(R,B,A,C\). Write \(D=N(N-1)\). The only events that change \(X_t\) are:
| Update | Conditional probability | Change in \(X_t\) |
|---|---:|---:|
| Blue copies red | \(BR/D\) | \(1/C\) |
| Red copies blue | \(RB/D\) | \(-1/C\) |
| Agnostic copies red | \(AR/D\) | \(B/[C(C+1)]\) |
| Agnostic copies blue | \(AB/D\) | \(-R/[C(C+1)]\) |
For example, when an agnostic node becomes red, the change is
\((R+1)/(C+1)-R/C=(C-R)/[C(C+1)]=B/[C(C+1)]\).
When it becomes blue, the change is
\(R/(C+1)-R/C=-R/[C(C+1)]\).
Each probability follows by counting the eligible ordered pairs. Events whose probability is zero contribute nothing. Every remaining event leaves \(X_t\) unchanged. Consequently, the conditional expected increment is
\((BR-RB)/(DC)+(ARB-ABR)/[DC(C+1)]=0\).
Thus \(X_t\) is a martingale. It is bounded between zero and one, so
\(\mathbb E[X_t]=X_0\) for every \(t\).
By Section 1, consensus occurs almost surely. Consensus is absorbing, and \(X_t\) thereafter equals one at red consensus and zero at blue consensus. Hence \(X_t\) converges almost surely to the indicator of eventual red consensus. Since \(|X_t|\leq 1\), dominated convergence applies and yields
\(\mathbb P(\text{eventual red consensus})=\lim_{t\to\infty}\mathbb E[X_t]=X_0\).
For every admissible lift with \(r+b>0\) and \(N\geq 2\), the preceding proof gives
\(X_0=Nr/(Nr+Nb)=r/(r+b)\).
For an admissible single-node lift, integrality and the total mass condition force that node to be initially red, blue, or agnostic. Its unchanged state gives the stated probability in each case.
If \(r+b=0\), every lift is all agnostic and remains so. Its red-consensus probability is zero.
Admissible lifts exist because the masses are rational: any positive common multiple of their denominators is admissible. Therefore the common lift-defined quantity exists and has the claimed formula.
Treat an omitted red or blue mass as \(0/1\). Write
\(r=u/v\) and \(b=w/z\), with nonnegative integer numerators and positive integer denominators.
Compute \(U=uz\) and \(V=wv\). If \(U+V=0\), output \(0/1\). Otherwise output
\(U/(U+V)\), optionally reducing it by \(\gcd(U,U+V)\).
This is correct because
\(r/(r+b)=uz/(uz+wv)\).
All intermediate integers have \(O(L)\) bits. Elementary multiplication and addition take polynomial time, and the Euclidean algorithm with elementary division gives a conservative \(O(L^3)\) bound for reduction. Reading the support also takes polynomial time. Thus computation is polynomial-time in \(m,\tau,L\), with \(m=2\) and \(\tau\leq 3\); no finite lift needs to be constructed or simulated.
If “binary rational” instead requires a finite binary expansion, that output convention is insufficient: the dyadic input \(r=1/4,b=1/2,a=1/4\) has output \(1/3\). Binary numerator–denominator encoding represents the exact answer.
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended task correctly. The absorption argument, martingale calculation, lift independence, and polynomial-time algorithm are rigorous. No major or minor mathematical gaps were found.
This verdict uses the prover’s explicitly stated output convention: a rational represented by a numerator and positive denominator written in binary. Its warning about finite binary expansions correctly identifies an ambiguity in the task.
The proof correctly fixes an arbitrary admissible lift with \(N\geq 2\) and at least one opinionated node.
An opinionated node cannot become agnostic under the specified update rule. Therefore, every reachable configuration still has an opinionated node \(j\).
The proposed sequence of \(N-1\) updates is valid: each node other than \(j\) copies \(j\), and \(j\) is never the updating node. Its colour remains fixed throughout, so the sequence ends in opinion consensus.
Every prescribed ordered pair consists of distinct nodes and has probability \(1/[N(N-1)]\). Independence of successive choices gives the stated probability
\(\varepsilon_N=[N(N-1)]^{-(N-1)}\).
Although \(j\) may depend on the current configuration, this causes no problem: conditional on any current history, the chosen sequence has the same probability \(\varepsilon_N\). Consequently, the conditional probability of avoiding consensus for another block is at most \(1-\varepsilon_N\). The resulting bound
\(\mathbb P(T>k(N-1))\leq(1-\varepsilon_N)^k\)
is correct, including \(k=0\), and implies almost-sure finite consensus.
The denominator \(C_t\) is always positive in the case under consideration, so \(X_t=R_t/C_t\) is well-defined.
All four transition probabilities and increments are correct:
The counts of eligible ordered pairs are \(BR\), \(RB\), \(AR\), and \(AB\). Each pair uses distinct nodes because the two states differ. All other updates preserve the fraction.
The expected increment cancels exactly:
\((BR-RB)/(DC)+(ARB-ABR)/[DC(C+1)]=0\).
This remains valid when any numerator count is zero.
Thus the bounded, adapted process is a martingale, and its expectation equals its deterministic initial value at every time.
Red and blue consensus are absorbing under the stated rule. Almost-sure finite consensus therefore implies that \(X_t\) eventually equals the indicator of red consensus.
The dominated-convergence application is justified: convergence holds almost surely, and the constant integrable random variable \(1\) bounds \(|X_t|\). Hence the limiting expectation equals the red-consensus probability.
Initially present consensus is included correctly: its indicator and initial fraction already agree.
For every admissible lift with \(r+b>0\), the initial opinionated count \(N(r+b)\) is a positive integer. For \(N\geq2\), the proved formula therefore gives \(p_R=r/(r+b)\).
For \(N=1\), integrality and normalization force exactly one mass to equal \(1\). The prover correctly handles the resulting red, blue, and agnostic single-node cases separately.
When \(r+b=0\), nonnegativity forces \(r=b=0\), and every lift remains all agnostic. Its red-consensus probability is zero.
Rational masses admit a positive common multiple of their denominators, so admissible lifts exist. The argument establishes both existence and independence of the lift-defined probability.
The cited [Corollary 3.3](https://arxiv.org/html/2502.15029v1#S3.SS1) states the claimed red-consensus formula for the asynchronous complete-graph model. The relevant setting matches the task when an opinion is present. The prover’s separate treatment of degenerate cases is appropriate.
The citation is corroborative; the supplied proof independently establishes the result.
The cross-products \(U=uz\) and \(V=wv\) correctly yield \(r/(r+b)=U/(U+V)\) when \(U+V>0\). Positive denominators and nonnegative numerators make the zero test valid.
Products have bit lengths bounded by sums of input bit lengths; addition adds at most one bit. Thus all intermediate integers and the output have \(O(L)\) bits. Binary arithmetic is polynomial-time, and the stated conservative \(O(L^3)\) bound for optional Euclidean reduction is valid.
The finite-expansion example is also correct: the specified dyadic masses yield probability \(1/3\). Under the explicitly stated numerator–denominator convention, the algorithm meets the intended exact-output requirement.
No repair or 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.