Answer: polynomial-time solvable
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAssume that T is connected (irreducible) and aperiodic and that q0 and T satisfy Assumption 1. Then there exists a vector α = (α1, ..., αn) ∈Rn + such that: (i) the limit posterior beliefs of all players converge to a degenerate belief on the maximiser of Πj∈N(qj 0(ω))αj. (ii) the vector α is parallel to the Perron-Frobenius eigenvector of T. To see the intuition of the result, consider the complete network. Note that after the first period of communication, all would have the same beliefs, at q1(ω) ≡ Πi∈Nqi 0(ω) P ν∈ΩΠi∈Nqi 0(ν).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite sets of types \(T\) and states \(\Omega\), rational type masses \(\mu_a\) summing to \(1\), rational full-support initial beliefs \(q_{a,0}\), and a rational interaction matrix \(W\) for which \(A_{ab}=W_{ab}\mu_b\) is primitive, compute the limiting consensus mode \(\arg\max_{\omega\in\Omega}\sum_{b\in T}\lambda_b\log q_{b,0}(\omega)\), where \(\lambda\) is the normalized positive left Perron–Frobenius eigenvector of \(A\). Assume the maximizing state is unique with a supplied rational score-gap lower bound, and determine the computation’s dependence on \(|T|\), \(|\Omega|\), input bit length, and the gap.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_a\), where \(\sum_a\mu_a=1\); \(\tau\) counts supported types, not possible types. Let \(\Omega\) be an explicitly listed state set of size \(m\ge2\).
Each type has a rational probability distribution \(q_{a,0}\) with \(q_{a,0}(\omega)>0\) for every state. The common prior is uniform. A nonnegative rational matrix \(W\) specifies interaction weights, with \(A_{ab}=W_{ab}\mu_b\); promise that \(A\) is primitive and its spectral radius \(\rho(A)>1\).
Mass-weighted Bayesian Peer Influence updates are \(q_{a,k+1}(\omega)=\frac{\prod_b q_{b,k}(\omega)^{A_{ab}}}{\sum_{v\in\Omega}\prod_b q_{b,k}(v)^{A_{ab}}}\).
Let \(\lambda\) be the positive left Perron–Frobenius eigenvector, normalized by \(\sum_b\lambda_b=1\), and set \(s(\omega)=\sum_b\lambda_b\log q_{b,0}(\omega)\), using natural logarithms. A supplied binary rational \(\delta>0\) promises a unique maximizer \(\omega^*\) satisfying \(s(\omega^*)-s(v)\ge\delta\) for every \(v\ne\omega^*\). The required output is \(\omega^*\). Let \(L\) be the total input bit length, including \(\delta\).
Is this promised consensus-mode problem solvable in polynomial time, or is it NP-hard? What is its bit-complexity dependence on \(m,\tau,L\), and \(\delta\), particularly on \(\log(1+\delta^{-1})\)?
For finite connected undirected networks with self-links and at least two agents, Bayesian Peer Influence converges to the unique Perron-weighted product mode; this is a convergence characterization, not a bit-complexity theorem. [Levy–Razin](https://eprints.lse.ac.uk/86554/7/Levy_information_diffusion_in_networks_accepted.pdf)
No result settling the exact mass-weighted, rational-input, supplied-gap problem was located in the literature search.
The promised problem is solvable in deterministic polynomial time. Its bit complexity is polynomial in
$$
m,\quad \tau,\quad L,\quad \log(1+\delta^{-1}).
$$
In particular, the algorithm does not require a number of steps proportional to $\delta^{-1}$. Since $\delta$ is a positive binary rational included in the input,
$$
\log_2(1+\delta^{-1})\le L+1,
$$
so the running time is polynomial in the total input length itself.
Consequently, NP-hardness under polynomial-time, promise-preserving reductions would imply $\mathsf P=\mathsf{NP}$.
The proof computes the Perron-weighted scores directly. It supplies a bit-complexity argument separate from the convergence characterization in [Levy–Razin](https://eprints.lse.ac.uk/86554/7/Levy_information_diffusion_in_networks_accepted.pdf).
Write $n=\tau$ and $A_{ab}=W_{ab}\mu_b$.
Let $D$ be the product of the denominators appearing in $W$ and in the masses. Then
$$
B=DA
$$
is an integer matrix. Indeed, the denominator of each product $W_{ab}\mu_b$ divides $D$. This construction uses the supported types directly, without expanding their rational masses into agents.
The matrices $A$ and $B$ have the same left and right Perron eigenvectors. Moreover, $B$ is primitive. Put
$$
r=\rho(B),\qquad H=\max_{a,b}B_{ab},\qquad U=nH+1.
$$
The input bounds give
$$
D\le 2^L,\qquad H\le 2^{2L},\qquad
\log_2 U=O(L+\log(n+1)).
$$
Every eigenvalue of $B$ has modulus at most $nH$, by the maximum row-sum bound. Thus
$$
0<r<U.
$$
We use the following consequences of the Perron–Frobenius theorem: because $B$ is primitive, $r$ is algebraically simple; there are strictly positive vectors $\lambda,h$ satisfying
$$
B^\top\lambda=r\lambda,\qquad Bh=rh,
\qquad \sum_a\lambda_a=1.
$$
Finally, every input probability satisfies $2^{-L}\le q_{a,0}(\omega)\le1$. Therefore, with
$$
M=L+1,
$$
we have
$$
\left|\log q_{a,0}(\omega)\right|\le M.
$$
Let
$$
p(x)=\det(xI-B).
$$
This is a monic integer polynomial of degree $n$. Define
$$
\gamma=(2U)^{-(n-1)^2}.
$$
We first prove
$$
p'(r)\ge\gamma.
$$
Let $f$ be the monic minimal polynomial of $r$ over $\mathbb Q$, of degree $d$. By Gauss’s lemma, $f$ belongs to $\mathbb Z[x]$ and divides $p$. Its distinct roots $\alpha_1=r,\alpha_2,\ldots,\alpha_d$ are roots of $p$.
Because $r$ is a simple root of $p$, we have $p'(r)\ne0$. Irreducibility of $f$ then implies
$$
p'(\alpha_j)\ne0
$$
for every $j$: otherwise $f$ would divide $p'$.
Multiplication by $p'$ on $\mathbb Z[x]/(f)$ has an integer matrix in the basis $1,x,\ldots,x^{d-1}$. Over $\mathbb C$, evaluation at the distinct roots of $f$ diagonalizes this multiplication map. Hence its determinant is the nonzero integer
$$
\prod_{j=1}^{d}p'(\alpha_j).
$$
Its absolute value is at least $1$.
Every root of $p$ has modulus less than $U$. At any simple root $\alpha_j$,
$$
|p'(\alpha_j)|
=\prod_{\substack{\beta\text{ a root of }p\\ \beta\ne\alpha_j}}
|\alpha_j-\beta|
\le(2U)^{n-1},
$$
where roots in the product are counted with multiplicity. Consequently,
$$
|p'(r)|
\ge(2U)^{-(n-1)(d-1)}
\ge\gamma.
$$
Also $p'(r)>0$: every other real eigenvalue is less than $r$, and conjugate nonreal eigenvalues contribute positive factors $|r-\beta|^2$ to $p'(r)$. This proves the claim.
The minimal polynomial is used only to establish this bound; computing it is unnecessary.
Now define the polynomial vector
$$
y(t)=\operatorname{adj}(tI-B^\top)\mathbf1,
\qquad
S(t)=\mathbf1^\top y(t).
$$
At the simple eigenvalue $r$,
$$
\operatorname{adj}(rI-B^\top)
=\frac{p'(r)}{h^\top\lambda}\lambda h^\top.
$$
To justify this identity, the adjugate’s columns and rows lie in the respective one-dimensional nullspaces of $rI-B^\top$. Thus it is a scalar multiple of $\lambda h^\top$. Differentiating the determinant gives
$$
p'(r)=\operatorname{tr}\!\left(\operatorname{adj}(rI-B^\top)\right),
$$
which determines the scalar.
It follows that
$$
y(r)=p'(r)\frac{h^\top\mathbf1}{h^\top\lambda}\lambda,
\qquad
S(r)=p'(r)\frac{h^\top\mathbf1}{h^\top\lambda}\ge\gamma.
$$
The inequality uses $\lambda_a\le1$ and $h_a>0$.
For rational $t$, test whether $tI-B^\top$ is nonsingular and the exact solution of
$$
(tI-B^\top)x=\mathbf1
$$
has every coordinate strictly positive.
This test is true exactly when $t>r$.
If $t>r$, the convergent Neumann series gives
$$
(tI-B^\top)^{-1}
=\frac1t\sum_{k=0}^{\infty}(B^\top/t)^k.
$$
Every summand is nonnegative, and its identity term ensures $x_a>0$.
Conversely, if a solution has $x>0$, multiplication by $h^\top$ gives
$$
(t-r)h^\top x=h^\top\mathbf1>0.
$$
Thus $t>r$. If the matrix is singular, $t$ is an eigenvalue of $B^\top$, so it cannot exceed $r$.
All these tests use exact rational arithmetic. Therefore bisection on $[0,U]$ maintains an interval containing $r$, with upper endpoint strictly greater than $r$. After $K$ steps its upper endpoint $t$ satisfies
$$
r<t,\qquad t-r\le U2^{-K}.
$$
We next bound how accurately $t$ must approximate $r$.
For $t\in[0,U]$, every entry of $tI-B^\top$ has absolute value at most $2U$. Expanding each cofactor determinant and differentiating its products shows, for $n\ge2$,
$$
|y_a'(t)|
\le n(n-1)!(n-1)(2U)^{n-2}.
$$
For $n=1$, the derivative is zero. Hence the following convenient bound works for all $n$:
$$
|y_a'(t)|\le C,\qquad
C=n^2n!(2U)^n.
$$
The mean-value theorem yields
$$
\|y(t)-y(r)\|_1\le nC|t-r|.
$$
For $t>r$, let
$$
\widehat\lambda=\frac{x(t)}{\mathbf1^\top x(t)}.
$$
This is an exactly computable positive rational probability vector. Since $p(t)>0$,
$$
\widehat\lambda=\frac{y(t)}{S(t)}.
$$
Put $E=\|y(t)-y(r)\|_1$. Both vectors are positive, and normalization gives
$$
\begin{aligned}
\left\|\frac{y(t)}{S(t)}-\frac{y(r)}{S(r)}\right\|_1
&\le
\frac{E}{S(r)}
+\frac{|S(t)-S(r)|}{S(r)}\\
&\le\frac{2E}{S(r)}.
\end{aligned}
$$
Therefore
$$
\|\widehat\lambda-\lambda\|_1
\le\frac{2nC}{\gamma}|t-r|.
$$
Choose
$$
\eta=\frac{\delta\gamma}{16nCM}
$$
and run bisection until $U2^{-K}\le\eta$. Then
$$
\|\widehat\lambda-\lambda\|_1\le\frac{\delta}{8M}.
$$
The required number of steps satisfies
$$
K=
O\!\left(
n^2(L+\log(n+1))
+\log(1+\delta^{-1})
+\log(L+1)
\right).
$$
This follows by taking binary logarithms of $U/\eta$, using the explicit formulas for $C$ and $\gamma$.
Thus no additional quantitative promise on the spectral gap is required.
Here is an explicit rational procedure for approximating the natural logarithms.
For an input probability $q$, choose an integer $e$ such that
$$
u=2^e q\in[1,2),\qquad 0\le e\le L.
$$
The exponent is obtained from numerator and denominator bit lengths followed by a comparison. Then
$$
\log q=\log u-e\log2.
$$
For $0\le z\le1/3$, define
$$
F_N(z)=2\sum_{j=0}^{N-1}\frac{z^{2j+1}}{2j+1}.
$$
Expanding the geometric series and integrating gives
$$
\log\frac{1+z}{1-z}
=2\sum_{j=0}^{\infty}\frac{z^{2j+1}}{2j+1}.
$$
Its tail obeys
$$
\begin{aligned}
0\le
\log\frac{1+z}{1-z}-F_N(z)
&\le\frac{2z^{2N+1}}{1-z^2}\\
&\le9^{-N}.
\end{aligned}
$$
Apply this with $z=(u-1)/(u+1)$ for $\log u$, and with $z=1/3$ for $\log2$. The resulting approximation to $\log q$ has error at most
$$
(L+1)9^{-N}.
$$
Choose $N\ge1$ with
$$
(L+1)9^{-N}\le\frac{\delta}{16},
$$
and round the resulting rational number to a common dyadic precision whose rounding error is at most $\delta/16$. We obtain rational numbers $\ell_a(\omega)$ satisfying
$$
|\ell_a(\omega)-\log q_{a,0}(\omega)|\le\frac{\delta}{8}.
$$
The required parameters obey
$$
N=O\!\left(\log(L+1)+\log(1+\delta^{-1})\right),
$$
and the dyadic precision is $O(1+\log(1+\delta^{-1}))$ bits after the binary point.
Now compute, exactly,
$$
\widehat s(\omega)=\sum_a\widehat\lambda_a\ell_a(\omega).
$$
Because $\widehat\lambda$ is a probability vector,
$$
\begin{aligned}
|\widehat s(\omega)-s(\omega)|
&\le
M\|\widehat\lambda-\lambda\|_1
+\sum_a\widehat\lambda_a
|\ell_a(\omega)-\log q_{a,0}(\omega)|\\
&\le\frac{\delta}{8}+\frac{\delta}{8}
=\frac{\delta}{4}.
\end{aligned}
$$
For every $v\ne\omega^*$, the supplied promise therefore implies
$$
\widehat s(\omega^*)-\widehat s(v)
\ge\delta-\frac{\delta}{4}-\frac{\delta}{4}
=\frac{\delta}{2}>0.
$$
Returning the exact maximizer of the rational scores $\widehat s$ returns $\omega^*$.
Let
$$
G=\left\lceil\log_2(1+\delta^{-1})\right\rceil,
$$
and use the parameters $K,N$ above. Define
$$
P=
n\bigl(L+K+\lceil\log_2(n+1)\rceil\bigr)
+
N\bigl(L+\lceil\log_2(N+1)\rceil\bigr).
$$
A conservative implementation using schoolbook integer arithmetic has bit complexity
$$
O\!\left(
\left[(K+1)n^4+mn(N+1)\right]P^2
\right).
$$
Here are the arithmetic bounds supporting this estimate.
$$
b^{2N-1}\prod_{j=0}^{N-1}(2j+1).
$$
Its bit length is $O(N(L+\log(N+1)))$. Precomputing the necessary powers and assembling the terms uses $O(N)$ integer operations of $O(P)$ bits. Range reduction and dyadic rounding have the same polynomial bounds.
Integer scaling and input processing fit within the displayed bound.
This estimate is deliberately coarse, but it gives the requested dependence explicitly:
$$
K=O\!\left(n^2(L+\log(n+1))+G+\log(L+1)\right),
\qquad
N=O(G+\log(L+1)).
$$
In particular, every dependence on gap precision is polynomial in $G$, rather than in $\delta^{-1}$. Since $G\le L+1$ and both $m$ and $n=\tau$ are explicitly represented, the algorithm is polynomial in $L$.
The same assumptions also justify calling the output the consensus mode.
For each competing state $v$, define the vector
$$
d_{a,k}(v)=
\log\frac{q_{a,k}(\omega^*)}{q_{a,k}(v)}.
$$
Cancellation of the update’s normalization factors gives
$$
d_{k+1}(v)=Ad_k(v),
\qquad
d_k(v)=A^kd_0(v).
$$
Because $A$ is primitive, Perron–Frobenius theory gives
$$
\rho(A)^{-k}A^k
\longrightarrow
\frac{h\lambda^\top}{\lambda^\top h}.
$$
Consequently,
$$
\rho(A)^{-k}d_k(v)
\longrightarrow
\frac{h\,[s(\omega^*)-s(v)]}{\lambda^\top h}.
$$
Every coordinate of the limit is strictly positive by the gap promise. Since $\rho(A)>1$, each $d_{a,k}(v)$ tends to $+\infty$. Finally,
$$
q_{a,k}(\omega^*)
=
\frac{1}{1+\sum_{v\ne\omega^*}\exp(-d_{a,k}(v))}
\longrightarrow1.
$$
The polynomial-time algorithm above identifies this state without simulating the dynamics.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the supplied-gap, rational-input problem. The algorithm is correct, and its bit complexity is polynomial in $m,\tau,L$, and $\log(1+\delta^{-1})$. I found no substantive or expositional gap requiring repair.
The construction $B=DA$ is valid. Each denominator in $W_{ab}\mu_b$ divides the product of the corresponding input denominators, hence divides $D$. Positive scalar multiplication preserves primitivity and both Perron eigenvectors.
The stated size bounds are sound:
The Perron–Frobenius hypotheses are satisfied: $B$ is a primitive nonnegative matrix. Consequently, its Perron root is positive and algebraically simple, with strictly positive left and right eigenvectors.
The argument establishing
$$
p'(r)\ge (2U)^{-(n-1)^2}
$$
is correct.
The minimal polynomial $f$ is monic with integer coefficients and divides $p$. If $p'$ vanished at any root of $f$, irreducibility would imply $f\mid p'$, contradicting $p'(r)\ne0$. Thus every conjugate used in the determinant product is a simple root of $p$.
Multiplication by $p'$ on $\mathbb Z[x]/(f)$ has an integer matrix. Evaluation at the distinct complex roots of $f$ diagonalizes its complexification, so the product
$$
\prod_{j=1}^d p'(\alpha_j)
$$
is a nonzero integer. Its absolute value is therefore at least $1$.
All roots of $p$ have modulus less than $U$. The bound $(2U)^{n-1}$ on each conjugate derivative follows, including repeated roots among the other factors. Combining these estimates gives the claimed lower bound.
The sign argument also holds: other real eigenvalues are strictly less than $r$, and nonreal conjugate pairs contribute positive factors. Therefore $p'(r)>0$.
For $n=1$, the formula gives $\gamma=1$, and indeed $p'(r)=1$.
The adjugate identity is justified as written. At the simple eigenvalue, the relevant right and left nullspaces are one-dimensional. Thus the adjugate is a scalar multiple of $\lambda h^\top$, and the determinant derivative determines that scalar.
Consequently,
$$
S(r)=p'(r)\frac{h^\top\mathbf1}{h^\top\lambda}\ge\gamma.
$$
The inequality follows from $0<\lambda_a\le1$ and $h_a>0$. No quantitative bound on individual Perron-vector coordinates is assumed.
The proposed test characterizes $t>r$ correctly.
For $t>r$, the matrix $B^\top/t$ has spectral radius less than $1$, so its Neumann series converges. Nonnegativity and the identity term ensure that the solution has strictly positive coordinates.
Conversely, a positive solution satisfies
$$
(t-r)h^\top x=h^\top\mathbf1>0,
$$
forcing $t>r$. A singular matrix cannot occur for real $t>r$, since such a $t$ cannot be an eigenvalue.
The initial interval $[0,U]$ is valid. Bisection preserves an upper endpoint strictly greater than $r$, including when a midpoint equals $r$. Hence the stated approximation guarantee follows.
The cofactor derivative estimate is valid: each cofactor contains $(n-1)!$ determinant terms, each product has $n-1$ factors, and each factor has absolute value at most $2U$. Summing over the $n$ cofactors contributing to a coordinate gives the displayed bound. The larger constant $C$ safely covers every $n$, including $n=1$.
For $t>r$, both $p(t)$ and the solution vector are positive, so
$$
\widehat\lambda=\frac{y(t)}{S(t)}
$$
is justified.
The normalization inequality is correct even if $S(t)<S(r)$; it does not require an additional lower bound on $S(t)$. It yields
$$
\|\widehat\lambda-\lambda\|_1
\le\frac{2nC}{\gamma}|t-r|.
$$
The chosen $\eta$ therefore gives the claimed error $\delta/(8M)$.
Taking logarithms of the explicit constants produces the stated bound on $K$. Thus the proof genuinely avoids requiring a separately supplied spectral-gap bound.
Range reduction is valid for every input probability, including $q=1$. The resulting series arguments lie in $[0,1/3]$.
The tail estimate checks:
$$
\frac{2z^{2N+1}}{1-z^2}\le 9^{-N}.
$$
The errors in approximating $\log u$ and $\log2$, including multiplication by $e$, total at most $(L+1)9^{-N}$. The subsequent rounding allowance gives the stated logarithm error $\delta/8$.
Because $\widehat\lambda$ is a probability vector, the score error is at most
$$
M\|\widehat\lambda-\lambda\|_1+\frac{\delta}{8}
\le\frac{\delta}{4}.
$$
Therefore the supplied separation promise leaves a strictly positive approximate-score margin:
$$
\widehat s(\omega^*)-\widehat s(v)\ge\frac{\delta}{2}.
$$
Exact comparison of the rational approximate scores returns the required state.
The conservative bound is supported by the arithmetic accounting.
Clearing each bisection denominator produces integer matrices with the stated entry lengths. Determinants and Cramer numerators can be computed by fraction-free elimination, with pivoting and singularity detection as needed. The minor bounds control intermediate bit lengths, and schoolbook multiplication and exact division fit the stated quadratic bit cost per arithmetic operation.
The proposed common denominator for $F_N(z)$ is valid: every term denominator divides it. Its bit length is $O(N(L+\log(N+1)))$, and powers and term assembly require $O(N)$ bounded-size operations.
Common denominators for the final logarithm approximations and normalized Perron vector also justify the score-computation bound.
Thus
$$
O\!\left(\left[(K+1)n^4+mn(N+1)\right]P^2\right)
$$
is a valid coarse bound. Its dependence on gap precision is polynomial in
$$
G=\left\lceil\log_2(1+\delta^{-1})\right\rceil,
$$
rather than in $\delta^{-1}$. Since $\delta$ is included in the binary input, $G\le L+1$. Explicit representation also bounds $m$ and $n$ by the input length.
The NP-hardness qualification is appropriately conditional on polynomial-time, promise-preserving reductions.
The log-ratio recurrence follows by cancellation of normalization factors. Primitivity supplies the stated normalized-power limit, and the gap promise makes each limiting coordinate strictly positive.
The separate assumption $\rho(A)>1$ then implies that every competing log ratio tends to $+\infty$. Since the state set is finite, the final probability expression converges to $1$ for every supported type.
This establishes the asserted consensus interpretation without using convergence speed as a complexity bound.
No additional clarification or repair is required.
⟨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.