Answer: —
Theorem 19 — class: algorithmic
Given an attack graph \(G=(A,R)\), a finite support \(T\) of ballot types \(t\in\{0,1\}^{2|A|}\), rational masses \(\mu_t\) summing to \(1\), a positive rational smoothing mass \(\delta\), and tolerance \(\eta>0\), compute a rational vector \(\hat{x}\in[0,1]^A\) with maximum residual at most \(\eta\) for \(x_a=r_a\prod_{b\in\operatorname{Att}(a)}(1-x_b)\), where \(r_a=p_a/(p_a+q_a+\delta)\), \(p_a=\sum_t\mu_t b_t^+(a)\), and \(q_a=\sum_t\mu_t b_t^-(a)\).
Let \(G=(A,R)\) be a finite directed attack graph with \(m=|A|\geq1\), \(R\subseteq A\times A\), and \(\operatorname{Att}(a)=\{b:(b,a)\in R\}\); self-attacks are allowed.
A society is given by its support: a list \(T\subseteq\{0,1\}^{2m}\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
The coordinates \(b_t^+(a),b_t^-(a)\) record positive and negative votes independently; both may equal \(1\), and both may equal \(0\).
Given binary rationals \(\delta>0\) and \(\eta>0\), define \(p_a=\sum_{t\in T}\mu_t b_t^+(a)\), \(q_a=\sum_{t\in T}\mu_t b_t^-(a)\), and \(r_a=p_a/(p_a+q_a+\delta)\). Zero positive-vote mass is allowed; an empty product equals \(1\).
Compute a rational vector \(\hat{x}\in[0,1]^A\) satisfying \(\max_{a\in A}|\hat{x}_a-r_a\prod_{b\in\operatorname{Att}(a)}(1-\hat{x}_b)|\leq\eta\). Let \(L\) be the total binary input length, including the graph, ballots, masses, smoothing mass, and tolerance.
Is this search problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time reductions?
For integer vote counts, Correia, Cruz and Leite state global convergence of iterative successive substitution from every interior initial vector; this is not a polynomial bound in binary input length ([2014](https://userweb.fct.unl.pt/~jleite/papers/ecai14a.pdf)).
Multiple simple-product models can exist even with four arguments ([Amgoud et al., 2017](https://arxiv.org/pdf/1705.03381)); the task permits any vector meeting the residual requirement.
No verified result located settles the complexity of this distribution-input residual search problem.
The general problem is $\mathrm{PPAD}$-complete under polynomial-time, solution-preserving search reductions. Hardness holds even with one ballot type, at most two attackers per argument, and fixed constants
$$
\delta=\eta=2^{-64}.
$$
This does not establish either requested unconditional alternative. A polynomial-time algorithm would give polynomial-time algorithms for every $\mathrm{PPAD}$ problem. Under the reduction convention specified below, $\mathrm{NP}$-hardness would imply $\mathrm{NP}=\mathrm{coNP}$.
I give a self-contained proof of this classification and two further results:
Thus the status remains partial.
If $\eta\geq1$, the zero vector immediately satisfies the requirement. The substantive question concerns arbitrary positive, binary-encoded tolerances.
Define
$$
F_a(x)=r_a\prod_{b\in\operatorname{Att}(a)}(1-x_b),
\qquad
F:[0,1]^A\longrightarrow[0,1]^A.
$$
The explicitly listed masses allow exact polynomial-time computation of $p_a$ and $q_a$. To see the bit-length bound, use the product of the listed denominators as a common denominator. Its binary length is at most the sum of their binary lengths. Adding the corresponding numerators increases length by at most a polynomial amount.
Computing
$$
r_a=\frac{p_a}{p_a+q_a+\delta}
$$
therefore also takes polynomial time and produces coefficients of polynomial binary length.
Because $p_a,q_a\geq0$ and $\delta>0$,
$$
0\leq r_a<1.
$$
In particular, $p_a=0$ gives $r_a=0$.
Each coordinate of $F$ is continuous. Every complementary factor lies in $[0,1]$, and an empty product is $1$. Hence $F$ maps the nonempty compact convex cube into itself. Brouwer’s fixed-point theorem supplies $x^*\in[0,1]^A$ with
$$
F(x^*)=x^*.
$$
For $u_i,v_i\in[0,1]$, the telescoping identity
$$
\prod_{i=1}^d u_i-\prod_{i=1}^d v_i
=
\sum_{i=1}^d
(u_i-v_i)
\left(\prod_{j<i}u_j\right)
\left(\prod_{j>i}v_j\right)
$$
implies
$$
\left|\prod_{i=1}^d u_i-\prod_{i=1}^d v_i\right|
\leq\sum_{i=1}^d|u_i-v_i|.
$$
Since every argument has at most $m$ distinct attackers,
$$
\|F(x)-F(y)\|_\infty\leq m\|x-y\|_\infty.
$$
Consequently,
$$
\|(x-F(x))-(y-F(y))\|_\infty
\leq(m+1)\|x-y\|_\infty.
$$
Choose a nonnegative integer $k$ such that
$$
2^{-k}\leq\frac{\min\{\eta,1\}}{m+1}.
$$
Round each coordinate of $x^*$ down to a multiple of $2^{-k}$. The resulting vector $\hat{x}$ remains in the cube and satisfies
$$
\|\hat{x}-F(\hat{x})\|_\infty
\leq(m+1)2^{-k}
\leq\eta.
$$
The binary encoding of $\eta$ ensures that $k=O(L+\log m)$ suffices. Thus every instance has a polynomial-length rational witness. Given such a witness, exact rational evaluation of all products and comparison with $\eta$ take polynomial time.
These facts establish totality and short, efficiently verifiable witnesses; they do not provide an algorithm for finding a witness.
We use the following established result: weak fixed-point approximation belongs to $\mathrm{PPAD}$ for a family of continuous self-maps that is polynomially computable on rational inputs and polynomially continuous. Here polynomial continuity means that each requested accuracy has a sufficient continuity radius of polynomial binary length. This is [Etessami and Yannakakis, Proposition 1(2)](https://www.inf.ed.ac.uk/publications/online/1164.pdf).
Both hypotheses hold:
$$
\frac{c}{m+1}
$$
has polynomial binary length and satisfies
$$
\|x-y\|_\infty<\frac{c}{m+1}
\quad\Longrightarrow\quad
\|F(x)-F(y)\|_\infty<c.
$$
The theorem returns a rational vector with residual strictly less than $\eta$, which satisfies the required non-strict inequality. Therefore the problem belongs to $\mathrm{PPAD}$.
We reduce from Pure-Circuit, which is $\mathrm{PPAD}$-complete by [Deligkas, Fearnley, Hollender, and Melissourgos, Theorem 2.1](https://arxiv.org/pdf/2209.15149).
Its variables receive labels in $\{0,1,\bot\}$. Every variable is the output of exactly one gate; the variables appearing within each gate are distinct. There are two gate types:
Decode target coordinates as follows:
The reduction must work for every vector satisfying the target residual inequalities.
Initially consider ideal primitive operations with coefficient $1$:
$$
U(z)=1-z,
\qquad
N(s,t)=(1-s)(1-t).
$$
They correspond to arguments having one and two attackers, respectively.
Multiplication is implemented by
$$
M(s,t)=N(U(s),U(t))=st.
$$
The two complement arguments are always distinct fresh vertices, including when $s=t$. This gadget has three primitive arguments and depth two.
Probabilistic OR is
$$
O(s,t)=1-(1-s)(1-t).
$$
Implement it by creating separate double-complement copies of $s$ and $t$, applying $N$ to these copies, and complementing the result. It has six primitive arguments and depth four. The copies ensure that the binary operation has two distinct attackers even when $s=t$.
Define
$$
\phi(z)=M(O(z,z),O(z,z))=(2z-z^2)^2.
$$
One application uses nine primitive arguments and has depth six. Moreover,
$$
\phi'(z)=4z(2-z)(1-z)\geq0
\qquad(z\in[0,1]),
$$
so $\phi$ is nondecreasing.
We prove
$$
\phi^{\circ8}(1/3)<1/100,
\qquad
\phi^{\circ8}(1/2)>99/100.
$$
The following exact calculations give successive strict upper bounds:
| Input $z$ | Exact $\phi(z)$ | Strict upper bound |
|---|---|---|
| $1/3$ | $25/81$ | $5/16$ |
| $5/16$ | $18225/65536$ | $9/32$ |
| $9/32$ | $245025/1048576$ | $1/4$ |
| $1/4$ | $49/256$ | $1/5$ |
| $1/5$ | $81/625$ | $1/7$ |
| $1/7$ | $169/2401$ | $1/14$ |
| $1/14$ | $729/38416$ | $1/50$ |
| $1/50$ | $9801/6250000$ | $1/100$ |
Each comparison follows by cross-multiplication of positive denominators. Monotonicity permits induction through the rows, proving the first bound.
For the second bound:
| Input $z$ | Exact $\phi(z)$ | Lower bound |
|---|---|---|
| $1/2$ | $9/16$ | $9/16$, equality |
| $9/16$ | $42849/65536$ | $13/20$, strict |
| $13/20$ | $123201/160000$ | $3/4$, strict |
| $3/4$ | $225/256$ | $7/8$, strict |
| $7/8$ | $3969/4096$ | $15/16$, strict |
| $15/16$ | $65025/65536$ | $99/100$, strict |
Thus $\phi^{\circ6}(1/2)>99/100$. Also,
$$
\phi(99/100)\geq\phi(15/16)>99/100,
$$
so two further iterations preserve the strict bound.
Set
$$
H(z)=\phi^{\circ8}(z),
\qquad
J(z)=1-H(1-z).
$$
Their primitive depths are at most $48$ and $50$, respectively.
The preceding bounds and monotonicity imply
$$
\begin{aligned}
z\leq1/3&\ \Longrightarrow\ H(z)<1/100,\\
z\geq1/2&\ \Longrightarrow\ H(z)>99/100,\\
z\leq1/2&\ \Longrightarrow\ J(z)<1/100,\\
z\geq2/3&\ \Longrightarrow\ J(z)>99/100.
\end{aligned}
$$
In particular, every $z\in[0,1]$ satisfies at least one of
$$
H(z)>99/100,
\qquad
J(z)<1/100.
$$
The first holds when $z\geq1/2$; the second holds when $z\leq1/2$.
Use one ballot type of mass $1$, voting positively and not negatively at every argument. Set
$$
\delta=\eta=2^{-64}.
$$
This gives the common coefficient
$$
r=\frac{1}{1+2^{-64}}.
$$
Every primitive argument has an equation
$$
x_v=rP_v(x),
$$
where $P_v$ is either $U$ or $N$.
Let $\hat{x}$ satisfy the target residual inequalities. Since $P_v(\hat{x})\in[0,1]$,
$$
\begin{aligned}
|\hat{x}_v-P_v(\hat{x})|
&\leq|\hat{x}_v-rP_v(\hat{x})|
+(1-r)P_v(\hat{x})\\
&\leq\eta+(1-r)
<2^{-63}.
\end{aligned}
$$
Fix the actual external input coordinates of an individual gadget, and evaluate its ideal circuit on those inputs. Compare the ideal values with the coordinates of $\hat{x}$.
The primitive sensitivity bounds are
$$
|U(s)-U(s')|=|s-s'|
$$
and
$$
|N(s,t)-N(s',t')|
\leq|s-s'|+|t-t'|.
$$
Writing $\varepsilon=2^{-63}$, induction on primitive depth gives the error bound
$$
E_d\leq(2^d-1)\varepsilon.
$$
Indeed, external inputs have comparison error zero. A primitive at depth $d$ contributes less than $\varepsilon$ local error and has at most two parents, each with error at most $E_{d-1}$.
For depth at most $50$, the output error is therefore less than
$$
2^{50}2^{-63}=2^{-13}<1/100.
$$
Consequently:
These ranges lie strictly inside the decoding intervals.
The comparison remains valid if the complete graph contains cycles. Each gadget is internally acyclic, and its actual external inputs are held fixed; no assumption is made about how those inputs satisfy their own equations.
For a source NOR gate, use the ideal output
$$
H(N(x_u,x_v))=H((1-x_u)(1-x_v)).
$$
Its primitive depth is at most $49$.
If both inputs decode to $0$, then
$$
(1-\hat{x}_u)(1-\hat{x}_v)\geq(9/10)^2=81/100\geq1/2.
$$
The ideal output exceeds $99/100$. By the error bound, the actual output exceeds $49/50$ and decodes to $1$.
If either input decodes to $1$, then
$$
(1-\hat{x}_u)(1-\hat{x}_v)\leq1/10\leq1/3.
$$
The ideal output is below $1/100$. The actual output is below $1/50$ and decodes to $0$, regardless of the other input’s label.
These are exactly the NOR requirements.
For a source PURIFY gate, use two separate circuits with ideal outputs
$$
H(x_u),
\qquad
J(x_u).
$$
If the input decodes to $0$, then $\hat{x}_u\leq1/10$. Both ideal outputs are below $1/100$, so both actual outputs decode to $0$.
If the input decodes to $1$, then $\hat{x}_u\geq9/10$. Both ideal outputs exceed $99/100$, so both actual outputs decode to $1$.
For an arbitrary input value:
Thus at least one output always has a pure label. The threshold value itself is covered by both statements.
Replace each source gate with its corresponding gadget. Identify final gadget outputs with the source output variables, and make all intermediate vertices fresh.
Every source variable is produced by exactly one gate, so no argument receives competing defining equations. Distinct primitive parents ensure that no operation depends on duplicate edges. Every argument has at most two attackers.
Each gadget has constant size. The constructed graph, its single ballot, and the fixed smoothing mass and tolerance therefore have polynomial total encoding length. Construction and threshold decoding take polynomial time.
Sections 6.1 and 6.2 show that every valid target residual vector decodes to a valid Pure-Circuit solution. Hence the problem is $\mathrm{PPAD}$-hard. Together with Section 2, this proves $\mathrm{PPAD}$-completeness.
A strongly connected component is a maximal vertex set in which every vertex can reach every other by a directed path.
Proposition. Suppose every strongly connected component is either:
Then the residual search problem is solvable in time polynomial in $m,\tau,L$. Arbitrarily many attacks between different components are allowed.
Contract each strongly connected component to one vertex. The resulting graph is acyclic: a directed cycle of distinct components would make their union strongly connected, contradicting maximality.
Process this acyclic graph in topological order. Thus, when processing a component $C$, all coordinates of its external attackers have already been selected.
For $a\in C$, compute exactly
$$
c_a=r_a
\prod_{b\in\operatorname{Att}(a)\setminus C}(1-\hat{x}_b).
$$
These coefficients satisfy
$$
0\leq c_a\leq r_a<1.
$$
If $C=\{a\}$ has no self-attack, set the temporary exact value to
$$
y_a=c_a.
$$
Otherwise, order the component cyclically as $a_1,\ldots,a_s$, including $s=1$ for a self-attacking singleton. Its equations are
$$
y_i=c_i(1-y_{i-1}),
\qquad
y_0=y_s.
$$
Define the affine maps
$$
f_i(z)=c_i(1-z).
$$
Each maps $[0,1]$ into itself. Substitution gives
$$
y_1=g(y_1),
\qquad
g=f_1\circ f_s\circ\cdots\circ f_2.
$$
For $s=1$, take $g=f_1$.
The composition has the form
$$
g(z)=\alpha+\beta z,
\qquad
\beta=(-1)^s\prod_{i=1}^s c_i.
$$
Since $|\beta|<1$, its unique possible fixed point is
$$
y_1=\frac{\alpha}{1-\beta}.
$$
It lies in $[0,1]$: the continuous function $g(z)-z$ is nonnegative at $0$ and nonpositive at $1$, because $g$ maps the interval into itself. The intermediate value theorem supplies a fixed point in the interval, and $1-\beta\neq0$ ensures uniqueness.
Compute the remaining coordinates by
$$
y_i=f_i(y_{i-1})
\qquad(2\leq i\leq s).
$$
The fixed-point equation for $g$ verifies the closing equation for $y_1$.
All these values are rational and computed using exact rational arithmetic.
Choose $k$ such that
$$
h=2^{-k}\leq\frac{\min\{\eta,1\}}2.
$$
After solving a component, round every temporary coordinate down to the dyadic grid of spacing $h$. Thus
$$
|\hat{x}_a-y_a|\leq h.
$$
For a component without an internal attack,
$$
|\hat{x}_a-F_a(\hat{x})|\leq h.
$$
For a cycle vertex with internal predecessor $b$, the previously selected external coordinates remain fixed, so
$$
F_a(\hat{x})=c_a(1-\hat{x}_b).
$$
Therefore
$$
\begin{aligned}
|\hat{x}_a-F_a(\hat{x})|
&=|\hat{x}_a-c_a(1-\hat{x}_b)|\\
&\leq|\hat{x}_a-y_a|
+c_a|\hat{x}_b-y_b|\\
&\leq(1+c_a)h
\leq2h
\leq\eta.
\end{aligned}
$$
This calculation also applies to a self-attacking singleton.
Later components cannot alter the residual of an earlier component: every attacker outside that earlier component precedes it in the component order. Hence all final residual inequalities hold.
Let $B$ bound the binary lengths of the precomputed $r_a$; Section 2 gives $B$ polynomial in $L$.
Every external coordinate is a dyadic with denominator $2^k$. Thus a coefficient $c_a$, containing at most $m$ such factors, has binary length
$$
O(B+mk).
$$
Composing $s$ affine maps increases rational length by at most the sum of the input coefficient lengths, up to polynomial overhead. More explicitly, if $c_i=u_i/v_i$, the affine constant and slope can both be represented with a denominator dividing $\prod_i v_i$. The denominator of the cycle fixed point is obtained by subtracting the corresponding slope numerator from that common denominator. Its binary length is therefore
$$
O\bigl(s(B+mk)\bigr).
$$
Computing the remaining cycle values and rounding them uses polynomial-time integer arithmetic. Rounding after each component prevents unbounded growth across components. Since
$$
k=O(L+1),
$$
the complete algorithm has polynomial running time.
This proves the proposition.
Corollary. Graphs with at most one attacker per argument admit polynomial-time computation of an exact rational fixed point.
Indeed, their components have the required form. Cycle coefficients are simply the original $r_a$. Outside cycles, each equation is either constant or unary affine. Along any outward path, at most $m$ original coefficients are introduced, so exact rational binary lengths remain polynomial. No rounding is needed in this special case.
The convergence statement in the question cannot by itself provide a polynomial bound in binary input length.
Proposition. There are valid instances with $m=\tau=1$ and input length $O(n)$ for which successive substitution from a fixed interior starting value requires more than $2^{n-2}$ iterations to satisfy the residual tolerance.
Proof. Take one self-attacking argument and one ballot of mass $1$ with positive vote $1$ and negative vote $0$. For an integer $n\geq3$, set
$$
\delta=\eta=2^{-n},
\qquad
r=\frac1{1+2^{-n}}.
$$
The equation is
$$
x=r(1-x).
$$
With one argument, both simultaneous and successive substitution use
$$
x^{(k+1)}=r(1-x^{(k)}).
$$
Choose the interior starting value
$$
x^{(0)}=1/4.
$$
Define its signed residual by
$$
d_k=(1+r)x^{(k)}-r.
$$
Direct substitution gives
$$
d_{k+1}=-rd_k.
$$
Since $r\geq2/3$,
$$
|d_0|=\frac{3r-1}{4}\geq1/4.
$$
Consequently,
$$
|d_k|=r^k|d_0|\geq\frac14r^k.
$$
Put $s=1-r$. Then
$$
0<s<2^{-n}.
$$
Bernoulli’s inequality, obtained by induction for integer $k\geq0$, gives
$$
r^k=(1-s)^k\geq1-ks.
$$
For $k\leq2^{n-2}$,
$$
r^k\geq3/4.
$$
Hence
$$
|x^{(k)}-r(1-x^{(k)})|
=|d_k|
\geq3/16
>2^{-n}
=\eta.
$$
The instance has binary length $O(n)$, but none of these iterations meets the tolerance. This proves the proposition.
The exact fixed point is nevertheless
$$
x^*=\frac{r}{1+r}=\frac1{2+2^{-n}},
$$
which is computable in polynomial time. Thus this is a lower bound for the substitution procedure, not for the search problem itself.
The classification establishes the equivalence
$$
\begin{gathered}
\text{This residual search problem has a polynomial-time algorithm}\\
\Longleftrightarrow\\
\text{Every $\mathrm{PPAD}$ search problem has a polynomial-time algorithm}.
\end{gathered}
$$
It does not prove either side.
For the $\mathrm{NP}$-hardness alternative, specify the reduction convention. Suppose there were polynomial-time procedures mapping each Boolean formula $\psi$ to a valid target instance and decoding every valid target solution into a correct satisfiability decision.
Then unsatisfiability would have polynomially verifiable certificates:
For an unsatisfiable formula, such a certificate exists by totality and the short-witness bound. For a satisfiable formula, none exists by correctness of decoding. Thus unsatisfiability would belong to $\mathrm{NP}$, implying
$$
\mathrm{NP}=\mathrm{coNP}.
$$
The same implication holds if decoding must return a satisfying assignment whenever one exists: accept the certificate precisely when the decoded output fails the direct satisfying-assignment check.
This is a conditional consequence, not a proof that $\mathrm{NP}$-hardness is impossible. Neither an unconditional polynomial-time algorithm for general graphs nor the requested $\mathrm{NP}$-hardness result is derived here.
⟨structured verdict parsed — rendered above⟩
The output establishes its claimed $\mathrm{PPAD}$-completeness result and both supplementary propositions. I found no false mathematical step or substantive gap in those arguments. It nevertheless remains partial relative to USER_TASK: it proves neither a general polynomial-time algorithm nor $\mathrm{NP}$-hardness under its stated reduction convention. The prover explicitly acknowledges this limitation.
Section 2.1 is correct.
The product of the explicitly encoded mass denominators has binary length bounded by their total encoding length. Converting the masses to this common denominator and summing polynomially many numerators requires only polynomial-length integer arithmetic. Incorporating the rational $\delta$ and computing each $r_a$ preserves polynomial bit complexity.
The bound
$$
0\leq r_a<1
$$
follows from $p_a,q_a\geq0$ and $\delta>0$. There is no division by zero. Zero positive-vote mass is handled correctly: $p_a=0$ implies $r_a=0$.
Independent positive and negative votes introduce no additional assumption into this computation.
Section 2.2 is correct.
The map $F$ is continuous and maps the nonempty compact convex cube $[0,1]^A$ into itself. These are the required hypotheses for Brouwer’s fixed-point theorem.
The displayed telescoping identity is correct, including the empty-product case. It gives
$$
\|F(x)-F(y)\|_\infty\leq m\|x-y\|_\infty.
$$
Self-attacks do not invalidate this bound: each attacker is still one distinct coordinate appearing once in the product.
Consequently, the residual map has Lipschitz constant at most $m+1$. Rounding an exact fixed point down to the stated dyadic grid therefore gives the required residual bound.
The choice
$$
k=O(L+\log m)
$$
is valid for a positive binary-encoded rational $\eta$. Thus the proof establishes polynomial-length witnesses, rather than merely rational witnesses of unspecified size. Exact verification of a supplied polynomial-length witness also takes polynomial time.
The separate observation for $\eta\geq1$ is correct.
The cited theorem is applicable.
[Etessami and Yannakakis, Proposition 1(2)](https://www.inf.ed.ac.uk/publications/online/1164.pdf) places weak fixed-point approximation in $\mathrm{PPAD}$ for polynomially computable, polynomially continuous families. Weak approximation there asks for a rational point in the domain with residual strictly below the supplied positive rational tolerance.
Both hypotheses are verified:
The domain is the unit cube, so no domain transformation is needed. A residual strictly below $\eta$ satisfies USER_TASK’s non-strict requirement.
Finding: membership is established.
The source problem is stated correctly.
[Deligkas, Fearnley, Hollender, and Melissourgos, Definition 1 and Theorem 2.1](https://arxiv.org/pdf/2209.15149) give precisely the NOR and PURIFY requirements used here. They also require distinct variables within each gate and exactly one producing gate for each variable.
The reduction correctly targets every valid target solution. It does not rely on selecting a preferred fixed point or residual solution.
Section 4.1 is correct.
The complement and binary product-of-complements primitives implement the displayed ideal functions. Fresh complement vertices make multiplication valid even when its two logical inputs coincide; the attack graph therefore never needs duplicate edges.
The probabilistic OR implementation has six primitive vertices and depth four. For the claimed nine-vertex implementation of $\phi$, its single OR output is reused as both logical inputs of the three-vertex multiplication gadget. The multiplication gadget’s two fresh complement vertices remain distinct. This agrees with the stated function and depth six.
The derivative
$$
\phi'(z)=4z(2-z)(1-z)
$$
is correct and nonnegative on $[0,1]$.
I rechecked every exact value and comparison in both tables. All are correct.
Monotonicity justifies propagating the successive upper and lower bounds through the iterations. The upper table establishes
$$
\phi^{\circ8}(1/3)<1/100.
$$
The lower table establishes
$$
\phi^{\circ6}(1/2)>99/100,
$$
and the stated comparison at $99/100$ correctly preserves this inequality through two further iterations.
The definitions of $H$ and $J$ give the stated depth bounds and threshold implications. In particular, the coverage argument includes $z=1/2$: both applicable inequalities hold there.
Finding: all amplification constants and ranges are verified.
Section 5 is correct.
The single mass-one ballot is a valid society and realizes the same coefficient at every vertex:
$$
r=\frac1{1+2^{-64}}.
$$
Both fixed parameters are positive binary rationals.
For every primitive,
$$
|\hat{x}_v-P_v(\hat{x})|
\leq\eta+(1-r)<2^{-63}.
$$
The strict inequality is valid because $1-r<2^{-64}$.
The two sensitivity inequalities hold throughout the cube. The depth induction therefore gives the claimed bound
$$
E_d\leq(2^d-1)2^{-63}.
$$
At depth at most $50$, the resulting error is below $2^{-13}$, which is below $1/100$. The conclusions placing actual outputs below $1/50$ or above $49/50$ follow.
The treatment of cycles in the assembled graph is also valid. Each individual gadget is acyclic once its actual external input coordinates are held fixed. The argument compares gadget values locally and does not assume global acyclicity or independence of those inputs.
Sections 6.1 and 6.2 verify all required cases.
For NOR, two decoded zero inputs put the ideal primitive output at least $81/100$, within the high amplification range. Any decoded one input puts it at most $1/10$, within the low range. The other input may be undecided in the latter case.
For PURIFY, decoded zero and one inputs force both outputs to the corresponding pure labels. For every remaining input value, the split at $1/2$ guarantees at least one pure output. Equality at the split is explicitly covered.
The error margins place the outputs strictly inside their decoding intervals, so there is no boundary ambiguity.
Section 6.3 is correct.
Exactly one producing source gate per variable prevents conflicting defining equations. Fresh intermediate vertices prevent unintended identifications. Distinct primitive attackers respect the graph’s set-valued edge representation.
The gadget sizes are constant, and the single ballot has length linear in the constructed number of vertices. The graph and fixed rational parameters have polynomial encoding length.
Threshold decoding is polynomial time and maps every valid residual vector to a source solution.
Finding: the claimed $\mathrm{PPAD}$-hardness, including the restricted family with one ballot and at most two attackers per argument, is established. Together with membership, this proves the stated $\mathrm{PPAD}$-completeness classification.
Section 7 is correct.
The component order follows the attack direction, so every external attacker is already assigned when its target component is processed.
The coefficients $c_a$ satisfy $0\leq c_a<1$. For a cycle, the displayed composition order correctly gives the closing equation for $y_1$. Its slope is
$$
\beta=(-1)^s\prod_{i=1}^s c_i,
$$
with $|\beta|<1$, including when some coefficient is zero. Hence $1-\beta$ is nonzero.
The interval-mapping property verifies the intermediate value theorem’s hypotheses and establishes that the unique affine fixed point lies in $[0,1]$. The remaining coordinates satisfy all cycle equations.
Rounding is also justified. External coordinates remain fixed, and each cycle equation has only one internal predecessor. The residual is therefore at most $2h\leq\eta$, including for a self-attacking singleton. Later components cannot change an earlier component’s attacker coordinates.
The bit-length analysis is polynomial. Rounding between components prevents successive products from carrying unrestricted exact denominators across the component graph.
The exact-solution corollary for graphs with at most one attacker is valid: their components have the required form, and outside cycles the dependency paths introduce only polynomially many original rational coefficients.
Section 8 is correct.
For the stated one-vertex instance,
$$
d_{k+1}=-rd_k
$$
follows directly from substitution. The initial residual bound is valid, and
$$
0<1-r<2^{-n}.
$$
Bernoulli’s inequality applies for every nonnegative integer iteration index. For all $k\leq2^{n-2}$, it yields the claimed residual lower bound.
For $n\geq3$,
$$
3/16>2^{-n},
$$
so none of those iterates meets the tolerance. The instance length is $O(n)$.
The prover correctly limits the conclusion to the substitution procedure. The displayed exact fixed point is correct and does not imply a lower bound for the search problem.
Section 9’s equivalence follows from the established completeness result under the stated polynomial-time search reductions.
The conditional implication concerning $\mathrm{NP}=\mathrm{coNP}$ is also correct under the explicitly specified decoder requirements. Totality supplies a short target witness for an unsatisfiable formula; universal decoder correctness excludes an accepting certificate for a satisfiable formula.
The satisfying-assignment variant likewise works under its stated requirement that every valid target solution decode to a satisfying assignment whenever one exists.
These implications do not establish either unconditional alternative in USER_TASK. They also do not cover unspecified broader reduction conventions.
Major — unresolved requested conclusion, Sections 1 and 9. The general polynomial-time versus $\mathrm{NP}$-hardness question remains unanswered. This is a limitation of what is established, not an error in the completeness proof.
The minimum clarification is already present: retain the explicit partial-status statement and keep the reduction convention attached to the conditional $\mathrm{NP}$-hardness discussion. Resolving USER_TASK itself requires an additional result establishing one requested alternative; no expositional repair of the existing argument supplies it.
No additional mathematical repair is needed for the results actually proved.
⟨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.