Answer: —
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $c^\star = \frac{\sqrt{2}-1}{2}$ be a universal constant. Let $G=(V, E)$ be an $(n, \epsilon, c_r, c_d)$-Core-Periphery network such that $d_{_{\min}} = \omega(\log n)$ and let $G$ run the \choice{}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given core and periphery masses \(\mu_C,\mu_P\) with \(\mu_C+\mu_P=1\), per-capita degree-volume weights \(d_C,d_P\), a rational \(q\in[0,1]\) for the periphery’s probability of sampling the frozen-blue core on each draw, a target \(\kappa\), and a horizon \(H\), initialize the core blue and the periphery red. Let \(x_t\) be the blue fraction of the periphery, \(y_t=q+(1-q)x_t\), and \(x_{t+1}=(1-x_t)y_t^2+x_t(1-(1-y_t)^2)\). Decide whether, for some \(t\le H\), the degree-volume-weighted blue share \((\mu_Cd_C+\mu_Pd_Px_t)/(\mu_Cd_C+\mu_Pd_P)\) is at least \(1-\kappa\).
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. Here the types are core and periphery, \(\tau=2\), and there are \(m=2\) colors.
The input consists of positive rational masses \(\mu_C+\mu_P=1\), positive rational degree-volume weights \(d_C,d_P\), rationals \(q,\kappa\in[0,1]\), and a nonnegative integer horizon \(H\) encoded in binary. Let \(L\) be the total input bit length.
The core stays blue forever. Initially the periphery is red. In each synchronous round, each periphery draw independently samples the core with probability \(q\), and otherwise samples the periphery uniformly by mass; two matching sampled colors replace the current color, while differing colors leave it unchanged.
The deterministic mass evolution is defined exactly by \(x_0=0\), \(y_t=q+(1-q)x_t\), and \(x_{t+1}=(1-x_t)y_t^2+x_t(1-(1-y_t)^2)\), where \(x_t\) is the blue fraction of the periphery.
The decision problem asks whether some integer \(0\leq t\leq H\) satisfies \((\mu_Cd_C+\mu_Pd_Px_t)/(\mu_Cd_C+\mu_Pd_P)\geq1-\kappa\); comparison is exact, including equality.
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, with running times measured in \(m,\tau,L\) and the binary encoding length of \(H\)?
Discrete: A stochastic phase-transition theorem gives blue almost-consensus within \(O(\log(1/\kappa(n)))\) rounds with high probability on graphs having periphery size \(n\), core size \(n^\varepsilon\), \(1/2\leq\varepsilon\leq1\), minimum degree \(\omega(\log n)\), periphery core/internal-neighbor ratio constantly above \((\sqrt2-1)/2\), core internal/periphery-neighbor ratio exceeding \(n^{(\varepsilon+\delta)/2}\) for suitable constant \(\delta>0\), and \(\kappa(n)\geq\lambda\log n/d_{\min}\) for suitable constant \(\lambda\); below the dominance threshold, at least three quarters of periphery volume stays red for polynomially many rounds with high probability. [Source](https://link.springer.com/article/10.1007/s00446-021-00396-5).
Continuous: No result settling this exact binary-horizon decision problem was identified in the literature search.
I do not obtain a classification of the unrestricted problem as belonging to $\mathrm P$ or being $\mathrm{NP}$-hard.
The main new result is a polynomial-time computable estimate of the first crossing time whose error is only $O(L)$ rounds, even when that crossing time is exponentially large. Consequently, for each choice of the non-horizon inputs, all but $O(L)$ integer horizons can be decided in polynomial time.
For the fixed target $x=1/2$ near the critical bias, the estimate can be sharpened to a constant error:
$$ \left| T(q)-\frac{\pi(3-q)}{\sqrt{6q-q^2-1}} \right|\leq128, \qquad 3-2\sqrt2<q\leq\frac15. $$
These results substantially narrow the remaining comparison problem, but do not decide the exceptional horizons.
Put
$$ A=\mu_Cd_C,\qquad B=\mu_Pd_P. $$
Both numbers are positive. The required volume inequality is equivalent to
$$ x_t\geq r, \qquad r=1-\kappa\frac{A+B}{B}. $$
The rational number $r$ has bit length $O(L)$: its construction uses a fixed number of rational arithmetic operations.
Because $\kappa\geq0$, we have $r\leq1$. If $r\leq0$, time $0$ satisfies the condition. Henceforth suppose $r>0$.
Write $a=1-q$ and denote the update map by $F_q$. Direct expansion gives
$$ F_q(x)-x=(1-x)h_q(x), $$
where
$$ h_q(x)=2a^2x^2+a(3q-1)x+q^2. $$
Equivalently, for $z=1-x$,
$$ 1-F_q(x)=az^2(2+a-2az). $$
The endpoint cases are immediate:
Suppose now that $0<q<1$. The original recurrence expresses $F_q(x)$ as a convex combination of $y^2$ and $1-(1-y)^2$, with $y=q+(1-q)x\in[0,1]$. Thus $F_q$ maps $[0,1]$ into itself. Moreover,
$$ F_q'(x)=2a(1-x)\bigl(2+a-3a(1-x)\bigr)>0 \qquad(0\leq x<1), $$
because the expression in parentheses is at least $2-2a=2q>0$.
Since $x_1=q^2>x_0$, applying strict monotonicity inductively proves
$$ 0=x_0<x_1<x_2<\cdots<1. $$
The last strict inequality follows also from the displayed formula for $1-F_q(x)$, which is positive when $x<1$.
Therefore the bounded-horizon question is exactly whether $x_H\geq r$. In particular, $r=1$ is unreachable at every finite time when $0<q<1$.
Define
$$ D(q)=q^2-6q+1, \qquad q_\star=3-2\sqrt2. $$
The discriminant of $h_q$ is $a^2D(q)$. Since $q_\star$ is irrational, rational input cannot satisfy $q=q_\star$.
If $0<q<q_\star$, the roots of $h_q$ are
$$ \alpha= \frac{1-3q-\sqrt{D(q)}}{4(1-q)}, \qquad \beta= \frac{1-3q+\sqrt{D(q)}}{4(1-q)}. $$
They satisfy $0<\alpha<\beta<1$. Indeed, $q_\star<1/3$, and
$$ (1-3q)^2-D(q)=8q^2>0 $$
proves positivity of both numerators. Also $D(q)<1$, so the numerator defining $\beta$ is less than $2$, whereas its denominator exceeds $8/3$.
Because $F_q(\alpha)=\alpha$ and $F_q$ is strictly increasing, every finite iterate lies strictly below $\alpha$. The increasing orbit has a limit $\ell\leq\alpha$. Continuity makes $\ell$ a fixed point; the only fixed points are $\alpha,\beta,1$, so $\ell=\alpha$.
If $q_\star<q<1$, then $D(q)<0$, hence $h_q$ is positive everywhere. The only fixed point in $[0,1]$ is $1$, so the same limit argument gives $x_t\to1$.
Thus, for $0<q<1$ and $0<r<1$,
$$ r\text{ is eventually reached} \quad\Longleftrightarrow\quad \begin{cases} r<\alpha,&q<q_\star,\\ \text{always},&q>q_\star. \end{cases} $$
These conditions are polynomial-time decidable. The sign of $D(q)$ identifies the regime. In the subcritical regime, putting
$$ W=1-3q-4(1-q)r $$
gives the exact equivalence
$$ r<\alpha \quad\Longleftrightarrow\quad W>0\ \text{and}\ W^2>D(q). $$
From now on, assume these tests establish that $0<r<1$ is reachable. Define its first crossing time by
$$ T=\min\{t\geq0:x_t\geq r\}. $$
Then $T$ exists, $T\geq1$, and the original answer is yes exactly when $H\geq T$.
Define the positive one-round increase on the interval $[0,r]$ by
$$ v(x)=F_q(x)-x=(1-x)h_q(x). $$
It is positive there: in the subcritical case $r<\alpha$, and in the supercritical case $h_q$ is everywhere positive.
Consider
$$ J(r)=\int_0^r\frac{dx}{v(x)}. $$
The following lemma controls its discrepancy from the integer crossing time.
Let $F$ be a continuously differentiable, nondecreasing map, and let $v(x)=F(x)-x>0$ on $[0,r]$. Suppose the orbit from $x_0=0$ reaches $r$, with first crossing time $T$. Then
$$ |T-J(r)| \leq 1+\int_0^r\frac{|v'(x)|}{v(x)}\,dx. $$
Consider an orbit interval starting at $a=x_t<r$, and truncate its endpoint at
$$ b=\min\{F(a),r\}. $$
Integration by parts gives
$$ \int_a^b\frac{dx}{v(x)} = \frac{b-a}{v(a)} - \int_a^b \frac{b-s}{v(s)} \frac{v'(s)}{v(s)}\,ds. $$
For $s\in[a,b]$, monotonicity of $F$ implies
$$ F(s)\geq F(a)\geq b. $$
Consequently,
$$ v(s)=F(s)-s\geq b-s, $$
and therefore
$$ 0\leq\frac{b-s}{v(s)}\leq1. $$
It follows that
$$ \left| \int_a^b\frac{dx}{v(x)} -\frac{b-a}{v(a)} \right| \leq \int_a^b\frac{|v'(s)|}{v(s)}\,ds. $$
There are $T-1$ complete orbit intervals before the last interval; each complete interval has $(b-a)/v(a)=1$. On the last interval this ratio is some $\theta\in(0,1]$. Summing over the partition of $[0,r]$ yields
$$ J(r)=T-1+\theta+E, \qquad |E|\leq\int_0^r\frac{|v'(x)|}{v(x)}\,dx. $$
Since $0\leq1-\theta<1$, the claimed bound follows. $\square$
Write the reduced fractions as
$$ q=\frac uv,\qquad r=\frac bc, $$
with positive denominators. In this section, the integer $v$ denotes the denominator of $q$; the function $v(x)$ retains its argument.
Let $N_v,N_c$ be the binary bit lengths of these denominators, and define
$$ K=10+6N_v+3N_c. $$
Both bit lengths are $O(L)$.
For $x\leq r<\alpha$,
$$ h_q'(x)<h_q'(\alpha)=-a\sqrt{D(q)}<0. $$
Since $h_q(x)>0$,
$$ v'(x)=-h_q(x)+(1-x)h_q'(x)<0. $$
Thus
$$ \int_0^r\frac{|v'(x)|}{v(x)}\,dx = \log\frac{v(0)}{v(r)}. $$
The positive rational number $v(r)$ has denominator dividing $v^2c^3$, so
$$ v(r)\geq\frac1{v^2c^3}. $$
Also $v(0)=q^2\leq1$. Hence
$$ \int_0^r\frac{|v'(x)|}{v(x)}\,dx \leq2\log v+3\log c. $$
Completing the square gives
$$ h_q(x) = 2a^2\left(x-\frac{1-3q}{4a}\right)^2-\frac{D(q)}8. $$
The positive rational number $-D(q)$ has denominator dividing $v^2$, so $-D(q)\geq1/v^2$. Since $1-r\geq1/c$,
$$ v(x)\geq\frac1{8v^2c} \qquad(0\leq x\leq r). $$
Also $v(x)\leq1$, because $F_q(x)\leq1$.
The polynomial $v$ has degree three, so $v'$ has at most two roots. Therefore $[0,r]$ can be partitioned into at most three intervals on which $v$ is monotone. On each such interval, the variation of $\log v$ is at most $\log(8v^2c)$. Consequently,
$$ \int_0^r\frac{|v'(x)|}{v(x)}\,dx \leq3\log(8v^2c). $$
Combining either bound with Lemma 1, and using $\log v<N_v$ and $\log c<N_c$, proves the uniform estimate
$$ \boxed{|T-J(r)|\leq K=O(L).} $$
This estimate does not depend on the numerical size of $T$.
The integral $J(r)$ has an explicit expression involving elementary functions.
Put
$$ U(x)=4ax+3q-1. $$
Then
$$ h_q(x)=\frac{U(x)^2-D(q)}8. $$
The partial fraction identity
$$ \frac1{(1-x)h_q(x)} = \frac1{1-x} + \frac{2a^2x+1-q^2}{h_q(x)} $$
follows by multiplying both sides by $(1-x)h_q(x)$. Furthermore,
$$ 2a^2x+1-q^2 = \frac12h_q'(x)+\frac{a(3-q)}2. $$
Thus
$$ J(r) = -\log(1-r) +\frac12\log\frac{h_q(r)}{q^2} +\frac{a(3-q)}2\int_0^r\frac{dx}{h_q(x)}. $$
Writing $U_0=U(0)$ and $U_r=U(r)$ gives the following formulas.
If $D(q)<0$, put $s=\sqrt{-D(q)}$. Then
$$ J(r)= -\log(1-r) +\frac12\log\frac{h_q(r)}{q^2} +\frac{3-q}{s} \left( \arctan\frac{U_r}{s} - \arctan\frac{U_0}{s} \right). $$
If $D(q)>0$, put $s=\sqrt{D(q)}$. Reachability gives $U_0<U_r<-s$, and
$$ J(r)= -\log(1-r) +\frac12\log\frac{h_q(r)}{q^2} +\frac{3-q}{2s} \log \frac{(U_r-s)(U_0+s)} {(U_r+s)(U_0-s)}. $$
All logarithm arguments are positive.
These formulas permit approximation of $J(r)$ with absolute error at most $1/4$ in polynomial time.
Here are the required size and precision checks:
$$ \frac1v\leq\sqrt{|D(q)|}\leq2. $$
$$ h_q(r)\geq\frac1{v^2c^2}. $$
$$ |U_r-s|\,|U_r+s|=8h_q(r), $$
while each factor is bounded above by an absolute constant. The same argument at $0$ uses $h_q(0)=q^2$.
Thus all arguments and intermediate nonzero divisors have magnitudes between $2^{-O(L)}$ and $2^{O(L)}$. A fixed number of arithmetic operations therefore requires only $O(L)$ working precision, with a sufficiently large constant, to attain the stated absolute error.
For completeness, the elementary functions needed here admit polynomial-time approximations at that precision:
$$ \log z = 2\sum_{j=0}^{\infty} \frac{w^{2j+1}}{2j+1}, \qquad w=\frac{z-1}{z+1}, $$
has $|w|\leq1/3$, so a linear number of terms in the requested precision suffices. The same series computes $\log2$.
$$ \arctan u = 2\arctan\frac{u}{1+\sqrt{1+u^2}} $$
reduces the argument below $1/2$. Its power series then converges geometrically. This also computes $\pi=4\arctan1$.
The rational arithmetic in these truncated series has polynomial bit complexity. Hence a dyadic rational $\widehat J$ satisfying
$$ |\widehat J-J(r)|\leq\frac14 $$
is computable in polynomial time.
The following answers are certified:
$$ H<\widehat J-K-\frac14 \quad\Longrightarrow\quad H<T, $$
and
$$ H\geq\widehat J+K+\frac14 \quad\Longrightarrow\quad H\geq T. $$
Both comparisons are exact rational comparisons computable in polynomial time, including when $H$ is encoded in binary.
The remaining interval has length $2K+1/2$ and contains at most $2K+2=O(L)$ integer horizons.
What this proves: a polynomial-time procedure decides all horizons outside an explicitly computable interval containing only $O(L)$ integers.
What it does not prove: a polynomial-time decision procedure for the horizons inside that interval.
For the fixed target $r=1/2$, the error can be bounded independently of input length.
We first give a sharper general estimate.
Under the assumptions of Lemma 1, suppose additionally that $v$ is twice continuously differentiable and
$$ |v'(x)|\leq\frac12, \qquad |v''(x)|\leq M \qquad(0\leq x\leq r). $$
Define
$$ \Phi(r)=J(r)+\frac12\log\frac{v(r)}{v(0)}. $$
Then
$$ |T-\Phi(r)| \leq 6\int_0^r\frac{v'(x)^2}{v(x)}\,dx +12M^2r^2+2Mr+3. $$
Consider a complete orbit interval $[a,a+v(a)]$ contained in $[0,r]$. Write
$$ v_i=v(a),\qquad k_i=v'(a), \qquad w(u)=\frac{v(a+v_i u)}{v_i} \quad(0\leq u\leq1). $$
The derivative bound gives $1/2\leq w(u)\leq3/2$. Taylor's theorem gives
$$ |w(u)-(1+k_i u)| \leq\frac12Mv_i u^2. $$
The increment of $\Phi$ over this interval is
$$ \int_0^1\frac{du}{w(u)} +\frac12\log w(1). $$
Replacing $w(u)$ by $1+k_i u$ changes the integral by at most $2Mv_i/3$, because both denominators are at least $1/2$. It changes the half-logarithm by at most $Mv_i/2$. Their sum is therefore at most $2Mv_i$.
For $|k|\leq1/2$,
$$ \int_0^1\frac{du}{1+ku} = 1-\frac k2+R, \qquad |R|\leq\frac23k^2, $$
using
$$ \frac1{1+ku}=1-ku+\frac{k^2u^2}{1+ku}. $$
Also $|\log(1+k)-k|\leq k^2$, obtained by integrating the bound $|s/(1+s)|\leq2|s|$. Consequently,
$$ \left| \int_0^1\frac{du}{1+ku} +\frac12\log(1+k)-1 \right| \leq2k^2. $$
The discrepancy of the complete increment of $\Phi$ from $1$ is therefore at most
$$ 2k_i^2+2Mv_i. $$
For every $x$ in that interval,
$$ k_i^2\leq2v'(x)^2+2M^2v_i^2. $$
Moreover,
$$ \frac23 \leq \int_a^{a+v_i}\frac{dx}{v(x)} \leq2. $$
Integrating the preceding inequality against $dx/v(x)$ yields
$$ k_i^2 \leq 3\int_a^{a+v_i}\frac{v'(x)^2}{v(x)}\,dx +6M^2v_i^2. $$
The complete intervals are disjoint, and their lengths satisfy
$$ \sum_i v_i\leq r, \qquad \sum_i v_i^2\leq r^2. $$
Summing their discrepancies gives the first three terms in the asserted bound.
Finally, on the last, possibly truncated interval,
$$ \Phi'(x)=\frac{1+v'(x)/2}{v(x)}>0. $$
Its increment is at most $5/2$: throughout that interval, $v(x)\geq v(a)/2$, and its length is at most $v(a)$. Its discrepancy from one round is thus at most $3$. This proves the lemma. $\square$
First,
$$ \frac16<q_\star<\frac7{40}, $$
because $D$ is decreasing on $[0,1]$ and
$$ D\left(\frac16\right)=\frac1{36}>0, \qquad D\left(\frac7{40}\right)=-\frac{31}{1600}<0. $$
Hence
$$ \frac45\leq a<\frac56. $$
For $z=1-x\in[1/2,1]$,
$$ F_q'(x)=2az(2+a-3az). $$
This is a concave quadratic in $z$. Its endpoint values exceed $1/2$:
$$ 4aq>\frac8{15}, \qquad a\left(2-\frac a2\right)\geq\frac{19}{15}. $$
Its maximum is at most
$$ \frac{(2+a)^2}{6} \leq\frac{289}{216}<\frac32. $$
Thus $|v'(x)|\leq1/2$.
Also,
$$ v''(x)=2a\bigl(6a(1-x)-(2+a)\bigr). $$
The bracket lies between $-2/5$ and $13/6$, so $|v''(x)|<4$. We may take $M=4$.
Put $s=\sqrt{-D(q)}$ and $b_0=(1-3q)/(4a)$. Then
$$ h_q(x)=2a^2(x-b_0)^2+\frac{s^2}{8}. $$
Since $h_q$ is convex and
$$ h_q(0)=q^2,\qquad h_q(1/2)=q, $$
we have $h_q(x)\leq q\leq1/5$ on $[0,1/2]$. Furthermore,
$$ \frac{h_q'(x)^2}{h_q(x)}\leq8a^2. $$
Using $v'=(1-x)h_q'-h_q$, we obtain
$$ \begin{aligned} \frac{v'(x)^2}{v(x)} &\leq 2(1-x)\frac{h_q'(x)^2}{h_q(x)} +\frac{2h_q(x)}{1-x}\\ &\leq16a^2+4q\\ &\leq\frac{536}{45}<12. \end{aligned} $$
Therefore
$$ \int_0^{1/2}\frac{v'(x)^2}{v(x)}\,dx\leq6. $$
Lemma 2 now gives
$$ |T-\Phi(1/2)| \leq36+48+4+3=91. $$
Since $v(1/2)=q/2$ and $v(0)=q^2$,
$$ \Phi(1/2)-J(1/2) = \frac12\log\frac1{2q}, $$
which lies between $0$ and $1$. Thus
$$ |T-J(1/2)|\leq92. $$
For $r=1/2$,
$$ U_r=1+q,\qquad U_0=3q-1,\qquad h_q(1/2)=q. $$
Hence
$$ J(1/2)= \log2+\frac12\log\frac1q +\frac{3-q}{s} \left( \arctan\frac{1+q}{s} - \arctan\frac{3q-1}{s} \right). $$
In the range $q_\star<q\leq1/5$, the first arctangent argument is positive and the second is negative. Therefore
$$ \arctan\frac{1+q}{s} - \arctan\frac{3q-1}{s} = \pi -\arctan\frac{s}{1+q} -\arctan\frac{s}{1-3q}. $$
For $u\geq0$, $0\leq\arctan u\leq u$. Since $1+q\geq1$, $1-3q\geq2/5$, and $3-q\leq3$, replacing the arctangent difference by $\pi$ changes its contribution by at most $21/2$.
The remaining logarithms have sum less than $7/2$, using $q>1/6$ and $\log z\leq z-1$. Consequently,
$$ \left| J(1/2)-\frac{\pi(3-q)}s \right|\leq14. $$
Together with the preceding section, this proves
$$ \boxed{ \left| T(q)-\frac{\pi(3-q)}{\sqrt{6q-q^2-1}} \right|\leq128 } $$
for every rational $q_\star<q\leq1/5$.
The displayed expression is approximable to absolute error $1/4$ in polynomial time by the methods of Section 4. Therefore, in this regime with target $1/2$, at most $258$ integer horizons remain undecided by this estimate, independently of input length.
Put $\delta=q-q_\star>0$. Factoring $-D(q)$ gives
$$ s^2=\delta(6-q-q_\star). $$
The constant-error estimate consequently implies
$$ \lim_{\substack{q\downarrow q_\star\\q\in\mathbb Q}} \sqrt{q-q_\star}\,T(q) = \frac{\pi(3-q_\star)}{\sqrt{6-2q_\star}} = \pi\,2^{1/4}. $$
Indeed, multiplying the bounded error by $\sqrt\delta$ makes it tend to zero, and the remaining coefficient is continuous at $q_\star$.
For $n\geq10$, define
$$ q_n= \frac{\lceil2^nq_\star\rceil+1}{2^n}. $$
Irrationality of $q_\star$ gives
$$ 2^{-n}<q_n-q_\star<2^{1-n}. $$
The ceiling can be computed in polynomial time by binary search, comparing dyadic rationals to $q_\star$ through the sign of $D$.
The upper-margin check is explicit:
$$ q_n< \frac7{40}+\frac1{512} < \frac9{50} < \frac15. $$
Thus the constant-error estimate applies and proves
$$ T(q_n)=\Theta(2^{n/2}). $$
To realize the target $r=1/2$ in the original inputs, take
$$ \mu_C=\mu_P=\frac12, \qquad d_C=d_P=1, \qquad \kappa=\frac14. $$
Taking $H_n=2^{n+10}$ gives total input length $\Theta(n)$ and includes the crossing. For example, the estimate implies
$$ T(q_n)\leq6\,2^{n/2}+128<H_n. $$
Hence exponentially long crossing times occur, while the crossing-time estimate itself remains polynomial-time computable. Long transients alone therefore do not establish computational hardness.
The unrestricted decision problem has been reduced to exact placement of the first crossing time within an explicitly computable interval containing $O(L)$ integers. For the fixed target $1/2$ near the phase transition, the interval contains only a constant number of integers.
However, a short uncertainty interval does not itself resolve its remaining integer comparisons. None of the estimates above determines whether an exceptional horizon satisfies $x_H\geq r$, including a potentially very close strict comparison.
The [cited stochastic paper](https://link.springer.com/article/10.1007/s00446-021-00396-5) studies random graph dynamics. Its probabilistic conclusions are not used to decide these exact deterministic comparisons.
A uniform polynomial-time algorithm for the exceptional horizons, or a hardness reduction exploiting them, remains unproved here.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial, mathematically sound partial results, but does not resolve the requested complexity classification.
The scalar reachability analysis, the two integral estimates, the polynomial-time approximation procedure, and the exponential-transient family check out. I found one minor overstatement in the numerical-conditioning discussion. The major outstanding requirement is explicitly acknowledged: exact decisions for the exceptional horizons remain unproved.
The appropriate status is partial, and the continuous problem remains unresolved.
The definitions $A=\mu_Cd_C$ and $B=\mu_Pd_P$ give strictly positive rational numbers. Rearranging the volume inequality correctly gives
$$ x_t\geq r, \qquad r=1-\kappa\frac{A+B}{B}. $$
A fixed number of rational arithmetic operations suffices to construct $r$, with bit length $O(L)$. The observations $r\leq1$ and immediate success when $r\leq0$ are correct.
I checked the polynomial identities
$$ F_q(x)-x=(1-x)h_q(x) $$
and
$$ 1-F_q(x)=a(1-x)^2\bigl(2+a-2a(1-x)\bigr), $$
with $a=1-q$. Both are correct.
The endpoint cases $H=0$, $q=0$, and $q=1$ are correctly handled. For $0<q<1$, the convex-combination argument establishes that $F_q$ maps $[0,1]$ into itself. The displayed derivative is correct and strictly positive for $x<1$. Consequently, the induction proving strict increase of the orbit is valid. The complement formula also proves that no finite iterate equals $1$.
Thus the bounded-horizon condition is correctly reduced to $x_H\geq r$, including equality, and $r=1$ is correctly excluded for finite horizons when $0<q<1$.
The discriminant, the critical value $q_\star=3-2\sqrt2$, and the formulas for $\alpha$ and $\beta$ are correct. The inequalities establishing
$$ 0<\alpha<\beta<1 $$
are valid. Strict monotonicity prevents the orbit from reaching $\alpha$ in finitely many steps. The monotone-limit and continuity argument therefore correctly proves convergence to $\alpha$ in the subcritical regime and to $1$ in the supercritical regime.
The resulting eventual-reachability conditions correctly distinguish $r<\alpha$ from $r=\alpha$. The exact rational test
$$ r<\alpha \quad\Longleftrightarrow\quad W>0\ \text{and}\ W^2>D(q) $$
is also correct: the sign condition is necessary before squaring.
Finding: This section establishes the stated reachability reduction rigorously.
The integration-by-parts identity has the correct sign and integrand. On each truncated orbit interval, nondecreasingness of $F$ gives
$$ F(s)\geq F(a)\geq b, $$
and hence
$$ 0\leq\frac{b-s}{v(s)}\leq1. $$
This justifies the interval error bound.
The intervals partition $[0,r]$. There are $T-1$ complete intervals, and the final interval contributes a ratio $\theta\in(0,1]$. Summing the interval bounds therefore proves
$$ |T-J(r)| \leq 1+\int_0^r\frac{|v'(x)|}{v(x)}\,dx. $$
The application satisfies the hypotheses: $F_q$ is continuously differentiable and increasing, $v$ is positive throughout $[0,r]$, and reachability has already been established.
Finding: Lemma 1 and its application are correct.
In the subcritical regime, the inequalities for $h_q'$ correctly imply $v'<0$ throughout $[0,r]$. Therefore the integral of $|v'|/v$ is exactly the logarithmic endpoint ratio.
The denominator bound for the positive rational number $v(r)$ is correct:
$$ v(r)\geq\frac1{v^2c^3}. $$
Here the reuse of $v$ as a denominator and as a function is explicitly explained, so it does not create a mathematical ambiguity.
In the supercritical regime, completing the square gives the stated formula. The rational separation bound
$$ -D(q)\geq\frac1{v^2} $$
and $1-r\geq1/c$ correctly yield the uniform positive lower bound on the increase function.
The cubic increase function has at most two derivative roots and thus at most three monotonicity intervals. The bound on the variation of $\log v$ follows on each interval. The constants are sufficient to obtain
$$ |T-J(r)|\leq K, \qquad K=10+6N_v+3N_c. $$
Finding: The uniform discrepancy estimate is proved, with the stated constants and dependence on input length.
I checked the partial-fraction identity, the numerator decomposition, and both antiderivative formulas. They are correct.
In the subcritical case, reachability implies
$$ U_0<U_r<-\sqrt{D(q)}. $$
This verifies that none of the logarithmic factors vanishes and that the displayed logarithm argument is positive.
The principal size bounds are also correct:
$$ \frac1v\leq\sqrt{|D(q)|}\leq2, \qquad h_q(r)\geq\frac1{v^2c^2}. $$
The product identity involving $U_r\pm s$, together with the constant upper bounds on those factors, establishes their stated separation from zero. The same reasoning applies at the initial endpoint.
These bounds control the conditioning of the formula. The elementary-function procedures described are sufficient for polynomial-time approximation: their argument reductions give geometric convergence, and polynomially many terms with polynomial-size rational arithmetic suffice. The exponentially large coefficient $1/s$ requires additional precision of order $O(L)$, which the stated working-precision allowance covers.
Accordingly, the claim that a dyadic approximation satisfying
$$ |\widehat J-J(r)|\leq\frac14 $$
can be computed in polynomial time is justified.
The sentence
“Thus all arguments and intermediate nonzero divisors have magnitudes between $2^{-O(L)}$ and $2^{O(L)}$.”
is too broad if “all arguments” includes arctangent inputs. Such an input can be zero.
For example, take $q=1/5$ and the reachable target $r=1/8$. Then
$$ U_r=4(1-q)r+3q-1=0, $$
so $U_r/s=0$.
This does not affect the approximation algorithm: arctangent is well defined and well conditioned at zero.
Minimum clarification: Restrict the asserted positive lower bound to the quantities that require separation from zero, and explicitly allow zero arctangent arguments.
The two horizon tests follow correctly from the approximation error and the discrepancy bound. In particular, the non-strict sufficient condition for a yes answer is valid:
$$ H\geq\widehat J+K+\frac14 \quad\Longrightarrow\quad H\geq T. $$
All these comparisons are exact rational comparisons, so binary encoding of $H$ creates no additional difficulty.
The stated uncertainty interval has length $2K+1/2$, and its asserted upper bound of $2K+2$ integer horizons is valid.
Finding: The output proves a polynomial-time procedure that decides every horizon outside an explicitly computable set of $O(L)$ consecutive candidates. It does not decide the candidates inside that set.
The proof’s bounds check out individually:
The final constant $3$ is conservative but valid. Combining these steps proves the lemma as stated.
Finding: Lemma 2 is correct.
The rational evaluations used to bracket $q_\star$ are correct. Consequently, the stated range for $a$ follows.
The endpoint and maximum bounds for the concave quadratic $F_q'$ establish $|v'|\leq1/2$. The displayed second derivative and its bounds establish that $M=4$ is admissible.
The identities
$$ h_q(0)=q^2, \qquad h_q(1/2)=q $$
are correct. Convexity gives the asserted upper bound on $h_q$. The estimate on $h_q'^2/h_q$ is valid, and the subsequent inequality has the correct numerical constant:
$$ 16a^2+4q\leq\frac{536}{45}<12. $$
Thus the integral bound is valid. Substituting into Lemma 2 gives exactly
$$ 36+48+4+3=91. $$
The logarithmic correction lies between $0$ and $1$, so the bound $|T-J(1/2)|\leq92$ follows.
Finding: The constant-error application is proved.
The substitutions for $U_r$, $U_0$, and $h_q(1/2)$ are correct. The arctangent identity applies with the stated signs.
The error bound $21/2$ for replacing the arctangent difference by $\pi$ is valid. The remaining logarithms have sum less than $7/2$, so the bound $14$ follows. Combining this with the previous discrepancy estimate gives a bound stronger than the claimed $128$, so the displayed constant-error theorem is valid.
The assertion that at most $258$ integer horizons remain uncertified by this estimate is also valid.
The factorization of $s^2$ and the limiting coefficient are correct, giving
$$ \lim_{\substack{q\downarrow q_\star\\q\in\mathbb Q}} \sqrt{q-q_\star}\,T(q) = \pi\,2^{1/4}. $$
For the family $q_n$, irrationality gives the strict dyadic-distance inequalities. Exact comparisons using $D$ support the claimed polynomial-time construction. The upper-margin check places every stated family member in the required regime.
The conclusion
$$ T(q_n)=\Theta(2^{n/2}) $$
follows from the proved constant-error estimate. The original input choices correctly realize $r=1/2$, and the supplied horizon has encoding length $\Theta(n)$ and exceeds the crossing time.
Finding: The exponential-transient example is sound. The output correctly avoids treating long transients as a hardness proof.
The major remaining requirement is the complexity classification itself.
An interval containing only $O(L)$ possible crossing times does not provide an algorithm for comparing $x_H$ with $r$ at those horizons. The corresponding horizons may be exponentially large. Neither integral estimate resolves exact equality or arbitrarily close strict comparisons there.
The output explicitly acknowledges this limitation. Its conclusions do not improperly invoke the stochastic theorem. The [cited paper](https://link.springer.com/article/10.1007/s00446-021-00396-5) concerns stochastic graph dynamics; it supplies no missing exact-comparison step in this write-up.
Minimum additional work required: Provide either a uniform polynomial-time exact decision procedure for the exceptional horizons, with bit-complexity and equality handling, or a valid hardness reduction for the specified problem. This requires additional mathematics, not an expositional correction.
The direction is promising because the established estimates are sound and sharply isolate the unresolved comparisons. The main target nevertheless remains unsettled.
⟨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.