Answer: Polynomial-time solvable.
Theorem 5.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (V, E) be an arbitrary graph. The biased opinion dynamics with voter as update rule reaches state 1 within τ = O( 1 αn log n) steps, with high probability.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\) with rational masses \(\mu_i>0\) summing to \(1\), a rational symmetric contact kernel \(K\) with positive row normalizers, rational \(\alpha\in(0,1]\), and rational \(\varepsilon,\delta\in(0,1)\), define \(Q_{ij}=\mu_jK_{ij}/\sum_\ell\mu_\ell K_{i\ell}\). Starting from \(x_i(0)=0\), evolve \(\dot{x}_i=\alpha(1-x_i)+(1-\alpha)(\sum_jQ_{ij}x_j-x_i)\). Return a certified interval of width at most \(\delta\) containing the first time \(s\) at which \(\max_i(1-x_i(s))\le\varepsilon\).
A society is given by its support: the list of \(\tau\ge1\) types with positive masses \(\mu_i\), each a binary rational, with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types; there are \(m=2\) opinions.
The input also contains a symmetric, entrywise nonnegative rational contact kernel \(K\), allowing diagonal entries, with \(d_i=\sum_j\mu_jK_{ij}>0\), and binary rationals \(\alpha\in(0,1]\) and \(\varepsilon,\delta\in(0,1)\). Let \(L\) be the total binary input length and \(Q_{ij}=\mu_jK_{ij}/d_i\).
Let \(x_i(t)\in[0,1]\) denote the fraction of type \(i\) holding opinion \(1\). In time units giving each individual update rate \(1\), define \(x_i(0)=0\) and \(\dot{x}_i=\alpha(1-x_i)+(1-\alpha)(\sum_jQ_{ij}x_j-x_i)\).
The computational problem is to return binary rational endpoints \(0\le a\le b\) with \(b-a\le\delta\) and \(a\le s\le b\), where \(s=\inf\{t\ge0:\max_i(1-x_i(t))\le\varepsilon\}\); containment must be guaranteed.
Can this certified interval problem be solved in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite undirected graphs with nonempty neighborhoods, biased voter dynamics selects one agent uniformly per step, sets its opinion to \(1\) with probability \(\alpha\), and otherwise copies a uniformly sampled neighbor. Absorption occurs within \(O(\alpha^{-1}n\log n)\) steps with high probability, even from arbitrary initial opinions ([Anagnostopoulos et al.](https://iris.uniroma1.it/retrieve/249c3bf5-d27b-4a01-a040-a36074f8d1a4/Anagnostopoulos_Biased-opinion_2022.pdf)).
This is a stochastic convergence bound, polynomial when \(\alpha^{-1}\) is polynomially bounded in \(n\); it does not classify the deterministic mass-based interval problem.
The certified interval problem is solvable in polynomial time in the stated binary input length, and hence in \(m,\tau,L\).
The common zero initial condition makes all types evolve identically. The substantive computational issue is obtaining a certified rational interval when \(\alpha\) and \(\delta\) may be exponentially small.
The assumptions \(d_i>0\) and \(K_{ij}\ge 0\) imply that \(Q\) is well-defined and satisfies
\[ \sum_j Q_{ij} =\frac{\sum_j\mu_jK_{ij}}{d_i} =1. \]
Let \(u(t)=1-e^{-\alpha t}\). If \(x_i(t)=u(t)\) for every \(i\), then \(\sum_jQ_{ij}x_j(t)=u(t)\), and consequently
\[ \alpha(1-x_i(t))+(1-\alpha)\left(\sum_jQ_{ij}x_j(t)-x_i(t)\right) =\alpha e^{-\alpha t} =\dot u(t). \]
Thus this vector satisfies both the differential equation and the prescribed initial condition. A finite-dimensional linear differential equation has a unique solution, so
\[ x_i(t)=1-e^{-\alpha t}\qquad\text{for every }i. \]
Therefore \(\max_i(1-x_i(t))=e^{-\alpha t}\). Since \(\alpha>0\) and \(0<\varepsilon<1\), the hitting time is exactly
\[ s=\frac{\log(1/\varepsilon)}{\alpha}. \]
Here and below, \(\log\) denotes the natural logarithm. Neither symmetry of \(K\) nor a stochastic absorption estimate is needed for this conclusion.
For \(1\le u\le 2\), put \(w=(u-1)/(u+1)\), so \(0\le w\le 1/3\). For an integer \(N\ge 1\), define the rational expression
\[ S_N(u)=2\sum_{j=0}^{N-1}\frac{w^{2j+1}}{2j+1}. \]
We claim that
\[ 0\le \log u-S_N(u)\le 9^{-N}. \]
Indeed, substituting \(u=(1+w)/(1-w)\) gives \(\log u=2\int_0^w(1-v^2)^{-1}\,dv\). The finite geometric identity then gives the exact remainder
\[ \log u-S_N(u) =2\int_0^w\frac{v^{2N}}{1-v^2}\,dv. \]
The integrand is nonnegative. Also, \(1-v^2\ge 1-w^2\), so
\[ \log u-S_N(u) \le \frac{2w^{2N+1}}{(2N+1)(1-w^2)} \le \frac{3}{4(2N+1)}\,9^{-N} \le 9^{-N}. \]
This proves the claimed enclosure using only rational arithmetic.
Set \(z=1/\varepsilon>1\). Compute the integer \(k\ge 0\) satisfying \(2^k\le z<2^{k+1}\), and put \(r=z/2^k\). Thus \(1\le r<2\), and
\[ \log z=k\log 2+\log r. \]
Choose the smallest integer \(N\ge 1\) satisfying
\[ (k+1)9^{-N}\le \alpha\delta. \]
This choice can be made by exact integer comparisons, without evaluating logarithms.
Compute the rational numbers
\[ \ell=kS_N(2)+S_N(r), \qquad E=(k+1)9^{-N}. \]
Applying the preceding logarithm bound to \(2\) and \(r\), and using \(k\ge 0\), yields
\[ \ell\le \log z\le \ell+E. \]
Return
\[ a=\frac{\ell}{\alpha}, \qquad b=\frac{\ell+E}{\alpha}. \]
All terms in \(\ell\) are nonnegative, hence \(0\le a\le b\). Since \(\alpha>0\), the logarithm enclosure proves \(a\le s\le b\). Finally,
\[ b-a=\frac{E}{\alpha}\le\delta. \]
Thus the output meets every required certification condition.
Under the stated binary rational encoding, every input numerator and denominator has at most \(O(L)\) bits.
First, \(z=1/\varepsilon\) has \(O(L)\)-bit numerator and denominator. Consequently \(k=O(L)\), and exact comparisons with powers of \(2\) compute \(k\) in polynomial time. The rational number \(r=z/2^k\) also has \(O(L)\)-bit numerator and denominator.
Second, positivity and the input bit-length bounds give \(\alpha\delta\ge 2^{-O(L)}\). Together with \(k=O(L)\), this implies that the selected \(N\) is \(O(L)\). Its selection requires only polynomially many comparisons involving polynomial-length integers.
Finally, the rational sums have polynomial-size exact representations. To see this explicitly, write \(w=P/H\), with \(P,H\) having \(O(L)\) bits. A common denominator for \(S_N(u)\) is
\[ D_N=H^{2N-1}\prod_{j=0}^{N-1}(2j+1). \]
Every summand denominator divides \(D_N\). Its bit length is
\[ O(NL+N\log N), \]
which is polynomial in \(L\). Each summand can therefore be converted to this common denominator and summed using polynomially many operations on polynomial-length integers. This applies to both \(S_N(2)\) and \(S_N(r)\). Forming \(\ell,E,a,b\) preserves polynomial bit length.
Standard exact integer arithmetic consequently computes and outputs the certified interval in polynomial time. Although \(s\) can be exponentially large, its magnitude does not prevent a polynomial-size binary representation of the endpoints.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes a polynomial-time algorithm that returns a guaranteed rational interval of width at most \(\delta\). No major or minor mathematical issues were found.
This assessment uses the stated binary encoding of rational numbers, in which numerators and denominators are written in binary.
The row-sum calculation is valid: each \(d_i>0\), so division is permitted, and the definition of \(d_i\) gives \(\sum_j Q_{ij}=1\).
The proposed solution \(x_i(t)=1-e^{-\alpha t}\) satisfies the initial condition and the differential equation. Because all its coordinates agree, the copying term vanishes by the row-sum identity. Its derivative is exactly \(\alpha e^{-\alpha t}\), matching the remaining forcing term.
The uniqueness theorem invoked is applicable: this is a finite-dimensional linear differential equation with fixed, finite coefficients, so its prescribed initial condition determines a unique solution for all \(t\ge0\).
Consequently, \(\max_i(1-x_i(t))=e^{-\alpha t}\). Since \(\alpha>0\) and \(0<\varepsilon<1\), this expression decreases continuously from \(1\) to \(0\), reaching \(\varepsilon\) at
\[
s=\frac{\log(1/\varepsilon)}{\alpha}.
\]
Thus the formula correctly computes the infimum in the task, including equality at the threshold.
The argument covers \(\tau=1\), \(\alpha=1\), diagonal contacts, and disconnected contact structures. Symmetry is indeed unnecessary for this particular initial condition.
Finding: Correct; no missing hypotheses or edge cases.
For \(1\le u\le2\), the transformation \(w=(u-1)/(u+1)\) gives \(0\le w\le1/3\), as claimed.
The integral identity and the finite geometric expansion yield the stated exact remainder. All denominators are positive throughout the integration interval. Bounding \(1-v^2\) below by \(1-w^2\) therefore preserves the inequality direction.
The numerical constant is correct. The bounds \(w^{2N+1}\le (1/3)9^{-N}\) and \((1-w^2)^{-1}\le9/8\) give
\[
\frac{2w^{2N+1}}{(2N+1)(1-w^2)}
\le \frac{3}{4(2N+1)}9^{-N}
\le 9^{-N}.
\]
The nonnegative integrand supplies the lower bound.
At \(u=1\), both the sum and the remainder vanish. At \(u=2\), the bound still holds. Hence the enclosure is valid over the entire claimed domain.
Finding: Correct; the constants, signs, and ranges check out.
Because \(z=1/\varepsilon>1\), the integer \(k\) exists and satisfies \(k\ge0\). The resulting \(r=z/2^k\) lies in \([1,2)\), within the logarithm enclosure’s domain.
The logarithm decomposition is exact. Multiplication of the enclosure for \(\log2\) by \(k\) preserves its direction because \(k\ge0\). Adding the enclosure for \(\log r\) gives precisely the stated error allowance \(E=(k+1)9^{-N}\).
An admissible \(N\) exists because \(\alpha\delta>0\) and \(9^{-N}\) tends to zero. The selected inequality guarantees \(E/\alpha\le\delta\).
Every summand defining \(\ell\) is nonnegative. Division by the positive \(\alpha\) therefore gives nonnegative, correctly ordered endpoints, preserves containment, and produces width at most \(\delta\).
The case \(k=0\) causes no difficulty. When \(r=1\), its logarithm contribution is zero; the error allowance remains valid.
Finding: All required output conditions are proved.
The bit-length analysis is sound.
\[
D_N=H^{2N-1}\prod_{j=0}^{N-1}(2j+1).
\]
Its bit length is \(O(NL+N\log N)\), as claimed. Conversion and summation thus involve polynomially many operations on polynomial-length integers.
Standard exact integer arithmetic supplies polynomial running time for these operations. The proof bounds both computation time and output length, despite potentially exponentially large endpoint values.
Finding: The claimed polynomial-time complexity is established.
No mathematical repair or additional clarification is needed. The proof resolves the deterministic interval problem directly and does not rely on the stochastic convergence bound.
⟨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.