Introduction
We study the iterates of a fixed ReLU network of constant width: the discrete-time system
x k + 1 = N ( x k ) , x 0 ∈ [ 0 , 1 ] 4 , x_{k+1}=N(x_k), \qquad x_0\in[0,1]^4, x k + 1 = N ( x k ) , x 0 ∈ [ 0 , 1 ] 4 ,
where N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N:[0,1]^4\to[0,1]^4 N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 is a feedforward ReLU network of width 4. In other words, the object of study is a recurrent network that takes no per-step input: its input is its initial state x 0 x_0 x 0 , and its outputs are its states x k x_k x k . Iterating one fixed block is the pattern behind deep equilibrium models [5 ] and discretized Neural ODEs [14 , 24 ] . Residual and highway 40th Conference on Neural Information Processing Systems (NeurIPS 2026). networks [20 , 37 ] follow the same pattern with untied weights. We ask what the iterates of a width-4 block can compute, and what it costs to verify their behavior.
The correspondence. We prove that iterated width-4 ReLU networks are Turing complete on convex input regions, with iteration count playing the role of time. For every Turing machine (TM) M M M , we construct in polynomial time a single network N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N_M : [0,1]^4 \to[0,1]^4 N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 of width 4 and depth poly ( ∣ M ∣ ) \operatorname{poly}(|M|) poly ( ∣ M ∣ ) per iteration. Its iterates simulate M M M exactly on encoded tapes, and irreversibly flag every point of [ 0 , 1 ] 4 [0,1]^4 [ 0 , 1 ] 4 whose simulation reads an invalid digit (Theorem 3). Instantiated on a universal TM U U U , the construction yields a single fixed block N U N_U N U that simulates every machine on every input. The consequence is a hardness ladder along the single axis of the time bound (Theorem 7). At fixed width 4, bounded-time reachability is NP-complete for a unary bound, NEXP-complete for a binary bound and undecidable with no bound. NP-hardness of ReLU verification has been known since Katz et al. [ [23 ] ; the ladder shows that restricting the width does not restore tractability, since width 4 already suffices (§ 2.2 ). The hardness extends at width 6 to every common smooth activation (Theorem 10) and, through the correspondence of Duan et al. [ [15 ] , to discretized Neural ODEs at dimension 5 (Theorem 50).
The obstruction, in plain terms. A TM tape is an infinite binary string, and to feed it to a network we must store it in a single real number. Writing the tape in base 2 fails twice over: 0.0 1 ‾ 2 = 0.1 2 0.0\overline{1}_2 = 0.1_2 0.0 1 2 = 0. 1 2 , so two different tapes can be the same number, and reading off the first bit is a discontinuous operation. Writing it in base 4 using only the digits 1 and 3, a device going back to Siegelmann and Sontag [ [34 ] , repairs both defects. The encoding becomes injective, and the two possible leading digits are separated by a fixed gap, so a continuous piecewise-affine gadget can read the first digit. The price is that the valid encodings form a Cantor-like set D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 of measure zero, whereas verification asks a question about a full-dimensional convex region. The two domains cannot be reconciled by any continuous preprocessing: any continuous map from a convex set into D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 is constant (Proposition 11), and ReLU networks compute only continuous piecewise-affine maps. Since continuous encoding is impossible, our network detects: a fourth coordinate accumulates, one base-4 digit per iteration, a continuous certificate that irreversibly flags every input whose simulation reads an invalid digit. This online certificate is the ingredient that is new at the level of network construction. It is what makes every verification reduction below sound on convex regions.
Four theorems. Formal statements are in Section 2, proofs in the appendices.
(Th.3) Turing completeness of iterated width-4 networks on convex input spaces. For every TM M M M , a single polynomial-time-constructible width-4 ReLU network simulates M M M when iterated, exactly on encoded inputs, and irreversibly flags every point of the convex cube [ 0 , 1 ] 4 [0,1]^4 [ 0 , 1 ] 4 whose simulation reads an invalid digit.
(Th.7) Verification spectrum. Bounded-time reachability for iterated width-4 ReLU networks is NP-complete with unary time bound, NEXP-complete with binary time bound and RE-complete (undecidable) with no bound.
(Th.10) Robust verification at width 6 for smooth activations. For every continuous, non-polynomial, C 1 C^1 C 1 -at-a-point, polynomial-time-computable activation ρ \rho ρ , the δ \delta δ -robust verification problem (a promise problem with δ / 2 δ \delta/2^\delta δ / 2 δ gap) for width-6 ρ \rho ρ -networks is NP-complete.
(Th.50) Neural ODE consequences at dimension 5 (App.H). Through the correspondence of Duan et al. [ [15 ] between vanilla feedforward networks and splitting-method discretizations, the whole spectrum transfers to the discretized reachability of Neural ODEs at dimension 5.
Positioning. Table 1 situates the results; its mode column records whether a statement concerns a feedforward network or the iterates of one (a recurrent network). Siegelmann–Sontag Siegelmann [1999], Siegelmann and Sontag [1991, 1994] established TM universality for recurrent networks; in the variant relevant here, where the input is placed in the initial state, their construction requires fractal-encoded inputs and does not optimize width. (Their results with per-step input sequences carry no such restriction, but answer a different question.) Bounded-width approximation by feedforward networks was developed by Hanin and Sellke [ [19 ] , Park et al. [ [31 ] , Telgarsky [ [38 ] . Bournez et al. [ [11 ] contains two distinct results: a width-3 network simulating one TM step exactly on the fractal encoding set, and a separate width-12 uniform approximation theorem for arbitrary continuous piecewise-affine maps on convex domains. Theorem 3 improves neither width. It establishes a different property: a single width-4 network whose iterates are exact on encoded inputs and certify non-encoded inputs, uniformly over the whole convex cube [ 0 , 1 ] 4 [0,1]^4 [ 0 , 1 ] 4 (§ 3.1 explains why neither prior result yields this). Verification of ReLU networks was previously known to be NP-hard via SMT-style encodings Katz et al. [ [23 ] ; (Th. 7) lifts this to the full NP / NEXP / RE spectrum along the time bound, and (Th. 10) extends it to smooth activations at width 6. Training hardness is known up to ∃ \exists ∃ R-completeness Blum and Rivest [ [8 ] , Abrahamsen et al. [ [1 ] , Froese et al. [ [16 ] . The question we study is also the narrow-network analogue of a line of work on how expressive power grows with the number of sequential steps: Merrill and Sabharwal [ [28 ] show that transformers gain expressive power as the number of chain-of-thought steps grows, and ours is the same trade-off in a different architecture class, pushed to its limit. Finally, the Neural ODE consequence (Th. 50) uses the discrete-to-continuous correspondence Chen et al. [ [14 ] , Duan et al. [ [15 ] .1
Table 1. Positioning. The mode column distinguishes feedforward statements from statements about the iterates of a fixed block. (Th. 3) improves neither width of Bournez et al. [ [11 ] : it is the first exact TM simulation whose soundness extends to a full-dimensional convex input region, which is what the NEXP and undecidability statements require.
Model, problems, and main theorems
Networks, iteration, and verification
The model: iterated networks. The object of study in Theorems 3 and 7 is the discrete-time system x k + 1 = N ( x k ) x_{k+1}=N(x_k) x k + 1 = N ( x k ) obtained by iterating a fixed feedforward ReLU network N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N:[0,1]^4\to[0,1]^4 N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 of width 4. In other words, it is a weight-tied recurrent network that takes no per-step input: its input is its initial state and its outputs are its states. We write N [ t ] : = N ∘ N ∘ ⋯ ∘ N N^{[t]} := N \circ N \circ\cdots\circ N N [ t ] := N ∘ N ∘ ⋯ ∘ N for the t t t -fold composition. Which representation a result concerns is stated with the result: the unary-bound NP-completeness also holds for feedforward width-4 networks, by unrolling (Corollary 8), while the NEXP and RE statements concern the iterated representation, whose unrolled depth would be exponential or unbounded.
We consider neural networks with rational weights, with the “enhanced neuron” convention (e.g. Kidger and Lyons [ [25 ] ): a neuron is a map ψ ∘ ρ ∘ ϕ \psi\circ\rho\circ\phi ψ ∘ ρ ∘ ϕ with ϕ , ψ \phi,\psi ϕ , ψ affine and ρ \rho ρ the activation. We write N n , m , k ρ \mathcal{N}^{\rho}_{n,m,k} N n , m , k ρ for the class of feedforward networks with n n n inputs, m m m outputs, ρ \rho ρ activation, and bounded width k k k (i.e. every hidden layer has at most k k k neurons).
Verification problems. Our hardness results concern the following decision problems.
Definition 1 (Reachability). The reachability problem takes as input a ρ \rho ρ -network N : [ 0 , 1 ] d → [ 0 , 1 ] d N:[0,1]^d\to[0,1]^d N : [ 0 , 1 ] d → [ 0 , 1 ] d and two convex regions I n i t , A c c ⊆ [ 0 , 1 ] d \mathrm{Init},\mathrm{Acc}\subseteq[0,1]^d Init , Acc ⊆ [ 0 , 1 ] d specified by rational linear inequalities, and asks whether ∃ x ∈ I n i t , ∃ t ≥ 0 , N [ t ] ( x ) ∈ A c c \exists x\in\mathrm{Init},\ \exists t\geq0,\ N^{[t]}(x)\in\mathrm{Acc} ∃ x ∈ Init , ∃ t ≥ 0 , N [ t ] ( x ) ∈ Acc .
Here, the network is presented as a weighted graph, where the encoding of each hidden layer is the adjacency matrix, but every entry is the numerator-denominator-pair describing the rational weight. This formulation follows the standard one in the neural-network verification literature (see e.g. Katz et al., [23 ] , Wurm, [41 ] ).
Definition 2 (Bounded-time reachability). The T T T -bounded reachability problem takes the same input plus a time bound T ∈ N T \in\mathbb{N} T ∈ N (encoded either in unary or in binary) and asks whether ∃ x ∈ I n i t , ∃ t ≤ T , N [ t ] ( x ) ∈ A c c \exists x \in\mathrm{Init},\ \exists t \le T,\ N^{[t]}(x) \in\mathrm{Acc} ∃ x ∈ Init , ∃ t ≤ T , N [ t ] ( x ) ∈ Acc .
When ρ = ReLU \rho= \operatorname{ReLU} ρ = ReLU , both problems admit NP-membership for unary T T T : by the small-witness property for piecewise-affine systems (Lemma 36, classical), it suffices to guess a rational x x x of polynomial bit complexity and simulate T T T steps with exact rational arithmetic. For binary T T T , no such polynomial-time simulation exists; we recover NEXP-membership in § 4 .
Why reachability, why convex regions, why iterates
Robustness certification is exactly the reachability question we study: an ℓ ∞ \ell_\infty ℓ ∞ ball around a data point x ˉ \bar{x} x ˉ is an axis-aligned box, hence a convex polytope specified by rational linear inequalities, and the certification query is literally ∃ x ∈ I n i t : N ( x ) ∈ A c c \exists x \in\mathrm{Init}: N(x) \in\mathrm{Acc} ∃ x ∈ Init : N ( x ) ∈ Acc , with A c c \mathrm{Acc} Acc the region where the decision is wrong. This is the VNN-LIB and VNN-COMP specification format [13 ] , decided by complete verifiers such as Reluplex, Marabou and α , β \alpha,\beta α , β -CROWN [23 , 40 ] . Convex initial regions are therefore imposed by the application. Iteration matters wherever one block is applied repeatedly, above all in closed-loop verification of a neural controller, where the reachable set over k k k control steps is exactly N [ k ] ( I n i t ) N^{[k]}(\mathrm{Init}) N [ k ] ( Init ) . The practical reading of our results is that certification cost scales along depth, or number of steps, and not along width: at width 4, relaxing only the time bound climbs PTIME → \to → NP → \to → NEXP → \to → undecidable, and the remaining route to tractability is a restriction on the dynamics or on the parameters (§ 6 ).
Encoding Turing machines
We encode Turing-machine (TM) configurations using base-4 digits { 1 , 3 } \{1,3\} { 1 , 3 } , a Cantor-style encoding in the lineage of Siegelmann and Sontag [ [34 , 35 ] . Allowing all digits would create ambiguities like 0.1 3 ‾ 4 = 0.2 4 ‾ 4 0.1\overline{3}{}_4 = 0.2\overline{4}{}_4 0.1 3 4 = 0.2 4 4 ; restricting to digits 1 and 3 makes the presentation of a number unique, and resolves the discontinuity issues inherent to ReLU iteration. A word u = u 1 ⋯ u n ∈ { 0 , 1 } n u = u_1 \cdots u_n \in\{0,1\}^n u = u 1 ⋯ u n ∈ { 0 , 1 } n maps to enc { 1 , 3 } ( u ) = ∑ i = 1 n ( 2 u i + 1 ) 4 − i ∈ [ 0 , 1 ] \operatorname{enc}_{\{1,3\}}(u) = \sum_{i=1}^{n}(2u_i + 1)4^{-i} \in[0,1] enc { 1 , 3 } ( u ) = ∑ i = 1 n ( 2 u i + 1 ) 4 − i ∈ [ 0 , 1 ] . A configuration c = ( u , q , v ) c = (u,q,v) c = ( u , q , v ) (current state q q q , tape to the left of the head u u u (reversed), tape from the head onward v v v ) is encoded as
enc M ( c ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v ) , 0 , 0 ) ∈ [ 0 , 1 ] 4 . \operatorname{enc}_M(c) = \left(\operatorname{enc}_{\{1,3\}}(u),\operatorname{enc}_M(q,v),0,0\right) \in[0,1]^4. enc M ( c ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v ) , 0 , 0 ) ∈ [ 0 , 1 ] 4 .
where enc M ( q , v ) \operatorname{enc}_M(q,v) enc M ( q , v ) co-encodes the state and the right tape into a single base-4 string with enc M ( q ) \operatorname{enc}_M(q) enc M ( q ) as a constant-length prefix followed by enc { 1 , 3 } ( v ) \operatorname{enc}_{\{1,3\}}(v) enc { 1 , 3 } ( v ) , based on a packing borrowed from Bournez et al. [2025] that saves one coordinate over the naive encoding (enc( { 1 , 3 } ) ( u ) (\{1,3\})(u) ({ 1 , 3 }) ( u ) , enc{ 1 , 3 } ( v ) _{\{1,3\}}(v) { 1 , 3 } ( v ) , encM ( q ) _M(q) M ( q ) , ⋯ \cdots ⋯ ) which would force width 5. The third coordinate is a scratch register used by the simulator; the fourth is a validity register, both initially 0 (see § 4 ). We write Q Q Q for the state set of M M M , enc M ( Q ) ⊆ [ 0 , 1 ] \operatorname{enc}_M(Q) \subseteq[0,1] enc M ( Q ) ⊆ [ 0 , 1 ] for the prefix-encoded set of states, DDD 1 , 3 ⊆ [ 0 , 1 ] \operatorname{DDD}_{1,3} \subseteq[0,1] DDD 1 , 3 ⊆ [ 0 , 1 ] for the Cantor-like set of points whose base-4 expansion uses only digits { 1 , 3 } \{1,3\} { 1 , 3 } , τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω for the infinite input, step M \operatorname{step}_M step M for the map sending a configuration of M M M to the next one, and c t ( τ ) : = step M t ( c 0 ( τ ) ) c_t(\tau) := \operatorname{step}_M^t(c_0(\tau)) c t ( τ ) := step M t ( c 0 ( τ )) for the configuration at step t t t on an infinite tape τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω , with c 0 ( τ ) c_0(\tau) c 0 ( τ ) the initial configuration. The state prefix of x 2 x_2 x 2 consists of its first ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣ ⌉ \lvert q\rvert_4 = \lceil\log_4 \lvert Q\rvert\rceil ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣⌉ base-4 digits, and the post-state-prefix (or tape-suffix) portion of x 2 x_2 x 2 is the remainder. We say that a digit of x 1 x_1 x 1 , or of the tape-suffix of x 2 x_2 x 2 , is visited during the first k k k iterations of the network of Theorem 3 if it is exposed as the leading digit of its register at some iteration j < k j < k j < k . When x x x encodes a configuration, the visited digits are exactly the tape cells read by M M M ’s head.
Turing completeness of iterated width-4 networks on convex input spaces
Theorem 3 (Turing completeness on convex input spaces). For every deterministic Turing machine M M M over the binary alphabet, one can construct in polynomial time a single ReLU \operatorname{ReLU} ReLU network N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N_M : [0,1]^4 \to[0,1]^4 N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 of width 4 and depth D M = poly ( ∣ M ∣ ) D_M = \operatorname{poly}(\lvert M\rvert) D M = poly (∣ M ∣) , with a constant C M ∈ N C_M \in\mathbb{N} C M ∈ N , such that:
(i) (Faithful simulation, all time.) For every τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω and every t ≥ 0 , t \ge0, t ≥ 0 ,
N M [ C M t ] ( enc M ( c 0 ( τ ) ) ) = enc M ( step M t ( c 0 ( τ ) ) ) . N_M^{[C_Mt]}\left(\operatorname{enc}_M(c_0(\tau))\right) = \operatorname{enc}_M\left(\operatorname{step}_M^t(c_0(\tau))\right). N M [ C M t ] ( enc M ( c 0 ( τ )) ) = enc M ( step M t ( c 0 ( τ )) ) . (For finite inputs w w w , take τ = w ⋅ τ ′ \tau= w \cdot\tau' τ = w ⋅ τ ′ for any suffix τ ′ \tau' τ ′ ; M M M ’s behavior up to time T T T depends only on the first ≤ T \le T ≤ T symbols.)
(ii) (Online validity certificate. ) The fourth coordinate π 4 ( N M [ k ] ( x ) ) \pi_4(N_M^{[k]}(x)) π 4 ( N M [ k ] ( x )) is non-decreasing in k k k and bounded in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Moreover, for x = ( x 1 , x 2 , x 3 , x 4 ) x=(x_1,x_2,x_3,x_4) x = ( x 1 , x 2 , x 3 , x 4 ) with x 4 = 0 x_4=0 x 4 = 0 , we have π 4 ( N M [ k ] ( x ) ) = 0 \pi_4(N_M^{[k]}(x))=0 π 4 ( N M [ k ] ( x )) = 0 iff every leading base-4 digit of x 1 x_1 x 1 and of the post-state-prefix portion of x 2 x_2 x 2 visited by M M M ’s head during the first k k k iterations lies in { 1 , 3 } \{1,3\} { 1 , 3 } , and the state prefix of x 2 x_2 x 2 stays in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) along the trajectory. In particular, π 4 ( N M [ k ] ( x ) ) = 0 \pi_4(N_M^{[k]}(x))=0 π 4 ( N M [ k ] ( x )) = 0 for all k ≥ 0 k\ge0 k ≥ 0 whenever x 1 x_1 x 1 and the v v v -part of x 2 x_2 x 2 lie in D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 and the state prefix of x 2 x_2 x 2 encodes a valid state.
Part (i) alone holds at width 3 (Theorem 12, due to Bournez et al., [11 ] ).
The combination of (i) and (ii) is what makes the verification reductions work: property (i) gives soundness on encoded inputs, and property (ii) on the rest of the convex region. Plugging in halting problems of varying time complexity yields the hardness spectrum below.
Verification spectrum of iterated width-4 networks
Theorem 7 (Verification spectrum at width 4). For iterated width-4 ReLU networks N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N:[0,1]^4\to[0,1]^4 N : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 (the system of § 2.1 ), T T T -bounded reachability is:
(i) NP-complete when T T T is encoded in unary;
(ii) NEXP-complete when T T T is encoded in binary;
(iii) RE-complete (hence undecidable) with no time bound.
The hardness statements hold even when Init and Acc are axis-aligned hyperrectangles with rational endpoints.
Corollary 8 (Verification of feedforward width-4 ReLU networks). Verification of feedforward width-4 ReLU networks on convex Init, Acc ⊆ [ 0 , 1 ] 4 \subseteq[0,1]^4 ⊆ [ 0 , 1 ] 4 (deciding whether ∃ x ∈ I n i t : N ( x ) ∈ A c c \exists x\in\mathrm{Init}:N(x)\in\mathrm{Acc} ∃ x ∈ Init : N ( x ) ∈ Acc , a single application of N N N ) is NP-complete.
Robust verification at width 6 for smooth activations
Why “robust”. Exact verification of ρ \rho ρ -networks for smooth ρ \rho ρ such as tanh \tanh tanh quickly leaves classical complexity classes: the relevant decision problems involve transcendental constraints whose decidability rests on contested hypotheses [27 , 41 , 43 ] . The standard remedy is robust verification, which allows a fixed tolerance with a promise gap.
Definition 9 (δ \delta δ -robust verification). Given a ρ \rho ρ -network N : [ 0 , 1 ] d → [ 0 , 1 ] d N:[0,1]^d\to[0,1]^d N : [ 0 , 1 ] d → [ 0 , 1 ] d , convex regions Init, Acc ⊆ [ 0 , 1 ] d \subseteq[0,1]^d ⊆ [ 0 , 1 ] d , and a rational δ > 0 \delta>0 δ > 0 , the δ \delta δ -robust verification problem is the promise problem:
Output Yes if ∃ x ∈ I n i t \exists x\in\mathrm{Init} ∃ x ∈ Init with N ( x ) ∈ A c c + δ N(x)\in\mathrm{Acc}^{+\delta} N ( x ) ∈ Acc + δ ;
Output No if ∀ x ∈ I n i t \forall x\in\mathrm{Init} ∀ x ∈ Init , N ( x ) ∉ A c c + 2 δ N(x)\notin\mathrm{Acc}^{+2\delta} N ( x ) ∈ / Acc + 2 δ .
Promise: the input falls into one of these two cases.
Here A c c + δ = { y ∈ R d : dist ( y , A c c ) ≤ δ } \mathrm{Acc}^{+\delta}=\{y\in\mathbb{R}^d:\operatorname{dist}(y,\mathrm{Acc})\le\delta\} Acc + δ = { y ∈ R d : dist ( y , Acc ) ≤ δ } and dist \operatorname{dist} dist is Euclidean distance. The T T T -bounded variant considers N [ t ] ( x ) N^{[t]}(x) N [ t ] ( x ) for t ≤ T t\le T t ≤ T .
Theorem 10 (Robust verification at width 6). Let ρ : R → R \rho:\mathbb{R}\to\mathbb{R} ρ : R → R satisfy:
(H1) ρ \rho ρ is continuous and non-polynomial;
(H2) ρ \rho ρ is C 1 C^1 C 1 at some point with non-zero derivative;
(H3) ρ \rho ρ is polynomial-time computable, and admits a polynomial-time-computable Lipschitz constant on every bounded interval.
Then δ \delta δ -robust verification and δ \delta δ -robust T-bounded reachability (with T T T unary) for ρ \rho ρ -networks of width 6 are NP-complete2 ^{2} 2 .
Coverage of (H1)–(H3). (H1)–(H2) is the relaxation of differentiability of Kidger and Lyons [ [25 ] ; with (H3) they cover ReLU, leaky ReLU, tanh, sigmoid, GELU, Swish, ELU, softplus, arctan, the Gaussian and every analytic non-polynomial activation. Constructive ρ → \rho\to ρ → ReLU bit-complexity bounds are provided by Zhang et al. [ [44 ] ; the remaining cases follow from interval evaluation under (H3).
Proof sketch of Theorem 3
The proof of Theorem 3 has three modular components, illustrated in Figure 1 : a width-3 subnetwork that simulates one Turing-machine step on the { 1 , 3 } \{1,3\} { 1 , 3 } -base-4 encoding domain (Stage 1, at width 3, based on ideas from Bournez et al. [ [11 ] ); a width-2 subnetwork that produces a continuous encoding-validity certificate (Stage 2); and a combinator that propagates the certificate across iterations (Stage 3). The full network has width 4. We first identify the obstruction, then describe each stage; complete proofs are in Appendices B to D.
Figure 1. One iteration of the width-4 network of Theorem 3: x 1 x_1 x 1 holds the left tape, x 2 x_2 x 2 co-encodes the state and the right tape, x 3 x_3 x 3 is a scratch register, and x 4 x_4 x 4 accumulates the certificate ε \varepsilon ε via the max update, with ε ( x 1 , x 2 ) = 0 \varepsilon(x_1,x_2)=0 ε ( x 1 , x 2 ) = 0 iff the leading digits and the state prefix are valid (Remark 33).
The continuity obstruction, and why exactness is forced
Why exactness, in one sentence. Each simulated tape shift multiplies a coordinate by 4 (Lemma 31), so a per-step error ϵ \epsilon ϵ becomes about 4 k ϵ 4^k\epsilon 4 k ϵ after k k k iterations: an approximation accurate for k k k steps needs precision 4 − k 4^{-k} 4 − k , hence a network whose size grows with the time horizon. Theorem 7(ii)–(iii) quantify over exponential and unbounded k k k with one fixed finite network, so no approximation-based construction can reach them.
The obstruction. The existing ReLU-based simulations operate on the fractal set D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 (totally disconnected, Lebesgue measure 0), whereas verification asks for a trajectory from a convex initial region Init ⊆ [ 0 , 1 ] 4 \operatorname{Init}\subseteq[0,1]^4 Init ⊆ [ 0 , 1 ] 4 . The two domains are incompatible in a strong sense.
Proposition 11 (No continuous encoding). Every continuous map from a convex subset of R n \mathbb{R}^n R n into D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 is constant.
Proof. A convex set is connected, the continuous image of a connected set is connected, and D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 is totally disconnected, so the image is a single point.
ReLU networks realize only continuous piecewise-affine maps Arora et al. [ [2 ] , so no subnetwork can map Init onto valid encodings, and none can gate the simulation on the discontinuous predicate “is x x x a valid encoding?”. Bournez et al. [ [11 ] circumvent this by approximating the validity predicate uniformly, at width 12 and at the cost of exact iteration; the companion work Bournez et al. [2026] restricts inputs by 3-SAT preprocessing, which yields NP-hardness but no TM simulation. We instead realize a continuous certificate ε ( x ) \varepsilon(x) ε ( x ) that vanishes on valid encodings, is positive elsewhere and is non-decreasing along trajectories: any input which was never a valid encoding is flagged and stays flagged. The certificate occupies one extra coordinate, hence width 4.
Stage 1: width-3 TM step on encoded inputs. TM simulation at some fixed width has been known since Siegelmann and Sontag [1991]; Bournez et al. [2025] reach width 3, which we make fully explicit in Appendix § 9 and use as a black box.
Theorem 12 (Width-3 step simulation, inspired from Bournez et al. [2025]). For every Turing machine M M M over { 0 , 1 } \{0,1\} { 0 , 1 } , there exists a ReLU network g M ∈ N 3 , 3 , 3 R e L U g_M \in\mathcal{N}^{\mathrm{ReLU}}_{3,3,3} g M ∈ N 3 , 3 , 3 ReLU of depth poly ( ∣ M ∣ ) \operatorname{poly}(|M|) poly ( ∣ M ∣ ) such that, for every valid encoded configuration enc M ( c ) ∈ D D 1 , 3 × D D 1 , 3 , Q × { 0 } \operatorname{enc}_M(c) \in\mathbb{D}\mathbb{D}_{1,3} \times\mathbb{D}\mathbb{D}_{1,3,Q} \times\{0\} enc M ( c ) ∈ D D 1 , 3 × D D 1 , 3 , Q × { 0 } , g M ( enc M ( c ) ) = enc M ( step M ( c ) ) g_M(\operatorname{enc}_M(c)) = \operatorname{enc}_M(\operatorname{step}_M(c)) g M ( enc M ( c )) = enc M ( step M ( c )) , where D D 1 , 3 , Q ⊆ [ 0 , 1 ] \mathbb{D}\mathbb{D}_{1,3,Q} \subseteq[0,1] D D 1 , 3 , Q ⊆ [ 0 , 1 ] denotes the set of co-encodings of a state prefix in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) followed by an D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 -tape suffix, and the third coordinate is a scratch register reset to 0 between steps.
Theorem 12 treats the encoding domain as a set of exact rational points: each TM transition is an explicit affine map on the relevant cylinder of D D 1 , 3 × D D 1 , 3 , Q \mathbb{D}\mathbb{D}_{1,3} \times\mathbb{D}\mathbb{D}_{1,3,Q} D D 1 , 3 × D D 1 , 3 , Q , and the gaps between cylinders allow these maps to be assembled at width 3. Outside the encoded domain, g M g_M g M has no specified behavior, which is what forces the certificate: it is what lets us talk about verification on convex inputs rather than on the fractal encoding set.
Stage 2: continuous encoding-validity certificate. The new ingredient is a per-step error gadget err : [ 0 , 4 ] → [ 0 , 1 ] \operatorname{err} : [0,4] \to[0,1] err : [ 0 , 4 ] → [ 0 , 1 ] , continuous and piecewise affine, which vanishes exactly on [ 1 , 2 ] ∪ [ 3 , 4 ] [1,2] \cup[3,4] [ 1 , 2 ] ∪ [ 3 , 4 ] and is positive elsewhere. It can be implemented as a sum of two tents by the nested ReLU expression
err ( x ) = ReLU ( 3 − x − ReLU ( 5 − 2 x − ReLU ( 2 − x + ReLU ( 1 − x ) ) ) ) . \operatorname{err}(x) = \operatorname{ReLU}\left(3-x-\operatorname{ReLU}\left(5-2x-\operatorname{ReLU}\left(2-x+\operatorname{ReLU}(1-x)\right)\right)\right). err ( x ) = ReLU ( 3 − x − ReLU ( 5 − 2 x − ReLU ( 2 − x + ReLU ( 1 − x ) ) ) ) .
Applied to 4 x j 4x_j 4 x j , err \operatorname{err} err vanishes iff the leading base-4 digit of x j x_j x j lies in { 1 , 3 } \{1,3\} { 1 , 3 } (scheduling inside the width-4 network: Appendix § 10 ).
Proposition 13 (Per-step encoding-validity gadget). The function err 4 ( x ) : = err ( 4 ⋅ x ) \operatorname{err}_4(x) := \operatorname{err}(4 \cdot x) err 4 ( x ) := err ( 4 ⋅ x ) is continuous, non-negative, computable in constant depth inside the width-4 register network of Theorem 3, and vanishes precisely on the leading-digit { 1 , 3 } \{1,3\} { 1 , 3 } -cylinders of [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Stage 3: combining the stages, and proof of Theorem 3. The full width-4 network N M N_M N M assembles, at each iteration, a per-step certificate update followed by Stage 1’s TM step:
Apply the per-step error gadget err \operatorname{err} err to 4 x 1 4x_1 4 x 1 and to the leading digits of the tape-suffix portion of x 2 x_2 x 2 (Proposition 13; the state-prefix portion of x 2 x_2 x 2 is checked by the same gadget composed with a constant-depth slicing, Appendix § 10 ). Update x 4 ′ ← max { x 4 , ε ( x 1 , x 2 ) } x'_4 \leftarrow\max\{x_4,\varepsilon(x_1,x_2)\} x 4 ′ ← max { x 4 , ε ( x 1 , x 2 )} , where ε ( x 1 , x 2 ) \varepsilon(x_1,x_2) ε ( x 1 , x 2 ) is the maximum of the digit-error and the state terms (Remark 33). The maximum is computed as a + ReLU ( b − a ) a+\operatorname{ReLU}(b-a) a + ReLU ( b − a ) at width 2.
Apply Stage 1, the width-3 step simulation g M g_M g M , to ( x 1 , x 2 , x 3 ) (x_1,x_2,x_3) ( x 1 , x 2 , x 3 ) to obtain ( x 1 ′ , x 2 ′ , x 3 ′ ) (x'_1,x'_2,x'_3) ( x 1 ′ , x 2 ′ , x 3 ′ ) . The fourth register x 4 ′ x'_4 x 4 ′ is propagated unchanged through Stage 1 by an identity wire.
Each iteration of N M N_M N M has constant depth on top of g M g_M g M ; thus the per-iteration depth of N M N_M N M is D M = poly ( ∣ M ∣ ) D_M=\operatorname{poly}(|M|) D M = poly ( ∣ M ∣ ) , independent of any input length or time horizon.
Scheduling and width-4 bound. Each step is a sequence of register-layer updates (Definition 15 ), each modifying one of ( x 1 , … , x 4 ) (x_1,\ldots,x_4) ( x 1 , … , x 4 ) : the error gadgets are width-2 and sequentialized so that x 4 x_4 x 4 serves as accumulator while x 1 , x 2 x_1,x_2 x 1 , x 2 are read-only and x 3 x_3 x 3 holds scratch data; Stage 1 then updates x 1 , x 2 , x 3 x_1,x_2,x_3 x 1 , x 2 , x 3 and preserves x 4 x_4 x 4 through an identity wire (register form of register width 4, Remark 42).
Proof of Theorem 3. ε \varepsilon ε is non-negative and bounded by 1; the max update keeps x 4 ( k ) : = π 4 ( N M [ k ] ( x ) ) x_4(k):=\pi_4\left(N_M^{[k]}(x)\right) x 4 ( k ) := π 4 ( N M [ k ] ( x ) ) non-decreasing and in [ 0 , 1 ] [0,1] [ 0 , 1 ] . If x 1 x_1 x 1 and the tape-suffix of x 2 x_2 x 2 lie in D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 , and the state-prefix of x 2 x_2 x 2 is in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) , every leading digit visited stays in { 1 , 3 } \{1,3\} { 1 , 3 } and the state stays in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) along the trajectory (since g M g_M g M preserves valid encodings by Theorem 12 ); ε \varepsilon ε vanishes at every iteration, x 4 = 0 x_4=0 x 4 = 0 throughout, and N M [ t ] ( x ) = enc M ( c t ) N_M^{[t]}(x)=\operatorname{enc}_M(c_t) N M [ t ] ( x ) = enc M ( c t ) by induction, proving (i). Conversely, when a visited leading digit falls outside [ 1 , 2 ] ∪ [ 3 , 4 ] [1,2]\cup[3,4] [ 1 , 2 ] ∪ [ 3 , 4 ] or the state-prefix leaves enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) , the per-step error is positive at that iteration; x 4 x_4 x 4 becomes positive and stays so. Stage 2 checks before Stage 1 reads, so the simulator never operates on a forbidden digit while x 4 = 0 x_4 = 0 x 4 = 0 . (A fully worked example is given in Appendix D.§ 4 .) □
Verification spectrum of iterated width-4 networks
Proof of Theorem 7
Reductions: a uniform recipe. For each part of Theorem 7, we reduce a classical TM complexity problem Π \Pi Π to width-4 reachability. The reduction is identical across the three parts, so we describe it once. Let Π \Pi Π ask whether some Turing machine M M M accepts some input within some (problem-dependent) time bound. By Theorem 3, applied to M M M , we obtain a width-4 ReLU network N M N_M N M with the simulation and certificate properties. Recall that the second coordinate x 2 x_2 x 2 co-encodes the state (constant-length prefix enc M ( q ) \operatorname{enc}_M(q) enc M ( q ) of length ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣ ⌉ |q|_4 = \lceil\log_4 |Q| \rceil ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣ ⌉ ) and the right tape (§ 2 ). Define
Init = { x ∈ [ 0 , 1 ] 4 : enc M ( q 0 ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q 0 ) + 1 , x 3 = 0 , x 4 = 0 } . \operatorname{Init} = \left\{x \in[0,1]^4 : \operatorname{enc}_M(q_0) \le4^{|q|_4}x_2 \le\operatorname{enc}_M(q_0)+1,\ x_3=0,\ x_4=0\right\}. Init = { x ∈ [ 0 , 1 ] 4 : enc M ( q 0 ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q 0 ) + 1 , x 3 = 0 , x 4 = 0 } .
i.e. x 2 x_2 x 2 has the prefix enc M ( q 0 ) \operatorname{enc}_M(q_0) enc M ( q 0 ) of the initial state, the remaining digits of x 2 x_2 x 2 encode an arbitrary right tape, x 1 x_1 x 1 is unrestricted in [ 0 , 1 ] [0,1] [ 0 , 1 ] (left tape), and the scratch and validity registers are pinned to 0. Define
Acc = { x ∈ [ 0 , 1 ] 4 : enc M ( q F ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q F ) + 1 , x 4 ≤ 0 } , \operatorname{Acc} = \left\{x \in[0,1]^4 : \operatorname{enc}_M(q_F) \le4^{|q|_4}x_2 \le\operatorname{enc}_M(q_F)+1,\ x_4 \le0\right\}, Acc = { x ∈ [ 0 , 1 ] 4 : enc M ( q F ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q F ) + 1 , x 4 ≤ 0 } ,
i.e. the state-prefix of x 2 x_2 x 2 encodes the final state q F q_F q F . Both Init and Acc are convex and specified by rational linear inequalities (axis-aligned in x 2 , x 3 , x 4 x_2,x_3,x_4 x 2 , x 3 , x 4 ). The reduction maps ( M , T ) (M,T) ( M , T ) (or ( M ) (M) ( M ) in the unbounded case) to ( N M , Init , Acc , T ) (N_M,\operatorname{Init},\operatorname{Acc},T) ( N M , Init , Acc , T ) (or ( N M , Init , Acc ) (N_M,\operatorname{Init},\operatorname{Acc}) ( N M , Init , Acc ) . Correctness is by Theorem 3: a trajectory enters Acc iff x 4 = 0 x_4=0 x 4 = 0 throughout, i.e. every step is locally valid in the sense of Lemma 35 , and the state-prefix of x 2 x_2 x 2 encodes q F q_F q F at some iteration ≤ T \le T ≤ T . Equivalently, the trajectory enters Acc iff M M M accepts on some infinite binary tape τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω within the time bound, which matches the NP / NEXP / RE hardness sources by padding: acceptance on some infinite tape in T T T steps reduces to acceptance on some length-T T T prefix in T T T steps (see Lemma 37 ).
It remains only to choose Π \Pi Π for each part and verify the upper bound.
Part (i): unary T T T . Take Π \Pi Π to be “does M M M accept some w ∈ { 0 , 1 } n w \in\{0,1\}^n w ∈ { 0 , 1 } n within T T T steps?” with T T T unary, which is NP-complete by Cook–Levin applied to a TM with the standard polynomial slowdown Arora and Barak [ [3 ] . Hardness follows from the recipe above. NP-membership follows from Lemma 36 : a non-deterministic verifier guesses a rational x ∈ Init x \in\operatorname{Init} x ∈ Init of polynomial bit complexity and simulates N M N_M N M exactly for T ⋅ C M T \cdot C_M T ⋅ C M steps. With T T T unary, total time is poly ( ∣ N M ∣ , T ) \operatorname{poly}(|N_M|,T) poly ( ∣ N M ∣ , T ) .
Part (ii): binary T T T . Take Π \Pi Π to be Succinct-TM-Acceptance: “does M M M accept some w w w of length at most n n n in at most T T T steps?” with n , T n,T n , T binary. This problem is NEXP-complete by a standard padding argument from Succinct-SAT Arora and Barak [ [3 ] . Hardness follows from the recipe above with T ⋅ C M T \cdot C_M T ⋅ C M binary as the new time bound. For membership: a non-deterministic verifier guesses x ∈ Init x \in\operatorname{Init} x ∈ Init and t ≤ T ⋅ C M t \le T \cdot C_M t ≤ T ⋅ C M in time polynomial in the input size; simulation of N M N_M N M for t t t iterations takes time poly ( t , ∣ N M ∣ ) = 2 poly ( input ) \operatorname{poly}(t,|N_M|)=2^{\operatorname{poly}(\operatorname{input})} poly ( t , ∣ N M ∣ ) = 2 poly ( input ) because t t t may be exponential in the binary encoding ∣ T ∣ |T| ∣ T ∣ . The overall verifier runs in non-deterministic exponential time, hence NEXP-membership.
Part (iii): no time bound. Take Π \Pi Π to be the halting problem on the empty input: “does M M M halt on the empty word?”, which is RE-complete. The recipe gives N M N_M N M together with the singleton Init = { enc M ( c 0 ( ε ) ) } =\{\operatorname{enc}_M(c_0(\varepsilon))\} = { enc M ( c 0 ( ε ))} (equivalent to a degenerate hyperrectangle with rational endpoints). A trajectory from this single point reaches Acc iff M M M halts on the empty word. Membership in RE is a standard semi-decision procedure (simulate N M N_M N M until the trajectory enters Acc, accept if so). □
A note on the NEXP witness. The witness in Part (ii) encodes a TM input of length up to n n n as the point x ∈ Init x \in\operatorname{Init} x ∈ Init ; Remark 38 explains why this lands on NEXP rather than EXPTIME.
Two corollaries used in the sequel
Two consequences follow at no additional cost. By complementation, the dual problem “does N ( x ) ∈ Acc N(x) \in\operatorname{Acc} N ( x ) ∈ Acc hold for every x ∈ Init x \in\operatorname{Init} x ∈ Init ?” is coNP-complete (this is what complete verifiers like Marabou and α , β \alpha,\beta α , β -CROWN Katz et al. [ [23 ] , Wang et al. [ [40 ] certify), and by a gap construction using the certificate of Theorem 3, approximating min x ∈ Init , t ≤ T N [ t ] ( x ) \min_{x \in\operatorname{Init},\,t \le T}N^{[t]}(x) min x ∈ Init , t ≤ T N [ t ] ( x ) within additive error η < 1 / 4 \eta< 1/4 η < 1/4 inherits the full spectrum.
Corollary 14 (Universal verification and approximation hardness). For width-4 ReLU networks: (i) universal verification is coNP-complete; (ii) approximating worst-case output within η \eta η is NP-hard (unary T T T ), NEXP-hard (binary T T T ), and undecidable (no T T T ).
Robust verification at width 6 for smooth activations
Theorem 7 addresses ReLU. We extend the hardness to every common smooth activation at the cost of two additional units of width, in the robust framework of § 2.6 : exact verification for smooth ρ \rho ρ leaves classical complexity [27 , 43 , 42 ] , while the δ / 2 δ \delta/2\delta δ /2 δ promise gap [17 ] absorbs the ρ → R e L U \rho\to\mathrm{ReLU} ρ → ReLU approximation error and matches the finite-precision regime of numerical verifiers. Theorem 10 shows this relaxation does not help.
ReLU-register networks and ρ \rho ρ -emulation
The reduction from ReLU width 4 to ρ \rho ρ width 6 is most cleanly stated in a register normal form, in which each hidden layer updates a single coordinate. Every ReLU network of width w w w can be expressed in this form at a polynomial cost in depth.
Definition 15 (ReLU-register network). A ReLU-register network of register width k ≥ 1 k \ge1 k ≥ 1 and depth L L L is a composition F = A o u t ∘ R L ∘ ⋯ ∘ R 1 ∘ A i n F = A_{\mathrm{out}} \circ R_L \circ\cdots\circ R_1 \circ A_{\mathrm{in}} F = A out ∘ R L ∘ ⋯ ∘ R 1 ∘ A in , where A i n : R d → R k A_{\mathrm{in}} : \mathbb{R}^{d} \to\mathbb{R}^{k} A in : R d → R k and A o u t : R k → R d A_{\mathrm{out}} : \mathbb{R}^{k} \to\mathbb{R}^{d} A out : R k → R d are affine, and each layer R ℓ : R k → R k R_\ell: \mathbb{R}^{k} \to\mathbb{R}^{k} R ℓ : R k → R k updates a single coordinate j ℓ ∈ { 1 , … , k } j_\ell\in\{1,\ldots,k\} j ℓ ∈ { 1 , … , k } via ( R ℓ ( x ) ) j ℓ = ReLU ( a ℓ ⋅ x + b ℓ ) (R_\ell(x))_{j_\ell} = \operatorname{ReLU}(a_\ell\cdot x + b_\ell) ( R ℓ ( x ) ) j ℓ = ReLU ( a ℓ ⋅ x + b ℓ ) , leaving the others unchanged.
We work directly with this register form: it captures all ReLU networks (any standard ReLU network of width w w w and depth L L L embeds into a register network of register width 2 w 2w 2 w and depth O ( w L ) O(wL) O ( w L ) ; for our purposes, we only need that N M N_M N M is natively in register form of register width 4, see Remark 42 in Appendix F.1). The technical core of the section is the following emulation result, adapted from Kidger and Lyons [2020].
Lemma 16 (Per-layer ρ \rho ρ -emulation at width $k + 2). Let ρ : R → R \rho: \mathbb{R} \to\mathbb{R} ρ : R → R satisfy hypotheses (H1)-(H3) of Theorem 10. For every ReLU-register layer R : R k → R k R : \mathbb{R}^{k} \to\mathbb{R}^{k} R : R k → R k , every compact K ⊆ R k K \subseteq\mathbb{R}^{k} K ⊆ R k , and every η > 0 \eta> 0 η > 0 , there exists a ρ \rho ρ -network R ~ ∈ N k , k , k + 2 ρ \widetilde{R} \in\mathcal{N}^{\rho}_{k,k,k+2} R ∈ N k , k , k + 2 ρ of depth O ( 1 ) O(1) O ( 1 ) such that sup x ∈ K ∥ R ~ ( x ) − R ( x ) ∥ ∞ ≤ η \sup_{x \in K} \|\widetilde{R}(x) - R(x)\|_{\infty} \le\eta sup x ∈ K ∥ R ( x ) − R ( x ) ∥ ∞ ≤ η . The construction time is polynomial in the description size of R R R and in log ( 1 / η ) \log(1/\eta) log ( 1/ η ) .
Mechanism of the +2 overhead. The width k + 2 k + 2 k + 2 decomposes into k k k identity wires (one per register coordinate, each implemented by one enhanced ρ \rho ρ -neuron via the local-identity approximation of Kidger and Lyons [2020, Lemma 4.1], see Proposition 40) plus a ρ \rho ρ -subnetwork of width 2 that approximates the univariate non-linearity ReLU ( a ⋅ x + b ) \operatorname{ReLU}(a \cdot x + b) ReLU ( a ⋅ x + b ) on a bounded range (Kidger and Lyons [2020, Proposition 4.9]). The full proof of Lemma 16 is in Appendix F.2.
Composing per-layer emulators with a standard telescoping argument yields a network-level approximation result.
Lemma 17 (Network-level ρ \rho ρ -emulation). Let F : R d → R d F : \mathbb{R}^{d} \to\mathbb{R}^{d} F : R d → R d be a ReLU-register network of register width k k k and depth L L L , and let K ⊆ R d K \subseteq\mathbb{R}^{d} K ⊆ R d be compact. For every ϵ > 0 \epsilon> 0 ϵ > 0 , there exists a ρ \rho ρ -network F ~ ∈ N d , d , k + 2 ρ \widetilde{F} \in\mathcal{N}^{\rho}_{d,d,k+2} F ∈ N d , d , k + 2 ρ of depth O ( L ) O(L) O ( L ) , with sup x ∈ K ∥ F ~ ( x ) − F ( x ) ∥ ∞ ≤ ϵ \sup_{x \in K} \|\widetilde{F}(x) - F(x)\|_{\infty} \le\epsilon sup x ∈ K ∥ F ( x ) − F ( x ) ∥ ∞ ≤ ϵ , and constructible in time poly ( ∣ F ∣ , log ( 1 / ϵ ) ) \operatorname{poly}(|F|,\log(1/\epsilon)) poly ( ∣ F ∣ , log ( 1/ ϵ )) .
Proof of Theorem 3
We prove NP-membership and NP-hardness of δ \delta δ -robust verification for ρ \rho ρ -networks of width 6. The bounded-time variant (unary T T T ) follows by the same argument with depth scaled by T T T . Throughout this section and Appendix F, we write R R R for the acceptance region A c c \mathrm{Acc} Acc of Definition 9.
NP-membership. By Lemma 36 (applied to the ReLU-equivalent given by Lemma 16), a non-deterministic verifier can guess a rational x ∈ E x \in E x ∈ E of polynomial bit complexity. It then computes y ~ ≈ N ( x ) \tilde{y} \approx N(x) y ~ ≈ N ( x ) to precision δ / 4 \delta/4 δ /4 using polynomial-time evaluation of ρ \rho ρ and exact rational arithmetic for affine layers. By (H3), each ρ \rho ρ evaluation costs poly ( log ( 1 / δ ) ) \operatorname{poly}(\log(1/\delta)) poly ( log ( 1/ δ )) time and the polynomial-time-computable Lipschitz constant L ρ = poly ( input ) L_\rho= \operatorname{poly}(\operatorname{input}) L ρ = poly ( input ) on the relevant compact yields total iteration error ≤ T ⋅ L ρ T ⋅ ε s t e p \le T \cdot L^T_\rho\cdot\varepsilon_{\mathrm{step}} ≤ T ⋅ L ρ T ⋅ ε step . Choosing ε s t e p = δ / ( 4 T L T ) \varepsilon_{\mathrm{step}} = \delta/(4T L^T) ε step = δ / ( 4 T L T ) requires log ( 1 / ε s t e p ) = poly ( input ) \log(1/\varepsilon_{\mathrm{step}}) = \operatorname{poly}(\operatorname{input}) log ( 1/ ε step ) = poly ( input ) bits of precision per step. The verifier returns Yes iff y ~ ∈ R + 3 δ / 2 \tilde{y} \in R^{+3\delta/2} y ~ ∈ R + 3 δ /2 . On promise YES, dist ( y ~ , R ) ≤ δ + δ / 4 = 5 δ / 4 ≤ 3 δ / 2 \operatorname{dist}(\tilde{y},R) \le\delta+ \delta/4 = 5\delta/4 \le3\delta/2 dist ( y ~ , R ) ≤ δ + δ /4 = 5 δ /4 ≤ 3 δ /2 and the verifier accepts; on promise NO, dist ( y ~ , R ) > 2 δ − δ / 4 = 7 δ / 4 > 3 δ / 2 \operatorname{dist}(\tilde{y},R) > 2\delta- \delta/4 = 7\delta/4 > 3\delta/2 dist ( y ~ , R ) > 2 δ − δ /4 = 7 δ /4 > 3 δ /2 and the verifier rejects. NP-hardness via robust reduction from ReLU. Corollary 14 (or directly the proof of Theorem 7) establishes that the δ 0 \delta_0 δ 0 -robust verification problem is NP-hard for ReLU networks at width 4 for some fixed δ 0 > 0 \delta_0 > 0 δ 0 > 0 (concretely, the construction yields a separation of Ω ( 1 ) \Omega(1) Ω ( 1 ) between N ( x ) ∈ R N(x) \in R N ( x ) ∈ R and N ( x ) ∉ R + 1 N(x) \notin R^{+1} N ( x ) ∈ / R + 1 on the relevant compact). We reduce this to robust ρ \rho ρ verification at width 6.
Given a width-4 ReLU instance ( N , I n i t , R , δ ) (N,\mathrm{Init}, R, \delta) ( N , Init , R , δ ) , since N M N_M N M is natively in register form of register width 4 (Remark 42), apply Lemma 17 on the compact K = [ 0 , 1 ] 4 K = [0,1]^4 K = [ 0 , 1 ] 4 with precision ε = δ / 4 \varepsilon= \delta/4 ε = δ /4 to obtain a width-6 ρ \rho ρ -network N ~ \widetilde{N} N such that sup K ∥ N ~ − N ∥ ∞ ≤ δ / 4 \sup_K \lVert\widetilde{N} - N \rVert_\infty\leq\delta/4 sup K ∥ N − N ∥ ∞ ≤ δ /4 . Output the ρ \rho ρ -instance ( N ~ , I n i t , R + δ , δ / 4 ) (\widetilde{N},\mathrm{Init}, R^{+\delta}, \delta/4) ( N , Init , R + δ , δ /4 ) .
YES preservation. If the original instance is YES, then ∃ x ∈ I n i t \exists x \in\mathrm{Init} ∃ x ∈ Init with N ( x ) ∈ R + δ N(x) \in R^{+\delta} N ( x ) ∈ R + δ . Then dist ( N ~ ( x ) , R ) ≤ δ + δ / 4 = 5 δ / 4 \operatorname{dist}(\widetilde{N}(x), R) \leq\delta+ \delta/4 = 5\delta/4 dist ( N ( x ) , R ) ≤ δ + δ /4 = 5 δ /4 , so N ~ ( x ) ∈ ( R + δ ) + δ / 4 \widetilde{N}(x) \in(R^{+\delta})^{+\delta/4} N ( x ) ∈ ( R + δ ) + δ /4 . The output instance is YES.
NO preservation. If the original is NO, then ∀ x ∈ I n i t \forall x \in\mathrm{Init} ∀ x ∈ Init , dist ( N ( x ) , R ) > 2 δ \operatorname{dist}(N(x), R) > 2\delta dist ( N ( x ) , R ) > 2 δ , so dist ( N ~ ( x ) , R ) > 2 δ − δ / 4 = 7 δ / 4 \operatorname{dist}(\widetilde{N}(x), R) > 2\delta- \delta/4 = 7\delta/4 dist ( N ( x ) , R ) > 2 δ − δ /4 = 7 δ /4 . We need N ~ ( x ) ∉ ( R + δ ) + 2 ( δ / 4 ) = R + 3 δ / 2 \widetilde{N}(x) \notin(R^{+\delta})^{+2(\delta/4)} = R^{+3\delta/2} N ( x ) ∈ / ( R + δ ) + 2 ( δ /4 ) = R + 3 δ /2 , which holds since 7 δ / 4 > 3 δ / 2 7\delta/4 > 3\delta/2 7 δ /4 > 3 δ /2 . The output instance is NO.
The reduction is polynomial-time (Lemma 17 is polynomial-time constructible by Lemma 44 ); promise is preserved; YES/NO map correctly. Hence δ / 4 \delta/4 δ /4 -robust verification of ρ \rho ρ -networks at width 6 is NP-hard. NP-membership above gives completeness.
Two complements. The argument needs T T T unary: with T T T binary, the precision required is doubly exponential in the input, and a NEXP-style statement at binary T T T is open. The approximation hardness of Corollary 14 transfers to width-6 ρ \rho ρ -networks by the same reduction (Appendix § 13 .§ 3 ).
Discussion and open problems
What this paper establishes. The iterates of a single fixed ReLU network of width 4 simulate an arbitrary Turing machine, exactly on encoded inputs and with a certificate on the rest of the convex cube (Theorem 3); their verification spans the hierarchy from NP to undecidable along the time-bound axis (Theorem 7); the hardness extends to all standard smooth activations at width 6 in the robust framework (Theorem 10 ) and, through Duan et al. [2024], to Neural ODEs at dimension 5 (Theorem 50). The technical novelty over classical Turing-simulation theorems for narrow recurrent networks is a continuous encoding-validity certificate that resolves a continuity obstruction at the cost of one extra unit of width.
Practical implications. Depth, not width, is the axis along which verification cost scales superpolynomially (§ 2.2 ). This is consistent with the empirical observation that depth dominates the cost of complete verifiers [23 , 40 ] , although our worst-case analysis does not by itself explain solver behavior on trained networks.
Open problems. Four questions remain. (i) Width 2. Width 1 admits polynomial-time verification, widths 3 and 4 admit NP-completeness via fractal preprocessing Bournez et al. [2026], and width 4 obeys the full spectrum of Theorem 7; width 2 is open. (ii) Continuous-time simulation. Theorem 50 holds under splitting-method discretization; whether a Lipschitz piecewise-affine ODE admits TM simulation by its continuous flow, at any dimension, is open (Appendix § 15 .§ 4 ). (iii) Trained and constrained networks. Our construction is essentially expanding: each tape shift multiplies by 4. First, contractivity: non-expansive iterates (spectral norm at most 1, as enforced in deep equilibrium models [5 ] ) and normalizing flows cannot create digit resolution, and we believe that bounded-time reachability leaves the NEXP / RE regime under such a constraint. Second, parameterized complexity in the number of unstable neurons, the quantity that governs complete solvers in practice, rather than in width or depth. (iv) Beyond piecewise-affine activations. (H1)–(H3) cover the standard smooth activations but not softmax or attention. Extending to Transformer-style architectures is natural.
Acknowledgments and Disclosure of Funding
O. Bournez and J. Cohen acknowledge support from PGMO, and O. Bournez from ANR project OTC ANR-24-CE48-0335. A. Wurm acknowledges partial support from the BTU Graduate Research School. The authors declare no competing interests.
Notation and preliminaries
This appendix collects formal definitions used throughout the paper. The neural-network model itself is defined in § 2.1 ; here we record additional conventions and the verification problems considered.
Rational networks. Throughout, we restrict attention to rational neural networks and inputs: all parameters (weights, biases, activation slopes and hyperplane coefficients of Init and R R R ) are rational numbers. When convenient (here, in § 5 and in Appendix § 13 ) we write R R R for the acceptance region A c c \mathrm{Acc} Acc .
Verification and reachability problems. Fix an activation ρ : R → R \rho:\mathbb{R}\to\mathbb{R} ρ : R → R .
Definition 18 (ρ \rho ρ -Verification). The ρ \rho ρ -Verification problem is the following decision problem. Given: a neural network N : [ 0 , 1 ] d → [ 0 , 1 ] d ∈ N N d , d , ∗ ρ N:[0,1]^d\to[0,1]^d\in\mathcal{NN}^{\rho}_{d,d,*} N : [ 0 , 1 ] d → [ 0 , 1 ] d ∈ NN d , d , ∗ ρ and two convex regions I n i t , A c c ⊆ [ 0 , 1 ] d \mathrm{Init},\mathrm{Acc}\subseteq[0,1]^d Init , Acc ⊆ [ 0 , 1 ] d specified by linear inequalities. Decide: is there x ∈ I n i t x\in\mathrm{Init} x ∈ Init such that N ( x ) ∈ A c c N(x)\in\mathrm{Acc} N ( x ) ∈ Acc ?
Definition 19 (ρ \rho ρ -Bounded-Time Recurrent Reachability). The ρ \rho ρ -Bounded-Time Recurrent Reachability problem is the decision problem. Given: a neural network N : [ 0 , 1 ] d → [ 0 , 1 ] d ∈ N N d , d , ∗ ρ N:[0,1]^d\to[0,1]^d\in\mathcal{NN}^{\rho}_{d,d,*} N : [ 0 , 1 ] d → [ 0 , 1 ] d ∈ NN d , d , ∗ ρ , two convex regions I n i t , A c c ⊆ [ 0 , 1 ] d \mathrm{Init},\mathrm{Acc}\subseteq[0,1]^d Init , Acc ⊆ [ 0 , 1 ] d , and a time bound T ∈ N T\in\mathbb{N} T ∈ N encoded in unary (resp. binary, or unbounded). Decide: is there x ∈ I n i t x\in\mathrm{Init} x ∈ Init and t ≤ T t\leq T t ≤ T with N [ t ] ( x ) ∈ A c c N^{[t]}(x)\in\mathrm{Acc} N [ t ] ( x ) ∈ Acc ?
The robust variants (δ \delta δ -robust verification, δ \delta δ -robust bounded-time reachability) are defined in Definition 9 .
Width-3 simulation of Turing machines (after Bournez et al. [ [11 ] )
This appendix recalls the building block of our main theorem: a width-3 ReLU network simulating one step of a Turing machine on a base-4 encoding with digits in { 1 , 3 } \{1,3\} { 1 , 3 } . The result is adapted from Bournez et al. [ [11 ] .
Turing machine conventions
We use the following conventions throughout. A deterministic Turing machine is a tuple M = ( Q , Γ , δ , q 0 , q F ) M=(Q,\Gamma,\delta,q_0,q_F) M = ( Q , Γ , δ , q 0 , q F ) , where Q Q Q is a finite set of states; Γ = { 1 , 3 , B } \Gamma=\{1,3,B\} Γ = { 1 , 3 , B } is the tape alphabet, with B B B denoting the distinguished blank symbol; δ : Q × Γ → Q × Γ × { L , R } \delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\} δ : Q × Γ → Q × Γ × { L , R } is the transition function, where L L L and R R R denote a one-cell move of the head to the left and to the right, respectively; q 0 ∈ Q q_0\in Q q 0 ∈ Q is the initial state; and q F ∈ Q q_F\in Q q F ∈ Q is the unique accepting state. The choice of digits { 1 , 3 } \{1,3\} { 1 , 3 } for the binary input alphabet, instead of { 0 , 1 } \{0,1\} { 0 , 1 } , is consistent with the encoding of § 2.3 and avoids a separate treatment of the digit 0. Thus, a binary input w ∈ { 0 , 1 } n w\in\{0,1\}^n w ∈ { 0 , 1 } n is identified with the tape word w ′ ∈ { 1 , 3 } n w'\in\{1,3\}^n w ′ ∈ { 1 , 3 } n defined by w i ′ = 2 w i + 1 w'_i=2w_i+1 w i ′ = 2 w i + 1 .
A configuration of M M M is a triple ( u , q , v ) (u,q,v) ( u , q , v ) where q ∈ Q q\in Q q ∈ Q is the current state and u , v ∈ Γ ω u,v\in\Gamma^\omega u , v ∈ Γ ω encode the left and right halves of the (bi-infinite) tape, with the head positioned at the leftmost symbol of v v v . The set of configurations is denoted C M \mathcal{C}_M C M . The transition function δ \delta δ induces the single-step map step M : C M → C M \operatorname{step}_M:\mathcal{C}_M\to\mathcal{C}_M step M : C M → C M . A run on input w w w is the sequence of configurations c 0 , c 1 , c 2 , … c_0,c_1,c_2,\ldots c 0 , c 1 , c 2 , … where c 0 = ( B ω , q 0 , w ′ ⋅ B ω ) c_0=(B^\omega,q_0,w'\cdot B^\omega) c 0 = ( B ω , q 0 , w ′ ⋅ B ω ) and c t + 1 = step M ( c t ) c_{t+1}=\operatorname{step}_M(c_t) c t + 1 = step M ( c t ) . We say M M M accepts w w w in t t t steps if c t c_t c t has state q F q_F q F .
Remark 20. We will sometimes consider M M M acting on an infinite binary tape τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^\omega τ ∈ { 0 , 1 } ω instead of a finite input; the initial configuration is then c 0 ( τ ) = ( B ω , q 0 , τ ′ ⋅ B ω ) → τ ′ c_0(\tau)=(B^\omega,q_0,\tau'\cdot B^\omega)\to\tau' c 0 ( τ ) = ( B ω , q 0 , τ ′ ⋅ B ω ) → τ ′ where τ ′ = ( 2 τ 1 + 1 ) ( 2 τ 2 + 1 ) ⋯ ∈ { 1 , 3 } ω \tau'=(2\tau_1+1)(2\tau_2+1)\cdots\in\{1,3\}^\omega τ ′ = ( 2 τ 1 + 1 ) ( 2 τ 2 + 1 ) ⋯ ∈ { 1 , 3 } ω . Within T T T steps M M M visits at most T T T tape positions, so a finite input w w w of length ≥ T \geq T ≥ T behaves identically to any infinite extension w ⋅ τ ′ w\cdot\tau' w ⋅ τ ′ .
Encoding configurations
Let D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 denote the set of base-4 reals with digits in { 1 , 3 } \{1,3\} { 1 , 3 } , that is,
D 1 , 3 = { ∑ i = 1 ∞ a i 4 − i : a i ∈ { 1 , 3 } } ⊆ [ 0 , 1 ] . \mathbb{D}_{1,3}=\left\{\sum_{i=1}^{\infty}a_i4^{-i}:a_i\in\{1,3\}\right\}\subseteq[0,1]. D 1 , 3 = { i = 1 ∑ ∞ a i 4 − i : a i ∈ { 1 , 3 } } ⊆ [ 0 , 1 ] .
This is a Cantor-like fractal subset of [ 0 , 1 ] [0,1] [ 0 , 1 ] . The choice of digits in { 1 , 3 } \{1,3\} { 1 , 3 } rather than { 0 , 1 , 2 , 3 } \{0,1,2,3\} { 0 , 1 , 2 , 3 } creates uniform gaps between the leading-digit cylinders, which is what allows continuous gadgets to discriminate them. This trick is inspired from Siegelmann and Sontag [ [34 ] : see also discussions and references in Remark 28.
A configuration C ∈ C M C \in C_M C ∈ C M of a Turing machine M M M over alphabet Γ = { 1 , 3 , B } \Gamma= \{1,3,B\} Γ = { 1 , 3 , B } (with blank B B B ) is a triple ( u , q , v ) (u,q,v) ( u , q , v ) where q q q is a state and u , v ∈ Γ ω u,v \in\Gamma^\omega u , v ∈ Γ ω are the left and right halves of the tape. Following Bournez et al. [ [11 ] , we encode such a configuration into two reals by a map
ν : C M ⟶ ( [ 0 , 1 ] ∩ D ‾ 1 , 3 ) 2 , ν ( C ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v ) ) , \nu: C_M \longrightarrow\left([0,1] \cap\overline{\mathbb{D}}_{1,3}\right)^2,\qquad\nu(C) = \left(\operatorname{enc}_{\{1,3\}}(u),\operatorname{enc}_M(q,v)\right), ν : C M ⟶ ( [ 0 , 1 ] ∩ D 1 , 3 ) 2 , ν ( C ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v ) ) ,
where the second coordinate co-encodes state and right tape in base 4 4 4 : enc M ( q , v ) \operatorname{enc}_M(q,v) enc M ( q , v ) places a constant-length state prefix enc M ( q ) \operatorname{enc}_M(q) enc M ( q ) of length ∣ q ∣ 4 : = ⌈ log 4 ∣ Q ∣ ⌉ |q|_4 := \lceil\log_4 |Q| \rceil ∣ q ∣ 4 := ⌈ log 4 ∣ Q ∣ ⌉ ahead of enc { 1 , 3 } ( v ) \operatorname{enc}_{\{1,3\}}(v) enc { 1 , 3 } ( v ) . This packing keeps the working dimension at 2 2 2 ; the equivalent “naive” encoding ( u , v , q ) (u,v,q) ( u , v , q ) would require 3 3 3 dimensions. The width-4 4 4 network of Theorem 3 embeds ν ( C ) \nu(C) ν ( C ) into its first two coordinates, the third being a scratch register and the fourth a validity register (§ 2 ).
We need to write some particular continuous affine maps (CPAM) as particular narrow neural networks.
Some known statements
We review some known statements. We improve some of them, as we need to discuss very small width constructions, and also some effectivity considerations.
Theorem 21 (Arora et al. [ [2 ] ). Every CPAM f : R d → R f : \mathbb{R}^{d} \to\mathbb{R} f : R d → R can be represented by a N N d , 1 , ∗ R e L U \mathcal{NN}^{\mathrm{ReLU}}_{d,1,*} NN d , 1 , ∗ ReLU .
Note that this is easily extended to CPAMs with any finite output dimension. However, in practice, the question of the width or depth of the involved ReLU-net that performs a CPAM function is relevant. The article Hanin and Sellke [ [19 ] studies the numbers w min ( d i n , d o u t ) w_{\min}(d_{\mathrm{in}},d_{\mathrm{out}}) w m i n ( d in , d out ) , defined to be the minimal value of width w w w such that for every continuous function f : [ 0 , 1 ] d i n → R d o u t f : [0,1]^{d_{\mathrm{in}}} \to\mathbb{R}^{d_{\mathrm{out}}} f : [ 0 , 1 ] d in → R d out and every ε > 0 \varepsilon> 0 ε > 0 there is a ReLU net N N N with input dimension d i n d_{\mathrm{in}} d in , hidden layer widths at most w w w , and output dimension d o u t d_{\mathrm{out}} d out that ε \varepsilon ε -approximates f f f . The main result of Hanin and Sellke [ [19 ] is the following estimate for w min ( d i n , d o u t ) w_{\min}(d_{\mathrm{in}},d_{\mathrm{out}}) w m i n ( d in , d out ) .
Theorem 22 (Hanin and Sellke, [19 ] ). For every d i n , d o u t ≥ 1 d_{\mathrm{in}}, d_{\mathrm{out}} \ge1 d in , d out ≥ 1 , d i n + 1 ≤ w min ( d i n , d o u t ) ≤ d i n + d o u t d_{\mathrm{in}} + 1 \le w_{\min}(d_{\mathrm{in}},d_{\mathrm{out}}) \le d_{\mathrm{in}} + d_{\mathrm{out}} d in + 1 ≤ w m i n ( d in , d out ) ≤ d in + d out .
The following has been discussed:
Definition 23 (Max-min string, Hanin and Sellke, [19 ] ). A function g : R d i n → R d o u t g : \mathbb{R}^{d_{\mathrm{in}}} \to\mathbb{R}^{d_{\mathrm{out}}} g : R d in → R d out is a max-min string of length L ≥ 1 L \ge1 L ≥ 1 on d i n d_{\mathrm{in}} d in input variables and d o u t d_{\mathrm{out}} d out output variables if there exist affine functions a f 1 , … , a f L : R d i n → R d o u t a f_1,\ldots,a f_L : \mathbb{R}^{d_{\mathrm{in}}} \to\mathbb{R}^{d_{\mathrm{out}}} a f 1 , … , a f L : R d in → R d out such that
g = σ L − 1 ( a f L , σ L − 2 ( a f L − 1 , … , σ 2 ( a f 3 , σ 1 ( a f 1 , a f 2 ) ) … ) ) g = \sigma_{L-1}\left(a f_L,\sigma_{L-2}\left(a f_{L-1},\ldots,\sigma_2\left(a f_3,\sigma_1\left(a f_1,a f_2\right)\right)\ldots\right)\right) g = σ L − 1 ( a f L , σ L − 2 ( a f L − 1 , … , σ 2 ( a f 3 , σ 1 ( a f 1 , a f 2 ) ) … ) ) where each σ i \sigma_i σ i is either a coordinate-wise max or a min.
Proposition 24 (Width efficient computation of max-min string, Hanin and Sellke, [19 ] ). For every max-min string g g g on d i n d_{\mathrm{in}} d in input variables and d o u t d_{\mathrm{out}} d out output variables with length L L L and every compact K ⊆ R d i n K \subseteq\mathbb{R}^{d_{\mathrm{in}}} K ⊆ R d in , there exists a N N d i n , d o u t , d i n + d o u t R e L U \mathcal{NN}^{\mathrm{ReLU}}_{d_{\mathrm{in}},d_{\mathrm{out}},d_{\mathrm{in}}+d_{\mathrm{out}}} NN d in , d out , d in + d out ReLU and depth L L L that computes x ↦ g ( x ) x \mapsto g(x) x ↦ g ( x ) for every x ∈ K x \in K x ∈ K .
What we actually use
For our purposes, we only need the well-known fact that any one-dimensional continuous piecewise-affine map (CPAM) is expressible as a ReLU expression via the standard hinge representation. The specific gadgets used in the present paper (Lemmas 29 to 31) are constructed explicitly with width-2 implementations that do not appeal to a general width-optimal compilation. They can be seen as (sometimes optimized) particular instances of the following observation.
Lemma 25 (Compilation of bounded CPAMs). Let M > 0 M > 0 M > 0 and let f : [ 0 , M ] → R ≥ 0 f : [0,M] \to\mathbb{R}_{\ge0} f : [ 0 , M ] → R ≥ 0 be a continuous piecewise affine map with n n n breakpoints 0 < a 1 < a 2 < ⋯ < a n ≤ M 0 < a_1 < a_2 < \cdots< a_n \le M 0 < a 1 < a 2 < ⋯ < a n ≤ M . Then f f f is computed exactly on [ 0 , M ] [0,M] [ 0 , M ] by a ReLU network of width 2 2 2 and depth 2 n + 2 2n+2 2 n + 2 (including one affine output layer).
Proof. Let α 0 , … , α n \alpha_0,\ldots,\alpha_n α 0 , … , α n denote the slopes of f f f on the subintervals [ 0 , a 1 ] , [ a 1 , a 2 ] , … , [ a n , M ] [0,a_1],[a_1,a_2],\ldots,[a_n,M] [ 0 , a 1 ] , [ a 1 , a 2 ] , … , [ a n , M ] , set β 0 : = f ( 0 ) \beta_0:=f(0) β 0 := f ( 0 ) , and adopt the convention a 0 : = 0 a_0:=0 a 0 := 0 . The hinge decomposition (see e.g. Arora et al. [ [2 ] ) reads
f ( x ) = β 0 + α 0 x + ∑ i = 1 n ( α i − α i − 1 ) ReLU ( x − a i ) , x ∈ [ 0 , M ] . f(x)=\beta_0+\alpha_0x+\sum_{i=1}^{n}(\alpha_i-\alpha_{i-1})\operatorname{ReLU}(x-a_i),\qquad x\in[0,M]. f ( x ) = β 0 + α 0 x + i = 1 ∑ n ( α i − α i − 1 ) ReLU ( x − a i ) , x ∈ [ 0 , M ] .
Define the partial sums S j ( x ) : = β 0 + α 0 x + ∑ i = 1 j ( α i − α i − 1 ) ReLU ( x − a i ) S_j(x):=\beta_0+\alpha_0x+\sum_{i=1}^{j}(\alpha_i-\alpha_{i-1})\operatorname{ReLU}(x-a_i) S j ( x ) := β 0 + α 0 x + ∑ i = 1 j ( α i − α i − 1 ) ReLU ( x − a i ) for j ∈ { 0 , … , n } j\in\{0,\ldots,n\} j ∈ { 0 , … , n } , so that S 0 ( x ) = β 0 + α 0 x S_0(x)=\beta_0+\alpha_0x S 0 ( x ) = β 0 + α 0 x and S n = f S_n=f S n = f .
Positivity offset. Each S j S_j S j is continuous on the compact [ 0 , M ] [0,M] [ 0 , M ] , hence
C : = max 0 ≤ j ≤ n max x ∈ [ 0 , M ] max ( 0 , − S j ( x ) ) C:=\max_{0\le j\le n}\max_{x\in[0,M]}\max(0,-S_j(x)) C := 0 ≤ j ≤ n max x ∈ [ 0 , M ] max max ( 0 , − S j ( x ))
is finite (with explicit bound C ≤ ∣ β 0 ∣ + L M C\le|\beta_0|+LM C ≤ ∣ β 0 ∣ + L M , where L : = ∣ α 0 ∣ + ∑ i = 1 n ∣ α i − α i − 1 ∣ L:=|\alpha_0|+\sum_{i=1}^{n}|\alpha_i-\alpha_{i-1}| L := ∣ α 0 ∣ + ∑ i = 1 n ∣ α i − α i − 1 ∣ ). Set S ~ j ( x ) : = S j ( x ) + C ≥ 0 \widetilde{S}_j(x):=S_j(x)+C\ge0 S j ( x ) := S j ( x ) + C ≥ 0 and u j ( x ) : = ReLU ( x − a j ) u_j(x):=\operatorname{ReLU}(x-a_j) u j ( x ) := ReLU ( x − a j ) , so u 0 ( x ) = x u_0(x)=x u 0 ( x ) = x .
Construction. We build a width-2 network whose state after the j j j -th block of two ReLU layers equals ( u j ( x ) , S ~ j ( x ) ) (u_j(x),\widetilde{S}_j(x)) ( u j ( x ) , S j ( x )) .
Initialization (1 layer). The input x ∈ [ 0 , M ] x\in[0,M] x ∈ [ 0 , M ] is lifted by
x ⟼ ReLU ( x α 0 x + β 0 + C ) = ( u 0 ( x ) S ~ 0 ( x ) ) , x\longmapsto\operatorname{ReLU}\begin{pmatrix}x\\ \alpha_0x+\beta_0+C\end{pmatrix}
=\begin{pmatrix}u_0(x)\\ \widetilde{S}_0(x)\end{pmatrix}, x ⟼ ReLU ( x α 0 x + β 0 + C ) = ( u 0 ( x ) S 0 ( x ) ) ,
the equality holding because both coordinates are ≥ 0 \ge0 ≥ 0 on [ 0 , M ] [0,M] [ 0 , M ] (the first by hypothesis, the second by choice of C C C ).
Block j → j + 1 j\to j+1 j → j + 1 (2 layers). SUB-LAYER A. Apply
( u j S ~ j ) ⟼ ReLU ( u j − ( a j + 1 − a j ) S ~ j ) . \begin{pmatrix}u_j\\ \widetilde{S}_j\end{pmatrix}
\longmapsto
\operatorname{ReLU}\begin{pmatrix}u_j-(a_{j+1}-a_j)\\ \widetilde{S}_j\end{pmatrix}. ( u j S j ) ⟼ ReLU ( u j − ( a j + 1 − a j ) S j ) .
The second coordinate is preserved since S ~ j ≥ 0 \widetilde{S}_j\ge0 S j ≥ 0 . The first equals u j + 1 ( x ) u_{j+1}(x) u j + 1 ( x ) : on { x ≥ a j } \{x\ge a_j\} { x ≥ a j } , u j ( x ) = x − a j u_j(x)=x-a_j u j ( x ) = x − a j so ReLU ( u j − ( a j + 1 − a j ) ) = ReLU ( x − a j + 1 ) = u j + 1 ( x ) \operatorname{ReLU}(u_j-(a_{j+1}-a_j))=\operatorname{ReLU}(x-a_{j+1})=u_{j+1}(x) ReLU ( u j − ( a j + 1 − a j )) = ReLU ( x − a j + 1 ) = u j + 1 ( x ) ; on { x < a j } \{x<a_j\} { x < a j } , u j ( x ) = 0 u_j(x)=0 u j ( x ) = 0 and ReLU ( − ( a j + 1 − a j ) ) = 0 = u j + 1 ( x ) \operatorname{ReLU}(-(a_{j+1}-a_j))=0=u_{j+1}(x) ReLU ( − ( a j + 1 − a j )) = 0 = u j + 1 ( x ) (since x < a j < a j + 1 x<a_j<a_{j+1} x < a j < a j + 1 ).
SUB-LAYER B. Apply
( u j + 1 S ~ j ) ⟼ ReLU ( u j + 1 S ~ j + ( α j + 1 − α j ) u j + 1 ) = ( u j + 1 S ~ j + 1 ) . \begin{pmatrix}u_{j+1}\\ \widetilde{S}_j\end{pmatrix}
\longmapsto
\operatorname{ReLU}\begin{pmatrix}u_{j+1}\\ \widetilde{S}_j+(\alpha_{j+1}-\alpha_j)u_{j+1}\end{pmatrix}
=
\begin{pmatrix}u_{j+1}\\ \widetilde{S}_{j+1}\end{pmatrix}. ( u j + 1 S j ) ⟼ ReLU ( u j + 1 S j + ( α j + 1 − α j ) u j + 1 ) = ( u j + 1 S j + 1 ) .
The first coordinate is preserved since u j + 1 ≥ 0 u_{j+1}\ge0 u j + 1 ≥ 0 . The second argument equals S ~ j + 1 ( x ) \widetilde{S}_{j+1}(x) S j + 1 ( x ) , which is ≥ 0 \ge0 ≥ 0 by definition of C C C ; hence the ReLU acts as the identity.
Output (1 affine layer). After 2 n 2n 2 n ReLU layers in blocks, the state is ( u n ( x ) , S ~ n ( x ) ) = ( u n ( x ) , f ( x ) + C ) (u_n(x),\widetilde{S}_n(x))=(u_n(x),f(x)+C) ( u n ( x ) , S n ( x )) = ( u n ( x ) , f ( x ) + C ) . The affine map ( u , v ) ↦ v − C (u,v)\mapsto v-C ( u , v ) ↦ v − C yields f ( x ) f(x) f ( x ) .
Width and depth. Width is 2 throughout; depth is 1 + 2 n + 1 = 2 n + 2 1+2n+1=2n+2 1 + 2 n + 1 = 2 n + 2 .
Width-3 step simulation
Theorem 26 (Simulation of TM, Bournez et al., [11 ] ). Let M M M be a Turing machine with input alphabet Σ = { 1 , 3 } \Sigma=\{1,3\} Σ = { 1 , 3 } and tape alphabet Γ = { 1 , 3 , B } \Gamma=\{1,3,B\} Γ = { 1 , 3 , B } , and let C M = Γ ω × Q × Γ ω C_M=\Gamma^\omega\times Q\times\Gamma^\omega C M = Γ ω × Q × Γ ω be its configuration space. There exist a piecewise-affine function g M : R 2 → R 2 ∈ N N 2 , 2 , 3 ReLU g_M:\mathbb{R}^2\to\mathbb{R}^2\in\mathbb{N}\mathcal{N}_{2,2,3}^{\operatorname{ReLU}} g M : R 2 → R 2 ∈ N N 2 , 2 , 3 ReLU and an encoding map ν : C M → ( [ 0 , 1 ] ∩ D 1 , 3 ) 2 \nu:C_M\to([0,1]\cap\mathbb{D}_{1,3})^2 ν : C M → ([ 0 , 1 ] ∩ D 1 , 3 ) 2 such that the diagram below commutes:
C M → ⊢ C M ν ↓ ↓ ν R 2 → g M R 2 \begin{CD}
C_M @> \vdash>> C_M \\
@V \nu VV @VV \nu V \\
\mathbb{R}^2 @>g_M>> \mathbb{R}^2
\end{CD} C M ν ↓ ⏐ R 2 ⊢ g M C M ↓ ⏐ ν R 2 That is, g M ( ν ( C ) ) = ν ( C ′ ) g_M(\nu(C))=\nu(C') g M ( ν ( C )) = ν ( C ′ ) for every pair of configurations C ⊢ C ′ C\vdash C' C ⊢ C ′ in C M C_M C M .
:::`
Proof. Since the original argument in Bournez et al. [ [11 ] leaves several technical points implicit, we give a self-contained derivation, combining a structural decomposition of the TM step with the one-dimensional compilation of Lemma 25.
Decomposition into one-coordinate atomic updates. The transition ⊢ \vdash ⊢ of Bournez et al. [ [11 ] acts on the encoded pair ν ( C ) ∈ [ 0 , 1 ] 2 \nu(C)\in[0,1]^2 ν ( C ) ∈ [ 0 , 1 ] 2 through a finite sequence of atomic operations: read the leading base-4 digit of the active half-tape (Lemma 30), branch on the state-symbol pair via a constant-depth case split on the finitely many such pairs, write the new symbol, shift the head, update the state prefix. Each atomic operation modifies exactly one of the two encoded coordinates y 1 = enc { 1 , 3 } ( u ) y_1=\operatorname{enc}_{\{1,3\}}(u) y 1 = enc { 1 , 3 } ( u ) , y 2 = enc M ( q , v ) y_2=\operatorname{enc}_M(q,v) y 2 = enc M ( q , v ) and reduces, after the case split, to a continuous piecewise-affine map of one variable with O M ( 1 ) O_M(1) O M ( 1 ) breakpoints (the gadgets of Lemmas 30 and 31 are particular instances). Since the number of atomic operations depends only on M M M , the construction yields
g M = ϕ K ∘ ⋯ ∘ ϕ 1 , g_M=\phi_K\circ\cdots\circ\phi_1, g M = ϕ K ∘ ⋯ ∘ ϕ 1 ,
where K K K depends on M M M and each ϕ i : R 2 → R 2 \phi_i:\mathbb{R}^2\to\mathbb{R}^2 ϕ i : R 2 → R 2 has the form ( y 1 , y 2 ) ↦ ( y 1 , ψ i ( y 2 ) ) (y_1,y_2)\mapsto(y_1,\psi_i(y_2)) ( y 1 , y 2 ) ↦ ( y 1 , ψ i ( y 2 )) , or ( y 1 , y 2 ) ↦ ( ψ i ( y 1 ) , y 2 ) (y_1,y_2)\mapsto(\psi_i(y_1),y_2) ( y 1 , y 2 ) ↦ ( ψ i ( y 1 ) , y 2 ) , with ψ i \psi_i ψ i a 1D CPAM taking values in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
One atomic update fits in width 3. Take the first form (the second is symmetric). Lemma 25 provides a width-2 ReLU subnetwork computing ψ i \psi_i ψ i , internally maintaining a 2-register state (staircase variable and shifted partial sum). We place these two registers in coordinates 2 and 3 of the ambient width-3 network, while coordinate 1 carries y 1 y_1 y 1 through every ReLU layer via ReLU ( y 1 ) = y 1 \operatorname{ReLU}(y_1)=y_1 ReLU ( y 1 ) = y 1 (valid since y 1 ∈ [ 0 , 1 ] ⊆ R ≥ 0 y_1\in[0,1]\subseteq\mathbb{R}_{\geq0} y 1 ∈ [ 0 , 1 ] ⊆ R ≥ 0 ). A constant-depth ReLU junction at the end of the block extracts ψ i ( y 2 ) \psi_i(y_2) ψ i ( y 2 ) into coordinate 2, zeros coordinate 3, and preserves y 1 y_1 y 1 in coordinate 1, restoring the layout ( y 1 , ψ i ( y 2 ) , 0 ) (y_1,\psi_i(y_2),0) ( y 1 , ψ i ( y 2 ) , 0 ) required at the entry of ϕ i + 1 \phi_{i+1} ϕ i + 1 . (See Figure 2 for an illustration).
Figure 2. Width-3 block computing ( y 1 , y 2 , y 3 ) ↦ ( y 1 , ψ i ( y 2 ) , 0 ) (y_1,y_2,y_3)\mapsto(y_1,\psi_i(y_2),0) ( y 1 , y 2 , y 3 ) ↦ ( y 1 , ψ i ( y 2 ) , 0 ) . Coordinates 2–3 host the width-2 subnetwork of Lemma 25 (staircase + shifted partial sum); coordinate 1 carries y 1 y_1 y 1 through each layer via ReLU ( y 1 ) = y 1 \operatorname{ReLU}(y_1)=y_1 ReLU ( y 1 ) = y 1 on [ 0 , 1 ] [0,1] [ 0 , 1 ] . A final constant-depth junction outputs ψ i ( y 2 ) \psi_i(y_2) ψ i ( y 2 ) on coordinate 2 and resets coordinate 3 to 0.
Concatenation. Stacking the K K K blocks produces g M ∈ N 2 , 2 , 3 ReLU g_M\in\mathcal{N}^{\operatorname{ReLU}}_{2,2,3} g M ∈ N 2 , 2 , 3 ReLU of depth ∑ i = 1 K O ( n i ) = poly ( ∣ M ∣ ) \sum_{i=1}^{K}O(n_i)=\operatorname{poly}(|M|) ∑ i = 1 K O ( n i ) = poly ( ∣ M ∣ ) , where n i n_i n i is the number of breakpoints of ψ i \psi_i ψ i . The commutation g M ∘ ν = ν ∘ ⊢ g_M\circ\nu=\nu\circ\vdash g M ∘ ν = ν ∘ ⊢ on C M C_M C M holds cylinder-by-cylinder by the explicit case analysis in Bournez et al. [ [11 ] ; outside the encoded domain ν ( C M ) \nu(C_M) ν ( C M ) , g M g_M g M is the continuous piecewise-affine extension determined by the construction, with no claim made. □ \square □
Remark 27 (Equivalence with Theorem 12). Theorem 12 in the main body differs from Theorem 26 only in its bookkeeping: the scratch register is exposed as an explicit third input/output coordinate, reset to 0 between TM steps. The conversion from one formulation to the other is purely affine and does not increase the hidden width: prepend an R 2 → R 3 \mathbb{R}^2\to\mathbb{R}^3 R 2 → R 3 map dropping the third input coordinate, and append an R 3 → R 3 \mathbb{R}^3\to\mathbb{R}^3 R 3 → R 3 map padding the output with a zero third coordinate. We use the two-dimensional formulation for the width analysis above and the three-dimensional register form when chaining the simulator with the encoding-validity certificate of Stage 2 in § 3 .
Remark 28. The use of base-4 digits in { 1 , 3 } \{1,3\} { 1 , 3 } rather than a binary representation is essential: a continuous ReLU map cannot discriminate adjacent base-2 digits, but it can discriminate { 1 , 3 } \{1,3\} { 1 , 3 } -digits because of the gap of size 1 2 \frac{1}{2} 2 1 between 1 4 \frac{1}{4} 4 1 and 3 4 \frac{3}{4} 4 3 . See [2001], [1991], [1994], [1996], [1991] for related work. Note that the gaps are between the leading-digit cylinders, not between admissible points: D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 is a perfect set, two encodings agreeing on their first m m m digits differ by at most 4 − m 4^{-m} 4 − m , so no fixed margin separates distinct encodings and no rounding step back onto the encoding set exists. This is one more reason why uniform approximation does not yield exact simulation (the main one is the expansion argument of Section 3.1).
Encoding-validity gadget at width 4
Theorem 26 requires a validly encoded input from D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 . To make the simulation work uniformly on any input in [ 0 , 1 ] 4 [0,1]^4 [ 0 , 1 ] 4 , we construct a width-4 preprocessing gadget that detects deviation from the encoding set. This appendix develops the auxiliary gadgets and combines them.
Why we need this gadget
If width and dimension were unrestricted, NP-completeness of verification for ReLU networks would follow from a SAT-style reduction [41 ] , or from the bounded-time reachability hardness for two-dimensional CPAMs [6 ] . Translating the CPAM to a ReLU network via [2 ] yields verification hardness for ReLU networks of some fixed width, but the width is not estimated and is at best loose. Moreover, this approach is unrelated to Turing-machine complexity, so it gives only NP-hardness rather than the full time-bound spectrum (Theorem 7).
We instead exploit Theorem 26 : ReLU networks of width 3 already simulate Turing machines, but on the fractal encoding D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 . Since the verification problem asks for the existence of an input in a convex region I n i t \mathit{Init} Init , we must close the gap between “valid encoding inputs” and “arbitrary convex inputs”. The encoding-validity gadget below performs this closure with one extra unit of width.
Auxiliary gadgets
We construct three width-2 subnetworks that constitute the building blocks of the validity check.
Lemma 29 (Error indicator). There exists a ReLU network N e r r : R → R 2 N_{\mathrm{err}}:\mathbb{R}\to\mathbb{R}^2 N err : R → R 2 in N 1 , 2 , 2 R e L U \mathcal{N}_{1,2,2}^{\mathrm{ReLU}} N 1 , 2 , 2 ReLU such that, for every x ∈ [ 0 , 4 ] x\in[0,4] x ∈ [ 0 , 4 ] , N e r r ( x ) = ( x , err ( x ) ) N_{\mathrm{err}}(x)=(x,\operatorname{err}(x)) N err ( x ) = ( x , err ( x )) , where err : R → R ≥ 0 \operatorname{err}:\mathbb{R}\to\mathbb{R}_{\geq0} err : R → R ≥ 0 satisfies 0 ≤ err ( x ) ≤ 1 0\leq\operatorname{err}(x)\leq1 0 ≤ err ( x ) ≤ 1 for all x ∈ R ≥ 0 x\in\mathbb{R}_{\geq0} x ∈ R ≥ 0 , and err ( x ) = 0 ⟺ x ∈ [ 1 , 2 ] ∪ [ 3 , 4 ] \operatorname{err}(x)=0\Longleftrightarrow x\in[1,2]\cup[3,4] err ( x ) = 0 ⟺ x ∈ [ 1 , 2 ] ∪ [ 3 , 4 ] .
Proof. Let f ( 0 , 1 ) ( x ) = ReLU ( 1 − x ) f_{(0,1)}(x)=\operatorname{ReLU}(1-x) f ( 0 , 1 ) ( x ) = ReLU ( 1 − x ) and f ( 2 , 3 ) ( x ) = 1 2 − ReLU ( x − 5 2 ) − ReLU ( 5 2 − x ) f_{(2,3)}(x)=\frac{1}{2}-\operatorname{ReLU}\left(x-\frac{5}{2}\right)-\operatorname{ReLU}\left(\frac{5}{2}-x\right) f ( 2 , 3 ) ( x ) = 2 1 − ReLU ( x − 2 5 ) − ReLU ( 2 5 − x ) . Then f ( 0 , 1 ) f_{(0,1)} f ( 0 , 1 ) is strictly positive on [ 0 , 1 ) [0,1) [ 0 , 1 ) and non-positive elsewhere; f ( 2 , 3 ) f_{(2,3)} f ( 2 , 3 ) is strictly positive on ( 2 , 3 ) (2,3) ( 2 , 3 ) and non-positive elsewhere. Define err ( x ) = ReLU ( f ( 0 , 1 ) ( x ) ) + ReLU ( f ( 2 , 3 ) ( x ) ) \operatorname{err}(x)=\operatorname{ReLU}(f_{(0,1)}(x))+\operatorname{ReLU}(f_{(2,3)}(x)) err ( x ) = ReLU ( f ( 0 , 1 ) ( x )) + ReLU ( f ( 2 , 3 ) ( x )) . By construction, err ( x ) = 0 \operatorname{err}(x)=0 err ( x ) = 0 iff x ∈ [ 1 , 2 ] ∪ [ 3 , 4 ] x\in[1,2]\cup[3,4] x ∈ [ 1 , 2 ] ∪ [ 3 , 4 ] . Rewriting as a nested ReLU composition gives
err ( x ) = ReLU ( 3 − x − ReLU ( 5 − 2 x − ReLU ( 2 − x + ReLU ( 1 − x ) ) ) ) . \operatorname{err}(x)=\operatorname{ReLU}\left(3-x-\operatorname{ReLU}\left(5-2x-\operatorname{ReLU}\left(2-x+\operatorname{ReLU}(1-x)\right)\right)\right). err ( x ) = ReLU ( 3 − x − ReLU ( 5 − 2 x − ReLU ( 2 − x + ReLU ( 1 − x ) ) ) ) .
which is a finite composition of ReLU and affine operations on a single real input, hence directly implementable by a ReLU network of width 2: at each layer one neuron computes the inner ReLU expression while the second neuron carries the running input value x x x via ReLU ( x ) = x \operatorname{ReLU}(x)=x ReLU ( x ) = x (valid since x ≥ 0 x\geq0 x ≥ 0 on the domain [ 0 , 4 ] [0,4] [ 0 , 4 ] ). See Figure 3 .
Figure 3. Network N e r r N_{\mathrm{err}} N err . Boxes represent ReLU neurons; subscripts indicate biases, edge labels indicate weights, and missing labels correspond to bias 0 and weight 1.
Lemma 30 (Leading-digit extraction). There exists a ReLU network N l e a d : R → R 2 N_{\mathrm{lead}}:\mathbb{R}\to\mathbb{R}^2 N lead : R → R 2 in N 1 , 2 , 2 R e L U \mathcal{N}_{1,2,2}^{\mathrm{ReLU}} N 1 , 2 , 2 ReLU such that, for every x = ∑ i = 1 ∞ a i 4 − i ∈ ( 0 , 1 ) x=\sum_{i=1}^{\infty}a_i4^{-i}\in(0,1) x = ∑ i = 1 ∞ a i 4 − i ∈ ( 0 , 1 ) , N l e a d ( x ) = ( x , lead ( x ) ) N_{\mathrm{lead}}(x)=(x,\operatorname{lead}(x)) N lead ( x ) = ( x , lead ( x )) , where lead ( x ) = a 1 \operatorname{lead}(x)=a_1 lead ( x ) = a 1 whenever a 1 ∈ { 1 , 3 } a_1\in\{1,3\} a 1 ∈ { 1 , 3 } .
@page 18/34 starts_mid=1 ends_mid=1
Proof. The digits a 1 ∈ { 1 , 3 } a_1 \in\{1,3\} a 1 ∈ { 1 , 3 } correspond exactly to x ∈ [ 1 4 , 1 2 ] ∪ [ 3 4 , 1 ] x \in\left[\frac{1}{4},\frac{1}{2}\right] \cup\left[\frac{3}{4},1\right] x ∈ [ 4 1 , 2 1 ] ∪ [ 4 3 , 1 ] (with gaps in between). Define
lead ( x ) = 1 + 8 ReLU ( x − 1 2 ) − 8 ReLU ( x − 3 4 ) . \operatorname{lead}(x) = 1 + 8\operatorname{ReLU}\left(x-\frac{1}{2}\right) - 8\operatorname{ReLU}\left(x-\frac{3}{4}\right). lead ( x ) = 1 + 8 ReLU ( x − 2 1 ) − 8 ReLU ( x − 4 3 ) .
A direct case analysis verifies: x ∈ [ 1 4 , 1 2 ] ⇒ lead ( x ) = 1 x \in\left[\frac{1}{4},\frac{1}{2}\right] \Rightarrow\operatorname{lead}(x)=1 x ∈ [ 4 1 , 2 1 ] ⇒ lead ( x ) = 1 ; x ∈ [ 3 4 , 1 ] ⇒ lead ( x ) = 3 x \in\left[\frac{3}{4},1\right] \Rightarrow\operatorname{lead}(x)=3 x ∈ [ 4 3 , 1 ] ⇒ lead ( x ) = 3 . See Figure 4 .
Figure 4. Network N l e a d N_{\mathrm{lead}} N lead . Boxes represent ReLU neurons; subscripts indicate biases, edge labels indicate weights, and missing labels correspond to bias 0 and weight 1.
Lemma 31 (Base-4 digit shift). There exists a ReLU network N s h i f t : R → R 2 N_{\mathrm{shift}}:\mathbb{R}\to\mathbb{R}^2 N shift : R → R 2 in N 1 , 2 , 2 R e L U \mathcal{N}^{\mathrm{ReLU}}_{1,2,2} N 1 , 2 , 2 ReLU such that, for every x ∈ ( 0 , 1 ) x\in(0,1) x ∈ ( 0 , 1 ) , N s h i f t ( x ) = ( x , shift ( x ) ) N_{\mathrm{shift}}(x)=(x,\operatorname{shift}(x)) N shift ( x ) = ( x , shift ( x )) , where shift ( x ) ∈ [ 0 , 1 ] \operatorname{shift}(x)\in[0,1] shift ( x ) ∈ [ 0 , 1 ] for x ∈ ( 0 , 1 ) x\in(0,1) x ∈ ( 0 , 1 ) and shift ( x ) = ∑ i = 2 ∞ a i 4 − ( i − 1 ) \operatorname{shift}(x)=\sum_{i=2}^{\infty}a_i4^{-(i-1)} shift ( x ) = ∑ i = 2 ∞ a i 4 − ( i − 1 ) when x = ∑ i = 1 ∞ a i 4 − i x=\sum_{i=1}^{\infty}a_i4^{-i} x = ∑ i = 1 ∞ a i 4 − i with a 1 ∈ { 1 , 3 } a_1\in\{1,3\} a 1 ∈ { 1 , 3 } . *
Proof. It suffices to verify shift ( x ) = 4 x − lead ( x ) \operatorname{shift}(x)=4x-\operatorname{lead}(x) shift ( x ) = 4 x − lead ( x ) .
Width-4 validity check via the { 1 , 3 } \{1,3\} { 1 , 3 } -base-4 digit gadget
Proposition 32 (Width-4 encoding-validity check). Fix n ∈ N n\in\mathbb{N} n ∈ N . There exists a ReLU network N T ( n ) ∈ N 2 , 2 , 4 R e L U N_{T(n)}\in\mathcal{N}^{\mathrm{ReLU}}_{2,2,4} N T ( n ) ∈ N 2 , 2 , 4 ReLU such that, for every x = ∑ i = 1 ∞ a i 4 − i ∈ [ 0 , 1 ] x=\sum_{i=1}^{\infty}a_i4^{-i}\in[0,1] x = ∑ i = 1 ∞ a i 4 − i ∈ [ 0 , 1 ] , N T ( n ) ( x , 0 ) = ( T n ( x ) , ϵ n ( x ) ) N_{T(n)}(x,0)=(T_n(x),\epsilon_n(x)) N T ( n ) ( x , 0 ) = ( T n ( x ) , ϵ n ( x )) satisfies:
if x = ∑ i = 1 n a i 4 − i x=\sum_{i=1}^{n}a_i4^{-i} x = ∑ i = 1 n a i 4 − i with a i ∈ { 1 , 3 } a_i\in\{1,3\} a i ∈ { 1 , 3 } , then T n ( x ) = x T_n(x)=x T n ( x ) = x and ϵ n ( x ) = 0 \epsilon_n(x)=0 ϵ n ( x ) = 0 ;
conversely, if ϵ n ( x ) = 0 \epsilon_n(x)=0 ϵ n ( x ) = 0 , then x x x has the form ∑ i = 1 n a i 4 − i \sum_{i=1}^{n}a_i4^{-i} ∑ i = 1 n a i 4 − i with a i ∈ { 1 , 3 } a_i\in\{1,3\} a i ∈ { 1 , 3 } .
Proof. The network N T ( n ) N_{T(n)} N T ( n ) iteratively decodes the first n n n base-4 digits of x x x , accumulating any deviation from { 1 , 3 } \{1,3\} { 1 , 3 } into an error variable ϵ \epsilon ϵ .
Construction. Given the input pair ( x , p ) (x,p) ( x , p ) , the network performs the following loop:
Initialise ϵ ← 0 \epsilon\leftarrow0 ϵ ← 0 .
For i = 1 , … , n i=1,\ldots,n i = 1 , … , n : (a) Update the error: ϵ ← ReLU ( ϵ + err ( 4 x ) ) \epsilon\leftarrow\operatorname{ReLU}(\epsilon+\operatorname{err}(4x)) ϵ ← ReLU ( ϵ + err ( 4 x )) . (b) Extract the leading base-4 digit: a ← lead ( x ) a\leftarrow\operatorname{lead}(x) a ← lead ( x ) . (c) Update the accumulator: p ← ReLU ( p + a ⋅ 4 − i ) p\leftarrow\operatorname{ReLU}(p+a\cdot4^{-i}) p ← ReLU ( p + a ⋅ 4 − i ) . (d) Shift the input: x ← shift ( x ) x\leftarrow\operatorname{shift}(x) x ← shift ( x ) .
Return ( p , x + ϵ ) (p,x+\epsilon) ( p , x + ϵ ) .
By Lemmas 29, 30, and 31, each instruction can be implemented by a width-2 ReLU subnetwork. The registers p p p and ϵ \epsilon ϵ must be propagated throughout the computation alongside the working register x x x , yielding total width 4; see Figure 5 .
Figure 5. Sub-network of N T ( n ) N_{T(n)} N T ( n ) implementing the i i i -th loop iteration, which updates ( x i , p i , ϵ i ) (x_i,p_i,\epsilon_i) ( x i , p i , ϵ i ) into ( x i + 1 , p i + 1 , ϵ i + 1 ) (x_{i+1},p_{i+1},\epsilon_{i+1}) ( x i + 1 , p i + 1 , ϵ i + 1 ) using ReLU neurons and the three components N e r r N_{\mathrm{err}} N err , N l e a d N_{\mathrm{lead}} N lead , and N s h i f t N_{\mathrm{shift}} N shift . Outputs are shown at the sources of the arrows, and weights at their targets. The sub-network has width 4. The components N l e a d N_{\mathrm{lead}} N lead and N s h i f t N_{\mathrm{shift}} N shift have constant depth. For readability, only one ReLU layer is drawn in parallel with these components; formally, one should include as many ReLU layers as the depths of the corresponding sub-networks.
Correctness. Let ( x i , p i , ϵ i ) (x_i,p_i,\epsilon_i) ( x i , p i , ϵ i ) denote the values after i i i iterations, with initial values ( x 0 , p 0 , ϵ 0 ) = ( x , 0 , 0 ) (x_0,p_0,\epsilon_0)=(x,0,0) ( x 0 , p 0 , ϵ 0 ) = ( x , 0 , 0 ) . Property 1. Suppose x = ∑ j = 1 n a j 4 − j x=\sum_{j=1}^{n}a_j4^{-j} x = ∑ j = 1 n a j 4 − j with a j ∈ { 1 , 3 } a_j\in\{1,3\} a j ∈ { 1 , 3 } . By induction, x i = ∑ j = i + 1 n a j 4 − ( j − i ) x_i=\sum_{j=i+1}^{n}a_j4^{-(j-i)} x i = ∑ j = i + 1 n a j 4 − ( j − i ) and p i = ∑ j = 1 i a j 4 − j p_i=\sum_{j=1}^{i}a_j4^{-j} p i = ∑ j = 1 i a j 4 − j . After n n n iterations, x n = 0 x_n=0 x n = 0 and p n = x p_n=x p n = x . Moreover, ϵ n = ∑ i = 1 n err ( 4 x i − 1 ) = 0 \epsilon_n=\sum_{i=1}^{n}\operatorname{err}(4x_{i-1})=0 ϵ n = ∑ i = 1 n err ( 4 x i − 1 ) = 0 since each err ( 4 x i − 1 ) \operatorname{err}(4x_{i-1}) err ( 4 x i − 1 ) vanishes when a i ∈ { 1 , 3 } a_i\in\{1,3\} a i ∈ { 1 , 3 } by Lemma 29. Hence T n ( x ) = p n = x T_n(x)=p_n=x T n ( x ) = p n = x and ε n ( x ) = x n + ϵ n = 0 \varepsilon_n(x)=x_n+\epsilon_n=0 ε n ( x ) = x n + ϵ n = 0 .
Property 2. Suppose N T ( n ) ( x , 0 ) = ( x ′ , 0 ) N_{T(n)}(x,0)=(x',0) N T ( n ) ( x , 0 ) = ( x ′ , 0 ) , i.e. x n + ϵ n = 0 x_n+\epsilon_n=0 x n + ϵ n = 0 . Both x n ≥ 0 x_n\ge0 x n ≥ 0 (since shift is non-negative) and ϵ n ≥ 0 \epsilon_n\ge0 ϵ n ≥ 0 (sum of ReLUs), so x n = 0 x_n=0 x n = 0 and ϵ n = 0 \epsilon_n=0 ϵ n = 0 . We argue by contradiction: suppose x x x is not of the form ∑ j = 1 n a j 4 − j \sum_{j=1}^{n}a_j4^{-j} ∑ j = 1 n a j 4 − j with a j ∈ { 1 , 3 } a_j\in\{1,3\} a j ∈ { 1 , 3 } . Two cases.
The first n n n digits are in { 1 , 3 } \{1,3\} { 1 , 3 } , but x ≠ ∑ j = 1 n a j 4 − j x\ne\sum_{j=1}^{n}a_j4^{-j} x = ∑ j = 1 n a j 4 − j . Then x n = ∑ j > n a j 4 − ( j − n ) > 0 x_n=\sum_{j>n}a_j4^{-(j-n)}>0 x n = ∑ j > n a j 4 − ( j − n ) > 0 , contradiction (on D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 , x n ≥ 1 / 3 x_n\ge1/3 x n ≥ 1/3 ).
There is some ℓ ≤ n \ell\le n ℓ ≤ n with a ℓ ∉ { 1 , 3 } a_\ell\notin\{1,3\} a ℓ ∈ / { 1 , 3 } , taken minimal. Then err ( 4 x ℓ − 1 ) > 0 \operatorname{err}(4x_{\ell-1})>0 err ( 4 x ℓ − 1 ) > 0 , hence ϵ n > 0 \epsilon_n>0 ϵ n > 0 , contradiction.
This completes the proof.
Remark 33 (The per-step certificate ε \varepsilon ε of Theorem 3). The per-step certificate of Theorem 3 is
ε ( x 1 , x 2 ) = max { err ( 4 x 1 ) , err ( 4 suf ( x 2 ) ) , d Q ( pre ( x 2 ) ) } ∈ [ 0 , 1 ] , \varepsilon(x_1,x_2)=\max\{\operatorname{err}(4x_1),\operatorname{err}(4\operatorname{suf}(x_2)),d_Q(\operatorname{pre}(x_2))\}\in[0,1], ε ( x 1 , x 2 ) = max { err ( 4 x 1 ) , err ( 4 suf ( x 2 )) , d Q ( pre ( x 2 ))} ∈ [ 0 , 1 ] ,
where pre ( x 2 ) \operatorname{pre}(x_2) pre ( x 2 ) and suf ( x 2 ) \operatorname{suf}(x_2) suf ( x 2 ) are the state-prefix and tape-suffix portions of x 2 x_2 x 2 (Section 2.3), obtained by a constant-depth slicing (a CPAM, expressible as a finite ReLU expression by Lemma 25), and d Q : [ 0 , 1 ] → [ 0 , 1 ] d_Q:[0,1]\to[0,1] d Q : [ 0 , 1 ] → [ 0 , 1 ] is a state-distance subgadget that vanishes exactly on enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) , built as a ∣ Q ∣ |Q| ∣ Q ∣ -fold minimum of tent functions. The maxima are realized in width 2 via max { a , b } = a + ReLU ( b − a ) \max\{a,b\}=a+\operatorname{ReLU}(b-a) max { a , b } = a + ReLU ( b − a ) . Thus ε ( x 1 , x 2 ) = 0 \varepsilon(x_1,x_2)=0 ε ( x 1 , x 2 ) = 0 iff the leading base-4 digit of x 1 x_1 x 1 and of the tape-suffix of x 2 x_2 x 2 lies in { 1 , 3 } \{1,3\} { 1 , 3 } (that is, 4 x 1 4x_1 4 x 1 and 4 suf ( x 2 ) 4\operatorname{suf}(x_2) 4 suf ( x 2 ) lie in the closed cylinders [ 1 , 2 ] ∪ [ 3 , 4 ] [1,2]\cup[3,4] [ 1 , 2 ] ∪ [ 3 , 4 ] , Lemma 29) and the state prefix lies in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) . The zero set of ε \varepsilon ε is a finite union of boxes, which a finite ReLU network can realize. Membership of the full expansions in D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 cannot be checked in one step (Proposition 11): it is checked across iterations, one digit per step, because the simulator’s own tape shifts expose successive digits as leading digits. The gadget of Proposition 32 belongs to the finite-word setting of Bournez et al. [ [12 ] : it vanishes exactly when x x x is a base-4 word of length n n n over { 1 , 3 } \{1,3\} { 1 , 3 } , and is positive on D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 . Only its one-digit building block err \operatorname{err} err (Lemma 29) enters ε \varepsilon ε .
Full proof of the main theorem
This appendix formalizes the construction sketched in Section 3 of the main body, using the building blocks of Appendices B and C. We construct N M N_M N M explicitly, establish a structural invariant on the certificate, and derive parts (i) and (ii) of Theorem 3.
Remark 34 (Certifying a set). Part (ii) of Theorem 3 says, informally, that N M N_M N M certifies a set V ⊆ [ 0 , 1 ] 14 V\subseteq[0,1]^{14} V ⊆ [ 0 , 1 ] 14 : a coordinate is non-decreasing along the iterates and vanishes along the whole trajectory of x x x exactly when x ∈ V x \in V x ∈ V . Here V V V is the set of inputs whose visited digits (§ 2.3 ) lie in { 1 , 3 } \{1,3\} { 1 , 3 } and whose state prefix stays in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) . This set contains the encoded configurations, and it is exactly what soundness requires. The quantification over all k k k is essential, since no finite ReLU network has zero set D 1 , 3 \mathbb{D}_{1,3} D 1 , 3 (Remark 4). The certificate appears only inside the witness network built for hardness (Remark 6).
Construction of the simulating network N M N_M N M for a Turing machine M M M
Recall the encoding map from Appendix B: a configuration c = ( u , q , v ) ∈ C M c=(u,q,v)\in C_M c = ( u , q , v ) ∈ C M is encoded as ν ( c ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v ) ) ∈ [ 0 , 1 ] 2 \nu(c)=(\operatorname{enc}_{\{1,3\}}(u),\operatorname{enc}_M(q,v))\in[0,1]^2 ν ( c ) = ( enc { 1 , 3 } ( u ) , enc M ( q , v )) ∈ [ 0 , 1 ] 2 , where the second coordinate co-encodes state and right tape. The full input to N M N_M N M is
enc M ( c ) : = ( ν ( c ) 1 , ν ( c ) 2 , 0 , 0 ) ∈ [ 0 , 1 ] 4 , \operatorname{enc}_M(c):=(\nu(c)_1,\nu(c)_2,0,0)\in[0,1]^4, enc M ( c ) := ( ν ( c ) 1 , ν ( c ) 2 , 0 , 0 ) ∈ [ 0 , 1 ] 4 ,
with the third coordinate used as scratch by the width-3 simulator g M g_M g M and the fourth as a validity accumulator.
The network N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N_M:[0,1]^4\to[0,1]^4 N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 is defined as the composition N M = N s i m ∘ N c h e c k N_M=N_{\mathrm{sim}}\circ N_{\mathrm{check}} N M = N sim ∘ N check of two register-network blocks; see Figure 1 (schematic) and 6 (formal).
(C) N c h e c k N_{\mathrm{check}} N check (width-4 certificate update ):
( x 1 , x 2 , x 3 , x 4 ) ⟼ ( x 1 , x 2 , x 3 , max { x 4 , ε ( x 1 , x 2 ) } ) , (x_1,x_2,x_3,x_4)\longmapsto(x_1,x_2,x_3,\max\{x_4,\varepsilon(x_1,x_2)\}), ( x 1 , x 2 , x 3 , x 4 ) ⟼ ( x 1 , x 2 , x 3 , max { x 4 , ε ( x 1 , x 2 )}) ,
where ε : [ 0 , 1 ] 2 → [ 0 , 1 ] \varepsilon:[0,1]^2\to[0,1] ε : [ 0 , 1 ] 2 → [ 0 , 1 ] is the per-step certificate of Remark 33: ε ( x 1 , x 2 ) = 0 \varepsilon(x_1,x_2)=0 ε ( x 1 , x 2 ) = 0 iff the leading base-4 digit of x 1 x_1 x 1 and of the tape-suffix of x 2 x_2 x 2 lies in { 1 , 3 } \{1,3\} { 1 , 3 } and the state prefix of x 2 x_2 x 2 lies in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) . Membership of the full expansions in $\mathbb{D}_{1,3} is checked across iterations, one digit per step (Remark 33). The max is realized in width 2 via max { a , b } = a + ReLU ( b − a ) \max\{a,b\}=a+\operatorname{ReLU}(b-a) max { a , b } = a + ReLU ( b − a ) .
(S) N s i m N_{\mathrm{sim}} N sim (width-3 simulation ): applies the width-3 network g M ∈ N 2 , 2 , 3 R e L U g_M\in\mathcal{N}_{2,2,3}^{\mathrm{ReLU}} g M ∈ N 2 , 2 , 3 ReLU of Theorem 26 to ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) using x 3 x_3 x 3 as scratch, while propagating x 4 x_4 x 4 unchanged through an identity wire (this is consistent with the register-form structure of N M N_M N M , see Remark 42).
The order (check before simulation ) is essential: any encoding violation is detected before g M g_M g M has the chance to overwrite ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) . The total per-iteration depth is D M = O ( depth ( g M ) ) = poly ( ∣ M ∣ ) D_M=O(\operatorname{depth}(g_M))=\operatorname{poly}(|M|) D M = O ( depth ( g M )) = poly ( ∣ M ∣ ) , and the width is 4.
Structural invariant
The key technical content of the proof is the following invariant, which formalizes the claim made informally in Stage 2 of Section 3.
Lemma 35 (Encoding-validity invariant). Let x = ( x 1 ( 0 ) , x 2 ( 0 ) , x 3 ( 0 ) , x 4 ( 0 ) ) ∈ [ 0 , 1 ] 4 x=(x_1^{(0)},x_2^{(0)},x_3^{(0)},x_4^{(0)})\in[0,1]^4 x = ( x 1 ( 0 ) , x 2 ( 0 ) , x 3 ( 0 ) , x 4 ( 0 ) ) ∈ [ 0 , 1 ] 4 be any input, and let ( x 1 ( k ) , x 2 ( k ) , x 3 ( k ) , x 4 ( k ) ) : = N M [ k ] ( x ) (x_1^{(k)},x_2^{(k)},x_3^{(k)},x_4^{(k)}):=N_M^{[k]}(x) ( x 1 ( k ) , x 2 ( k ) , x 3 ( k ) , x 4 ( k ) ) := N M [ k ] ( x ) for k ≥ 0 k\ge0 k ≥ 0 . Call step j j j locally valid if the leading base-4 digit
of x 1 ( j ) x_1^{(j)} x 1 ( j ) and of the tape-suffix of x 2 ( j ) x_2^{(j)} x 2 ( j ) lies in { 1 , 3 } \{1,3\} { 1 , 3 } and the state-prefix of x 2 ( j ) x_2^{(j)} x 2 ( j ) lies in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) . Then for every k ≥ 0 k \ge0 k ≥ 0 :
(a) (Monotonicity.) x 4 ( k + 1 ) ≥ x 4 ( k ) x_4^{(k+1)} \ge x_4^{(k)} x 4 ( k + 1 ) ≥ x 4 ( k ) and x 4 ( k ) ∈ [ 0 , 1 ] x_4^{(k)} \in[0,1] x 4 ( k ) ∈ [ 0 , 1 ] .
(b) (Local validity preserves the certificate.) If every step j ≤ k j \le k j ≤ k is locally valid, then x 4 ( k ) = x 4 ( 0 ) x_4^{(k)} = x_4^{(0)} x 4 ( k ) = x 4 ( 0 ) .
In particular, if x 1 ( 0 ) ∈ D D 1 , 3 x_1^{(0)} \in\mathbb{D}\mathbb{D}_{1,3} x 1 ( 0 ) ∈ D D 1 , 3 , the tape-suffix of x 2 ( 0 ) x_2^{(0)} x 2 ( 0 ) is in D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 and the state-prefix of x 2 ( 0 ) x_2^{(0)} x 2 ( 0 ) is in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) , then every step is locally valid, since g M g_M g M preserves these properties (Theorem 26), and x 4 ( k ) = x 4 ( 0 ) x_4^{(k)} = x_4^{(0)} x 4 ( k ) = x 4 ( 0 ) for all k k k .
(c) (Violation detected.) Conversely, if some step j ≤ k j \le k j ≤ k is not locally valid, then x 4 ( k ) ≥ ε ( x 1 ( j ) , x 2 ( j ) ) > 0 x_4^{(k)} \ge\varepsilon(x_1^{(j)},x_2^{(j)}) > 0 x 4 ( k ) ≥ ε ( x 1 ( j ) , x 2 ( j ) ) > 0 for all k ≥ j + 1 k \ge j+1 k ≥ j + 1 . In particular, if x 4 ( 0 ) = 0 x_4^{(0)} = 0 x 4 ( 0 ) = 0 , then x 4 ( k ) > x 4 ( 0 ) x_4^{(k)} > x_4^{(0)} x 4 ( k ) > x 4 ( 0 ) , and this persists forever.
Summed over the steps j < k j < k j < k , the local-validity conditions are exactly the condition of Theorem 3(ii): every digit visited during the first k k k iterations (§ 2.3 ) lies in { 1 , 3 } \{1,3\} { 1 , 3 } , and the state prefix stays in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) along the trajectory.
Proof. (a) The fourth coordinate is updated by x 4 ( k + 1 ) = max { x 4 ( k ) , ε ( x 1 ( k ) , x 2 ( k ) ) } x_4^{(k+1)} = \max\{x_4^{(k)}, \varepsilon(x_1^{(k)},x_2^{(k)})\} x 4 ( k + 1 ) = max { x 4 ( k ) , ε ( x 1 ( k ) , x 2 ( k ) )} , which is non-decreasing. Since ε ≤ 1 \varepsilon\le1 ε ≤ 1 (Remark 33) and x 4 ( 0 ) ∈ [ 0 , 1 ] x_4^{(0)} \in[0,1] x 4 ( 0 ) ∈ [ 0 , 1 ] , induction gives x 4 ( k ) ∈ [ 0 , 1 ] x_4^{(k)} \in[0,1] x 4 ( k ) ∈ [ 0 , 1 ] .
(b) If step j j j is locally valid, then ε ( x 1 ( j ) , x 2 ( j ) ) = 0 \varepsilon(x_1^{(j)},x_2^{(j)}) = 0 ε ( x 1 ( j ) , x 2 ( j ) ) = 0 by Remark 33, hence x 4 ( j + 1 ) = max { x 4 ( j ) , 0 } = x 4 ( j ) x_4^{(j+1)} = \max\{x_4^{(j)},0\} = x_4^{(j)} x 4 ( j + 1 ) = max { x 4 ( j ) , 0 } = x 4 ( j ) . Iterating from j = 0 j=0 j = 0 to k − 1 k-1 k − 1 yields x 4 ( k ) = x 4 ( 0 ) x_4^{(k)} = x_4^{(0)} x 4 ( k ) = x 4 ( 0 ) . The second claim follows since g M g_M g M maps valid encodings to valid encodings (Theorem 26), so every leading digit exposed along the trajectory stays in { 1 , 3 } \{1,3\} { 1 , 3 } and the state prefix stays in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) .
(c) If step j j j is not locally valid, then ε ( x 1 ( j ) , x 2 ( j ) ) > 0 \varepsilon(x_1^{(j)},x_2^{(j)}) > 0 ε ( x 1 ( j ) , x 2 ( j ) ) > 0 (Remark 33), so x 4 ( j + 1 ) ≥ ε ( x 1 ( j ) , x 2 ( j ) ) > 0 x_4^{(j+1)} \ge\varepsilon(x_1^{(j)},x_2^{(j)}) > 0 x 4 ( j + 1 ) ≥ ε ( x 1 ( j ) , x 2 ( j ) ) > 0 . By monotonicity, x 4 ( k ) ≥ x 4 ( j + 1 ) x_4^{(k)} \ge x_4^{(j+1)} x 4 ( k ) ≥ x 4 ( j + 1 ) for all k ≥ j + 1 k \ge j+1 k ≥ j + 1 . □
Proof of thm:main
Proof of Theorem 3. Part (i): faithful simulation on encoded inputs. Let τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω be an infinite binary tape and c 0 : = c 0 ( τ ) c_0 := c_0(\tau) c 0 := c 0 ( τ ) the initial configuration of M M M on τ \tau τ . The input is enc M ( c 0 ) = ( ν ( c 0 ) 1 , ν ( c 0 ) 2 , 0 , 0 ) \operatorname{enc}_M(c_0) = (\nu(c_0)_1,\nu(c_0)_2,0,0) enc M ( c 0 ) = ( ν ( c 0 ) 1 , ν ( c 0 ) 2 , 0 , 0 ) with both ν ( c 0 ) 1 \nu(c_0)_1 ν ( c 0 ) 1 and ν ( c 0 ) 2 \nu(c_0)_2 ν ( c 0 ) 2 encoded as required.
We claim by induction on t ≥ 0 t \ge0 t ≥ 0 that N M [ C M t ] ( enc M ( c 0 ) ) = enc M ( c t ( τ ) ) N_M^{[C_Mt]}(\operatorname{enc}_M(c_0)) = \operatorname{enc}_M(c_t(\tau)) N M [ C M t ] ( enc M ( c 0 )) = enc M ( c t ( τ )) , where C M C_M C M is the per-step iteration count of g M g_M g M in Theorem 26. The base case t = 0 t=0 t = 0 is immediate. For the inductive step, suppose N M [ C M t ] ( enc M ( c 0 ) ) = enc M ( c t ) N_M^{[C_Mt]}(\operatorname{enc}_M(c_0)) = \operatorname{enc}_M(c_t) N M [ C M t ] ( enc M ( c 0 )) = enc M ( c t ) for some t t t . By Theorem 26, g M g_M g M maps ν ( c t ) ↦ ν ( c t + 1 ) \nu(c_t) \mapsto\nu(c_{t+1}) ν ( c t ) ↦ ν ( c t + 1 ) in C M C_M C M iterations. Since the trajectory remains within encoded configurations (the simulator preserves D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 -encoded tapes by Theorem 26), the validity hypothesis of Lemma 35(b) holds at every step, so the fourth coordinate stays at 0 0 0 . Hence N M [ C M ( t + 1 ) ] ( enc M ( c 0 ) ) = enc M ( c t + 1 ) N_M^{[C_M(t+1)]}(\operatorname{enc}_M(c_0)) = \operatorname{enc}_M(c_{t+1}) N M [ C M ( t + 1 )] ( enc M ( c 0 )) = enc M ( c t + 1 ) .
Part (ii): online certificate properties. The boundedness and monotonicity of π 4 ( N M [ k ] ) \pi_4(N_M^{[k]}) π 4 ( N M [ k ] ) are exactly Lemma 35(a). For x 4 ( 0 ) = 0 x_4^{(0)} = 0 x 4 ( 0 ) = 0 , the condition for π 4 ( N M [ k ] ( x ) ) = 0 \pi_4(N_M^{[k]}(x)) = 0 π 4 ( N M [ k ] ( x )) = 0 to hold is exactly local validity of every step j < k j < k j < k , which by the closing claim of Lemma 35 is the visited-digit condition of the statement. The contrapositive (a violation forces x 4 > 0 x_4 > 0 x 4 > 0 thereafter) is Lemma 35(c).
Effective construction. The reduction M ↦ N M M \mapsto N_M M ↦ N M is computable in polynomial time: g M g_M g M is constructed in poly ( ∣ M ∣ ) \operatorname{poly}(|M|) poly ( ∣ M ∣ ) time by Theorem 26, the certificate gadget in poly ( ∣ M ∣ ) \operatorname{poly}(|M|) poly ( ∣ M ∣ ) time by Remark 33, and the register-form composition is immediate by construction (Remark 42). Instantiating M = U M = U M = U , where U U U is a fixed universal TM (Lemma 39), yields a single fixed network whose iterates simulate every ( M ′ , w ) (M',w) ( M ′ , w ) .
A worked example
There is no encoder anywhere in the construction: in the reachability problem, the input to the network is not produced by encoding anything. It is chosen by the existential quantifier directly inside the convex region Init, and N M N_M N M is applied to whichever point the quantifier picks. Almost every point of Init is not a valid encoding, and being finitely representable is unrelated to being a valid encoding: the rationals in [ 0 , 1 ] [0,1] [ 0 , 1 ] are dense, and only a measure-zero subset of them encodes anything. The following two witnesses make this concrete. Fix any M M M and the regions Init, Acc of § 4.1 : the state prefix of x 2 x_2 x 2 is pinned to enc M ( q 0 ) \operatorname{enc}_M(q_0) enc M ( q 0 ) , x 3 = x 4 = 0 x_3=x_4=0 x 3 = x 4 = 0 , and x 1 x_1 x 1 is free in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Witness A (a valid encoding). Take x 1 = 0. 1 ‾ = 1 3 x_1=0.\overline{1}=\frac{1}{3} x 1 = 0. 1 = 3 1 (all digits equal to 1, hence x 1 ∈ D D 1 , 3 x_1\in\mathbb{D}\mathbb{D}_{1,3} x 1 ∈ D D 1 , 3 ), and let the tape-suffix digits of x 2 x_2 x 2 all be 1 as well. Every step is locally valid: 4 x 1 = 4 3 ∈ [ 1 , 2 ] 4x_1=\frac{4}{3}\in[1,2] 4 x 1 = 3 4 ∈ [ 1 , 2 ] , so err ( 4 x 1 ) = 0 \operatorname{err}(4x_1)=0 err ( 4 x 1 ) = 0 (Lemma 29), and likewise on the suffix of x 2 x_2 x 2 ; the same happens at every later step, since g M g_M g M maps encodings to encodings (Theorem 26 ). So x 4 = 0 x_4=0 x 4 = 0 throughout and the iterates are exactly enc M ( c t ) \operatorname{enc}_M(c_t) enc M ( c t ) . If M M M accepts the all-ones tape, the trajectory enters Acc.
Witness B (not an encoding). Take x 1 = 1 8 = 0.0 24 ‾ x_1=\frac{1}{8}=0.0\overline{24} x 1 = 8 1 = 0.0 24 , with x 2 x_2 x 2 as in Witness A. This point is perfectly representable (three bits), lies in Init, and is not in D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 : its leading digit is 0. The gadget evaluates err ( 4 x 1 ) = err ( 1 2 ) \operatorname{err}(4x_1)=\operatorname{err}\left(\frac{1}{2}\right) err ( 4 x 1 ) = err ( 2 1 ) , and with err as in Lemma 29 the first tent contributes ReLU ( 1 − 1 2 ) = 1 2 \operatorname{ReLU}\left(1-\frac{1}{2}\right)=\frac{1}{2} ReLU ( 1 − 2 1 ) = 2 1 while the second contributes 0, so ε ( x 1 , x 2 ) = 1 2 \varepsilon(x_1,x_2)=\frac{1}{2} ε ( x 1 , x 2 ) = 2 1 . Hence x 4 x_4 x 4 jumps to 1 2 \frac{1}{2} 2 1 at the first iteration and, being non-decreasing, stays at least 1 2 \frac{1}{2} 2 1 forever. Since Acc requires x 4 ≤ 0 x_4\le0 x 4 ≤ 0 , this witness can never reach Acc, whatever the continuous extension of g M g_M g M does with it downstream.
Witness B is exactly the case the certificate exists for: without it, g M g_M g M acting on 1 8 \frac{1}{8} 8 1 is an unconstrained continuous piecewise-affine map, and nothing would prevent it from landing in Acc, making the instance answer YES for reasons unrelated to M M M .
Verification spectrum at width 4
Polynomial-bit-complexity witness lemma
The NP-membership claim in the proof of Theorem 7 (unary T T T , width-4 ReLU) and in the proof of Theorem 10 (unary T T T , width-6 smooth ρ \rho ρ , after ρ → ReLU \rho\to\operatorname{ReLU} ρ → ReLU emulation) rests on the following classical observation.
Lemma 36 (Polynomial-bit-complexity for ReLU network reachability). Let N : [ 0 , 1 ] d → [ 0 , 1 ] d N:[0,1]^d\to[0,1]^d N : [ 0 , 1 ] d → [ 0 , 1 ] d be a ReLU network with rational weights of bit complexity b b b , depth L L L , and width w w w . Let Init, Acc ⊆ [ 0 , 1 ] d \subseteq[0,1]^d ⊆ [ 0 , 1 ] d be convex regions specified by rational linear inequalities of bit complexity ≤ b ′ \le b' ≤ b ′ , and let T ∈ N T\in\mathbb{N} T ∈ N . If there exists a real x ∈ I n i t x\in\mathrm{Init} x ∈ Init with N [ t ] ( x ) ∈ A c c N^{[t]}(x)\in\mathrm{Acc} N [ t ] ( x ) ∈ Acc for some t ≤ T t\le T t ≤ T , then there exists a rational x ∈ I n i t x\in\mathrm{Init} x ∈ Init with the same property and bit complexity poly ( d , w , L , T , b , b ′ ) \operatorname{poly}(d,w,L,T,b,b') poly ( d , w , L , T , b , b ′ ) .
Proof. Suppose x ∗ ∈ I n i t x^*\in\mathrm{Init} x ∗ ∈ Init is a real point such that N [ t ∗ ] ( x ∗ ) ∈ A c c N^{[t^*]}(x^*)\in\mathrm{Acc} N [ t ∗ ] ( x ∗ ) ∈ Acc for some t ∗ ≤ T t^*\le T t ∗ ≤ T . We construct a rational witness of polynomial bit complexity.
Step 1: activation pattern. A single forward pass through a ReLU network N N N of width w w w and depth L L L involves at most w L wL w L neurons, hence w L wL w L ReLU activations. For each t ∈ { 1 , … , T } t\in\{1,\ldots,T\} t ∈ { 1 , … , T } , the composition N [ t ] N^{[t]} N [ t ] involves at most w t L ≤ w T L wtL\le wTL w t L ≤ w T L such neurons. Hence, at most w T L wTL w T L ReLU activations in total along the trajectory x ∗ , N ( x ∗ ) , … , N [ T ] ( x ∗ ) x^*,N(x^*),\ldots,N^{[T]}(x^*) x ∗ , N ( x ∗ ) , … , N [ T ] ( x ∗ ) . Each neuron is in one of two states: active (ReLU ( z ) = z \operatorname{ReLU}(z)=z ReLU ( z ) = z , i.e. z ≥ 0 z\ge0 z ≥ 0 ) or inactive (ReLU ( z ) = 0 \operatorname{ReLU}(z)=0 ReLU ( z ) = 0 , i.e. z ≤ 0 z\le0 z ≤ 0 ). Let σ ∗ ∈ { + , − } w T L \sigma^*\in\{+,-\}^{wTL} σ ∗ ∈ { + , − } w T L denote the activation pattern realized at x ∗ x^* x ∗ .
Step 2: polyhedral characterization. Fix any activation pattern σ ∈ { + , − } w T L \sigma\in\{+,-\}^{wTL} σ ∈ { + , − } w T L . On the set of points x ∈ [ 0 , 1 ] d x\in[0,1]^d x ∈ [ 0 , 1 ] d for which iterating N N N produces the pattern σ \sigma σ , each ReLU acts as either the identity or zero, and so N [ t ] N^{[t]} N [ t ] becomes an affine map A σ ( t ) : R d → R d A_\sigma^{(t)}:\mathbb{R}^d\to\mathbb{R}^d A σ ( t ) : R d → R d for every t ≤ T t\le T t ≤ T . The set of x x x realizing σ \sigma σ is the polyhedron
P σ : = { x ∈ [ 0 , 1 ] d : sign ( z i , t ( x ) ) = σ i , t for every neuron i and iteration t ≤ T } , P_\sigma:=\left\{x\in[0,1]^d:\operatorname{sign}(z_{i,t}(x))=\sigma_{i,t}\text{ for every neuron }i\text{ and iteration }t\le T\right\}, P σ := { x ∈ [ 0 , 1 ] d : sign ( z i , t ( x )) = σ i , t for every neuron i and iteration t ≤ T } ,
where each z i , t ( x ) z_{i,t}(x) z i , t ( x ) is an affine function of x x x with rational coefficients of bit complexity at most poly ( d , w , L , T , b ) \operatorname{poly}(d,w,L,T,b) poly ( d , w , L , T , b ) (the bit complexity grows by at most O ( b log w ) O(b\log w) O ( b log w ) at each layer).
Step 3: linear system. For σ = σ ∗ \sigma=\sigma^* σ = σ ∗ and t = t ∗ t=t^* t = t ∗ , the conjunction “x ∈ I n i t x\in\mathrm{Init} x ∈ Init , x ∈ P σ x\in P_\sigma x ∈ P σ , A σ ( t ) ( x ) ∈ A c c A_\sigma^{(t)}(x)\in\mathrm{Acc} A σ ( t ) ( x ) ∈ Acc ” is a system S S S of rational linear inequalities. Each inequality has rational coefficients of bit complexity poly ( d , w , L , T , b , b ′ ) \operatorname{poly}(d,w,L,T,b,b') poly ( d , w , L , T , b , b ′ ) , and the system has at most poly ( d , w , L , T , b ′ ) \operatorname{poly}(d,w,L,T,b') poly ( d , w , L , T , b ′ ) inequalities. The system S S S is feasible over R \mathbb{R} R since x ∗ x^* x ∗ satisfies it. Step 4: rational witness. By a standard result in polyhedral combinatorics [32 Ch. 10] , any feasible system of rational linear inequalities admits a rational solution of bit complexity polynomial in the bit complexity of the system. Applied to S S S , this yields a rational x ∈ [ 0 , 1 ] d x \in[0,1]^d x ∈ [ 0 , 1 ] d of bit complexity poly ( d , w , L , T , b , b ′ ) \operatorname{poly}(d,w,L,T,b,b') poly ( d , w , L , T , b , b ′ ) with x ∈ I n i t x \in\mathrm{Init} x ∈ Init , x ∈ P σ ∗ x \in P_{\sigma^*} x ∈ P σ ∗ , and N [ t ∗ ] ( x ) = A σ ∗ ( t ∗ ) ( x ) ∈ A c c N[t^*](x)=A^{(t^*)}_{\sigma^*}(x) \in\mathrm{Acc} N [ t ∗ ] ( x ) = A σ ∗ ( t ∗ ) ( x ) ∈ Acc .
Underlying complexity statements about Turing machines
We use the following classical facts about Turing-machine complexity.
Lemma 37 (Basic statements from complexity theory). Let Σ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 } . The following decision problems are complete for the indicated complexity classes.
(i) (Unary time bound, NP-complete.) Given a deterministic Turing machine M M M and T ∈ N T \in\mathbb{N} T ∈ N in unary, does there exist w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ and t ≤ T t \le T t ≤ T such that M M M accepts w w w in t t t steps?
(ii) (Binary time bound, NEXP-complete.) Given a deterministic Turing machine M M M and T ∈ N T \in\mathbb{N} T ∈ N in binary, does there exist w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ and t ≤ T t \le T t ≤ T such that M M M accepts w w w in t t t steps?
(iii) (No time bound, RE-complete.) Given a deterministic Turing machine M M M , does there exist w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ such that M M M accepts w w w (in finite time)?
Proof. We treat the three items in turn.
(i) NP-completeness (unary time bound).
NP-membership. Let ( M , T ) (M,T) ( M , T ) be an instance, with T T T given in unary. A nondeterministic polynomial-time verifier guesses w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ of length at most T T T and a time t ≤ T t \le T t ≤ T , then simulates M M M on input w w w for exactly t t t steps. Since T T T is in unary, the witness ( w , t ) (w,t) ( w , t ) has polynomial bit length and the simulation runs in polynomial time. The verifier accepts iff M M M is in an accepting state at step t t t .
NP-hardness. We reduce from SAT. Let φ \varphi φ be a Boolean formula in CNF with n n n variables. Construct a deterministic Turing machine M φ M_\varphi M φ that, on input w ∈ { 0 , 1 } ∗ w \in\{0,1\}^* w ∈ { 0 , 1 } ∗ , checks whether ∣ w ∣ = n |w|=n ∣ w ∣ = n (rejecting otherwise), interprets w w w as a Boolean assignment, and accepts iff φ \varphi φ is satisfied under this assignment. The machine M φ M_\varphi M φ runs in time poly ( ∣ φ ∣ ) \operatorname{poly}(|\varphi|) poly ( ∣ φ ∣ ) ; let T T T be a unary encoding of an upper bound on this runtime. Then φ ∈ S A T \varphi\in\mathrm{SAT} φ ∈ SAT iff ∃ w ∈ { 0 , 1 } n , ∃ t ≤ T , M φ \exists w \in\{0,1\}^n,\ \exists t \le T,\ M_\varphi ∃ w ∈ { 0 , 1 } n , ∃ t ≤ T , M φ accepts w w w in t t t steps. The reduction is polynomial-time.
(ii) NEXP-completeness (binary time bound).
NEXP-membership. Let ( M , T ) (M,T) ( M , T ) be an instance with T T T in binary, of total input size n = ∣ M ∣ + ∣ T ∣ n=|M|+|T| n = ∣ M ∣ + ∣ T ∣ . Since M M M visits at most T T T tape positions in T T T steps, we may restrict to w ∈ Σ ≤ T w \in\Sigma^{\le T} w ∈ Σ ≤ T . A nondeterministic verifier guesses such a w w w in ≤ T = 2 O ( n ) \le T=2^{O(n)} ≤ T = 2 O ( n ) nondeterministic bits and a time t ≤ T t \le T t ≤ T , then simulates M M M on w w w for t t t steps in deterministic time poly ( ∣ M ∣ , T ) = 2 O ( n ) \operatorname{poly}(|M|,T)=2^{O(n)} poly ( ∣ M ∣ , T ) = 2 O ( n ) . Total nondeterministic running time is 2 O ( n ) 2^{O(n)} 2 O ( n ) , hence in NEXP.
NEXP-hardness. We reduce from Succinct-3SAT, the canonical NEXP-complete problem Papadimitriou and Yannakakis [1986], Arora and Barak [2009]. An instance is a Boolean circuit C C C of size s s s that, on input a ⌈ 2 log N ⌉ \lceil2\log N\rceil ⌈ 2 log N ⌉ -bit clause index, outputs three pairs (variable index, sign) encoding a clause of a 3-CNF formula φ \varphi φ over N = 2 s N=2^s N = 2 s variables; the question is whether φ \varphi φ is satisfiable. From C C C , construct a deterministic Turing machine M C M_C M C that, on input w ∈ { 0 , 1 } N w \in\{0,1\}^N w ∈ { 0 , 1 } N interpreted as an assignment, iterates over all poly ( N ) \operatorname{poly}(N) poly ( N ) clauses of φ \varphi φ (each obtained by simulating C C C , which runs in time poly ( s ) \operatorname{poly}(s) poly ( s ) per clause), and accepts iff every clause is satisfied. Then M C M_C M C has size poly ( s ) \operatorname{poly}(s) poly ( s ) and runs in time T 0 = poly ( N ) ⋅ poly ( s ) T_0=\operatorname{poly}(N)\cdot\operatorname{poly}(s) T 0 = poly ( N ) ⋅ poly ( s ) ; let T = T 0 T=T_0 T = T 0 in binary, of size O ( log N ) = poly ( s ) O(\log N)=\operatorname{poly}(s) O ( log N ) = poly ( s ) bits. The equivalence φ ∈ S u c c i n c t - 3 S A T ⟺ ∃ w ∈ { 0 , 1 } N , ∃ t ≤ T , M C \varphi\in\mathrm{Succinct\text{-}3SAT}\Longleftrightarrow\exists w \in\{0,1\}^N,\ \exists t \le T,\ M_C φ ∈ Succinct - 3SAT ⟺ ∃ w ∈ { 0 , 1 } N , ∃ t ≤ T , M C accepts w w w in t t t steps yields the reduction.
(iii) RE-completeness (no time bound).
RE-membership. A semi-decision procedure enumerates pairs ( w , t ) ∈ Σ ∗ × N (w,t) \in\Sigma^*\times\mathbb{N} ( w , t ) ∈ Σ ∗ × N (e.g. by ∣ w ∣ + t |w|+t ∣ w ∣ + t increasing) and simulates M M M on w w w for t t t steps; it accepts iff an accepting configuration is reached.
RE-hardness. We reduce from the halting problem H A L T ϵ = { M : M halts on ϵ } \mathrm{HALT}_{\epsilon}=\{M:M\text{ halts on }\epsilon\} HALT ϵ = { M : M halts on ϵ } , which is RE-complete Arora and Barak [ [3 ] . Given M M M , let M ′ M' M ′ be the machine that ignores its input and simulates M M M on ϵ \epsilon ϵ . Then M ∈ H A L T ϵ M \in\mathrm{HALT}_{\epsilon} M ∈ HALT ϵ iff ∃ w ∈ Σ ∗ \exists w \in\Sigma^* ∃ w ∈ Σ ∗ , M ′ M' M ′ accepts w w w . The map M ↦ M ′ M \mapsto M' M ↦ M ′ is polynomial-time.
Remark 38 (Two binary-T T T variants: EXPTIME vs. NEXP). With T T T in binary, two natural variants of the decision problem above must be distinguished:
Fixed input. “Given M M M , a fixed input w w w , and T T T in binary, does M M M accept w w w in at most T T T steps?” This is EXPTIME-complete: the deterministic simulation runs in time T ≤ 2 ∣ T ∣ T \leq2^{|T|} T ≤ 2 ∣ T ∣ , and hardness follows from the time-hierarchy theorem.
Existential input. As in Lemma 37(ii) above: w w w is quantified existentially. This is NEXP-complete.
The two problems differ in whether w w w is part of the input or (fixed) quantified existentially. Our reduction in the proof of Theorem 7 encodes w w w as the real-valued point x ∈ I n i t x \in\mathrm{Init} x ∈ Init chosen existentially inside the network’s convex initial region, hence corresponds to the existential variant. This is why we obtain NEXP, not EXPTIME, for binary T T T .
By passing to a fixed universal Turing machine, the same statements hold with M M M replaced by an instance of a single fixed U U U .
Lemma 39 (Fixing the machine). There exists a fixed deterministic universal Turing machine U U U such that the three problems of Lemma 37 retain their respective complexity classifications when “M M M accepts w w w in t t t steps” is replaced by “U U U accepts ⟨ M , w ⟩ \langle M,w\rangle ⟨ M , w ⟩ in at most p U ( t , ∣ M ∣ ) p_U(t,|M|) p U ( t , ∣ M ∣ ) steps” for some fixed polynomial p U p_U p U .
Proof. Fix once and for all a deterministic universal Turing machine U U U with the standard property (see e.g. Hopcroft and Ullman [2000], Arora and Barak [2009]) that there exists a polynomial p U p_U p U such that, for every deterministic Turing machine M M M , every w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ , and every t ∈ N t \in\mathbb{N} t ∈ N ,
M accepts w in t steps ⟺ U accepts ⟨ M , w ⟩ in at most t ′ ≤ p U ( ∣ M ∣ , t ) steps , (1) M \text{ accepts } w \text{ in } t \text{ steps} \Longleftrightarrow U \text{ accepts } \langle M,w\rangle\text{ in at most } t' \leq p_U(|M|,t) \text{ steps}, \tag*{(1)} M accepts w in t steps ⟺ U accepts ⟨ M , w ⟩ in at most t ′ ≤ p U ( ∣ M ∣ , t ) steps , (1)
where ⟨ M , w ⟩ ∈ Σ ∗ \langle M,w\rangle\in\Sigma^* ⟨ M , w ⟩ ∈ Σ ∗ is a standard binary encoding of the pair, of size O ( ∣ M ∣ + ∣ w ∣ ) O(|M|+|w|) O ( ∣ M ∣ + ∣ w ∣ ) .
The map Φ : ( M , T ) ↦ ( M , p U ( ∣ M ∣ , T ) ) \Phi:(M,T) \mapsto(M,p_U(|M|,T)) Φ : ( M , T ) ↦ ( M , p U ( ∣ M ∣ , T )) (with Φ ( M ) = M \Phi(M)=M Φ ( M ) = M in case (iii)) is, by (1), a two-sided reduction between each item of Lemma 37 and its universal-machine variant. It remains to verify that Φ \Phi Φ is polynomial-time and that the resulting universal-machine variant falls into the claimed class.
For Lemma 37(i), T T T is in unary, so T ′ = p U ( ∣ M ∣ , T ) T'=p_U(|M|,T) T ′ = p U ( ∣ M ∣ , T ) is computable and written in unary in polynomial time. For Lemma 37(ii), T T T is in binary, so ∣ T ′ ∣ = O ( log p U ( ∣ M ∣ , T ) ) = poly ( ∣ M ∣ , ∣ T ∣ ) |T'|=O(\log p_U(|M|,T))=\operatorname{poly}(|M|,|T|) ∣ T ′ ∣ = O ( log p U ( ∣ M ∣ , T )) = poly ( ∣ M ∣ , ∣ T ∣ ) and Φ \Phi Φ is polynomial-time. For Lemma 37(iii), Φ \Phi Φ is the identity on M M M .
In each case, membership in the appropriate class (NP/NEXP/RE) follows by viewing the universal-machine variant as a special case of Lemma 37 applied to the single fixed machine U U U on inputs of the form ⟨ M , w ⟩ \langle M,w\rangle ⟨ M , w ⟩ : the new time bound is T ′ = p U ( T , ∣ M ∣ ) T'=p_U(T,|M|) T ′ = p U ( T , ∣ M ∣ ) , which has the same encoding type as T T T (unary/binary/none, depending on the item); the size of ⟨ M , w ⟩ \langle M,w\rangle ⟨ M , w ⟩ is polynomial in ∣ M ∣ |M| ∣ M ∣ and ∣ w ∣ |w| ∣ w ∣ . Hardness follows from (1) together with the hardness part of the corresponding item of Lemma 37.
Proof of thm:verif-spectrum
We now assemble the ingredients to give a formal proof of Theorem 7, restating the result for convenience.
Theorem (Theorem 7, restated). The bounded-time recurrent reachability problem (Definition 19) for width-4 ReLU networks is:
NP-complete when T T T is encoded in unary;
NEXP-complete when T T T is encoded in binary;
RE-complete (undecidable) when T T T is unbounded.
Reduction recipe (uniform across (i)–(iii)). For each item, we reduce a Turing-machine acceptance problem to width-4 recurrent reachability. The reduction is identical across items; only the source problem and the encoding of T T T vary.
Let M M M be a deterministic Turing machine and T ∈ N T \in\mathbb{N} T ∈ N a time bound (unary, binary, or absent). By Theorem 3, applied to M M M , we obtain a width-4 ReLU network N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 N_M : [0,1]^4 \to[0,1]^4 N M : [ 0 , 1 ] 4 → [ 0 , 1 ] 4 of depth D M = poly ( ∣ M ∣ ) D_M = \operatorname{poly}(|M|) D M = poly ( ∣ M ∣ ) , constructible in polynomial time, with the simulation property (part (i)) and the online certificate property (part (ii)). Recall from Appendix § 9 that the second coordinate x 2 x_2 x 2 co-encodes the state and right tape: a state-prefix enc M ( q ) ∈ { 0 , 1 , … , 4 ∣ q ∣ 4 − 1 } ⋅ 4 − ∣ q ∣ 4 \operatorname{enc}_M(q) \in\{0,1,\ldots,4^{|q|_4}-1\}\cdot4^{-|q|_4} enc M ( q ) ∈ { 0 , 1 , … , 4 ∣ q ∣ 4 − 1 } ⋅ 4 − ∣ q ∣ 4 of length ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣ ⌉ |q|_4 = \lceil\log_4 |Q| \rceil ∣ q ∣ 4 = ⌈ log 4 ∣ Q ∣ ⌉ is followed by a D D 1 , 3 \mathbb{D}\mathbb{D}_{1,3} D D 1 , 3 -encoded right tape.
Define the convex regions
Init : = { x ∈ [ 0 , 1 ] 4 : enc M ( q 0 ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q 0 ) + 1 , x 3 = 0 , x 4 = 0 } , \operatorname{Init} := \{x \in[0,1]^4 : \operatorname{enc}_M(q_0) \le4^{|q|_4}x_2 \le\operatorname{enc}_M(q_0)+1,\ x_3=0,\ x_4=0\}, Init := { x ∈ [ 0 , 1 ] 4 : enc M ( q 0 ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q 0 ) + 1 , x 3 = 0 , x 4 = 0 } ,
Acc : = { x ∈ [ 0 , 1 ] 4 : enc M ( q F ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q F ) + 1 , x 4 ≤ 0 } . \operatorname{Acc} := \{x \in[0,1]^4 : \operatorname{enc}_M(q_F) \le4^{|q|_4}x_2 \le\operatorname{enc}_M(q_F)+1,\ x_4 \le0\}. Acc := { x ∈ [ 0 , 1 ] 4 : enc M ( q F ) ≤ 4 ∣ q ∣ 4 x 2 ≤ enc M ( q F ) + 1 , x 4 ≤ 0 } .
Both regions are specified by axis-aligned linear inequalities with rational coefficients of bit complexity O ( ∣ q ∣ 4 ) = O ( log ∣ M ∣ ) O(|q|_4)=O(\log|M|) O ( ∣ q ∣ 4 ) = O ( log ∣ M ∣ ) , hence convex and polynomial-time constructible from M M M .
The reduction maps the Turing-machine instance ( M , T ) (M,T) ( M , T ) (or just M M M for case (iii)) to the reachability instance ( N M , Init , Acc , T ⋅ C M ) (N_M,\operatorname{Init},\operatorname{Acc},T \cdot C_M) ( N M , Init , Acc , T ⋅ C M ) , where C M C_M C M is the per-step iteration count of Theorem 3.
Correctness of the recipe. We claim:
There exist x ∈ Init and t ≤ T ⋅ C M with N M [ t ] ( x ) ∈ Acc ⟺ ∃ τ ∈ { 0 , 1 } ω , ∃ t ′ ≤ T , M accepts τ in t ′ steps . (2) \text{There exist }x \in\operatorname{Init}\text{ and }t \le T \cdot C_M\text{ with }N_M^{[t]}(x) \in\operatorname{Acc}
\Longleftrightarrow
\exists\tau\in\{0,1\}^{\omega},\ \exists t' \le T,\ M\text{ accepts }\tau\text{ in }t'\text{ steps}. \tag*{(2)} There exist x ∈ Init and t ≤ T ⋅ C M with N M [ t ] ( x ) ∈ Acc ⟺ ∃ τ ∈ { 0 , 1 } ω , ∃ t ′ ≤ T , M accepts τ in t ′ steps . (2)
( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose x ∈ Init x \in\operatorname{Init} x ∈ Init and N M [ t ] ( x ) ∈ Acc N_M^{[t]}(x) \in\operatorname{Acc} N M [ t ] ( x ) ∈ Acc for some t ≤ T ⋅ C M t \le T \cdot C_M t ≤ T ⋅ C M . We have x 4 ( 0 ) = 0 x_4(0)=0 x 4 ( 0 ) = 0 and π 4 ( N M [ t ] ( x ) ) ≤ 0 \pi_4(N_M^{[t]}(x)) \le0 π 4 ( N M [ t ] ( x )) ≤ 0 (since N M [ t ] ( x ) ∈ Acc N_M^{[t]}(x) \in\operatorname{Acc} N M [ t ] ( x ) ∈ Acc ). By monotonicity of x 4 x_4 x 4 along the trajectory (Lemma 35 (a)), this forces π 4 ( N M [ k ] ( x ) ) = 0 \pi_4(N_M^{[k]}(x))=0 π 4 ( N M [ k ] ( x )) = 0 for every k ≤ t k \le t k ≤ t . By items (b)–(c) of Lemma 35 , every step k ≤ t k \le t k ≤ t is locally valid: the leading digit of x 1 ( k ) x_1^{(k)} x 1 ( k ) and of the tape-suffix of x 2 ( k ) x_2^{(k)} x 2 ( k ) lies in { 1 , 3 } \{1,3\} { 1 , 3 } , and the state-prefix of x 2 ( k ) x_2^{(k)} x 2 ( k ) lies in enc M ( Q ) \operatorname{enc}_M(Q) enc M ( Q ) . Since N M N_M N M acts by affine maps that are uniform on leading-digit cylinders, the state prefixes of its first t t t iterates depend only on the digits visited during the first t t t iterations. Let x ′ x' x ′ be obtained from x x x by setting every unvisited digit of x 1 x_1 x 1 and of the tape-suffix of x 2 x_2 x 2 to 1 1 1 . Then x ′ x' x ′ encodes a configuration c 0 ( τ ) c_0(\tau) c 0 ( τ ) with τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω , and N M [ k ] ( x ) N_M^{[k]}(x) N M [ k ] ( x ) and N M [ k ] ( x ′ ) N_M^{[k]}(x') N M [ k ] ( x ′ ) have the same state prefix for every k ≤ t k \le t k ≤ t . By Theorem 3(i), N M N_M N M faithfully simulates M M M on the infinite binary tape τ \tau τ encoded by x ′ x' x ′ , and its trajectory reaches a state-encoded q F q_F q F at iteration ≤ t \le t ≤ t . Hence M M M accepts τ \tau τ in some t ′ ≤ t / C M ≤ T t' \le t/C_M \le T t ′ ≤ t / C M ≤ T steps.
( ⇐ ) (\Leftarrow) ( ⇐ ) Conversely, suppose M M M accepts some τ ∈ { 0 , 1 } ω \tau\in\{0,1\}^{\omega} τ ∈ { 0 , 1 } ω in t ′ ≤ T t' \le T t ′ ≤ T steps. Set x = enc M ( c 0 ( τ ) ) ∈ Init x=\operatorname{enc}_M(c_0(\tau)) \in\operatorname{Init} x = enc M ( c 0 ( τ )) ∈ Init . By Theorem 3(i), N M [ C M t ′ ] ( x ) = enc M ( c t ′ ( τ ) ) N_M^{[C_Mt']}(x)=\operatorname{enc}_M(c_{t'}(\tau)) N M [ C M t ′ ] ( x ) = enc M ( c t ′ ( τ )) , whose state-prefix is enc M ( q F ) \operatorname{enc}_M(q_F) enc M ( q F ) and whose fourth coordinate is 0 0 0 (by Lemma 35 (b), since the trajectory remains within encoded configurations). Hence N M [ C M t ′ ] ( x ) ∈ Acc N_M^{[C_Mt']}(x) \in\operatorname{Acc} N M [ C M t ′ ] ( x ) ∈ Acc with C M t ′ ≤ T ⋅ C M C_Mt' \le T \cdot C_M C M t ′ ≤ T ⋅ C M .
Polynomial-time computability. The reduction ( M , T ) ↦ ( N M , Init , Acc , T ⋅ C M ) (M,T) \mapsto(N_M,\operatorname{Init},\operatorname{Acc},T \cdot C_M) ( M , T ) ↦ ( N M , Init , Acc , T ⋅ C M ) is polynomial-time: N M N_M N M is constructed in poly ( ∣ M ∣ ) \operatorname{poly}(|M|) poly ( ∣ M ∣ ) by Theorem 3; Init \operatorname{Init} Init and Acc \operatorname{Acc} Acc are described by O ( ∣ q ∣ 4 ) = O ( log ∣ M ∣ ) O(|q|_4)=O(\log|M|) O ( ∣ q ∣ 4 ) = O ( log ∣ M ∣ ) rational coefficients; and the new time bound T ⋅ C M T \cdot C_M T ⋅ C M has size ∣ T ∣ + poly ( ∣ M ∣ ) |T|+\operatorname{poly}(|M|) ∣ T ∣ + poly ( ∣ M ∣ ) , which preserves the encoding (unary stays unary, binary stays binary).
Hardness of (i)–(iii). Apply the recipe with the source problems of Lemma 37 :
(i) Source: Lemma 37 (i), NP-complete with unary T T T . The recipe yields a polynomial-time reduction to width-4 reachability with unary time bound T ⋅ C M T \cdot C_M T ⋅ C M .
(ii) Source: Lemma 37 (ii), NEXP-complete with binary T T T . The recipe yields a polynomial-time reduction preserving the binary encoding of the time bound.
(iii) Source: Lemma 37 (iii), RE-complete with no time bound. The recipe yields a polynomial-time reduction to unbounded reachability.
Membership in (i): NP. Given ( M , T ) (M,T) ( M , T ) with T T T in unary, build ( N M , I n i t , A c c , T ⋅ C M ) (N_M,\mathrm{Init},\mathrm{Acc},T \cdot C_M) ( N M , Init , Acc , T ⋅ C M ) in polynomial time. By Lemma 36 applied with parameters d = 4 d=4 d = 4 , w = 4 w=4 w = 4 , L = D M = poly ( ∣ M ∣ ) L=D_M=\operatorname{poly}(|M|) L = D M = poly ( ∣ M ∣ ) , time bound T ⋅ C M = poly ( ∣ M ∣ , T ) T \cdot C_M=\operatorname{poly}(|M|,T) T ⋅ C M = poly ( ∣ M ∣ , T ) , weight bit complexity b = poly ( ∣ M ∣ ) b=\operatorname{poly}(|M|) b = poly ( ∣ M ∣ ) , and region bit complexity b ′ = O ( log ∣ M ∣ ) b'=O(\log|M|) b ′ = O ( log ∣ M ∣ ) , any reachability witness can be taken rational of bit complexity poly ( ∣ M ∣ , T ) \operatorname{poly}(|M|,T) poly ( ∣ M ∣ , T ) . A nondeterministic verifier guesses such a rational x ∈ I n i t x \in\mathrm{Init} x ∈ Init , simulates N M N_M N M exactly for T ⋅ C M T \cdot C_M T ⋅ C M iterations, and checks at each step whether the trajectory enters A c c \mathrm{Acc} Acc . Total time is poly ( ∣ M ∣ , T ) \operatorname{poly}(|M|,T) poly ( ∣ M ∣ , T ) , hence NP-membership.
Membership in (ii): NEXP. Given ( M , T ) (M,T) ( M , T ) with T T T in binary, build ( N M , I n i t , A c c , T ⋅ C M ) (N_M,\mathrm{Init},\mathrm{Acc},T \cdot C_M) ( N M , Init , Acc , T ⋅ C M ) as before. Apply Lemma 36 with the same parameters except T ⋅ C M T \cdot C_M T ⋅ C M now binary, of bit length ∣ T ∣ + O ( log ∣ M ∣ ) |T|+O(\log|M|) ∣ T ∣ + O ( log ∣ M ∣ ) . The lemma yields a rational witness of bit complexity poly ( ∣ M ∣ , T ) \operatorname{poly}(|M|,T) poly ( ∣ M ∣ , T ) , which is exponential in the input size ∣ M ∣ + ∣ T ∣ |M|+|T| ∣ M ∣ + ∣ T ∣ . A nondeterministic verifier guesses such a witness in poly ( ∣ M ∣ , T ) = 2 poly ( ∣ M ∣ , ∣ T ∣ ) \operatorname{poly}(|M|,T)=2^{\operatorname{poly}(|M|,|T|)} poly ( ∣ M ∣ , T ) = 2 poly ( ∣ M ∣ , ∣ T ∣ ) nondeterministic time, then simulates N M N_M N M for T ⋅ C M = 2 O ( ∣ T ∣ ) ⋅ poly ( ∣ M ∣ ) T \cdot C_M=2^{O(|T|)}\cdot\operatorname{poly}(|M|) T ⋅ C M = 2 O ( ∣ T ∣ ) ⋅ poly ( ∣ M ∣ ) steps in deterministic exponential time. Total nondeterministic running time is 2 poly ( ∣ M ∣ , ∣ T ∣ ) 2^{\operatorname{poly}(|M|,|T|)} 2 poly ( ∣ M ∣ , ∣ T ∣ ) , hence NEXP-membership.
Membership in (iii): RE. A semi-decision procedure simulates N M N_M N M from each rational point of I n i t \mathrm{Init} Init enumerated in some computable order, for increasing numbers of iterations, accepting if the trajectory ever enters A c c \mathrm{Acc} Acc . By Lemma 36, if the instance is positive then some rational x ∈ I n i t x \in\mathrm{Init} x ∈ Init of finite bit complexity reaches A c c \mathrm{Acc} Acc in finite time, so the procedure halts and accepts on positive instances. Hence the problem is in RE.
Combining hardness and membership in each case proves Theorem 7.
Robust hardness transfer from ReLU to smooth activations
This appendix proves Theorem 10 by transferring NP-hardness from ReLU networks at width 4 to ρ \rho ρ -networks at width 6. We work with the register form of ReLU networks, in which each hidden layer updates a single coordinate.
The key technical ingredient, used to construct identity-preserving gadgets and approximate ReLU from ρ \rho ρ , is the local-identity approximation of Kidger and Lyons [ [25 ] .
Proposition 40 (Local approximation of the identity, Kidger and Lyons, 2020, Lemma 4.1). Let ρ : R → R \rho:\mathbb{R}\to\mathbb{R} ρ : R → R be continuous and continuously differentiable at at least one point with nonzero derivative there. Let L ⊆ R L\subseteq\mathbb{R} L ⊆ R be compact. Then a single enhanced neuron with activation ρ \rho ρ uniformly approximates the identity function I d : R → R \mathrm{Id}:\mathbb{R}\to\mathbb{R} Id : R → R on L L L , with arbitrarily small error.
Proof sketch (after Kidger and Lyons, 2020). By hypothesis there exist α ∈ R \alpha\in\mathbb{R} α ∈ R where ρ \rho ρ is continuously differentiable with ρ ′ ( α ) ≠ 0 \rho'(\alpha)\ne0 ρ ′ ( α ) = 0 . For h ∈ R ∖ { 0 } h\in\mathbb{R}\setminus\{0\} h ∈ R ∖ { 0 } set ϕ h ( x ) = h x + α \phi_h(x)=hx+\alpha ϕ h ( x ) = h x + α and ψ h ( x ) = ( x − ρ ( α ) ) / ( h ρ ′ ( α ) ) \psi_h(x)=(x-\rho(\alpha))/\left(h\rho'(\alpha)\right) ψ h ( x ) = ( x − ρ ( α )) / ( h ρ ′ ( α ) ) . Then h ↦ ψ h ∘ ρ ∘ ϕ h h\mapsto\psi_h\circ\rho\circ\phi_h h ↦ ψ h ∘ ρ ∘ ϕ h is realized by a single enhanced neuron, and ψ h ( x ) → x \psi_h(x)\to x ψ h ( x ) → x uniformly on any compact L L L as h → 0 h\to0 h → 0 , by the mean-value theorem applied to ρ \rho ρ on [ α , α + h x ] [\alpha,\alpha+hx] [ α , α + h x ] .
Register networks
Definition 41 (ReLU-register network, restated from Definition 15). A ReLU-register network F : R d → R d F:\mathbb{R}^d\to\mathbb{R}^d F : R d → R d of register width k k k and depth L L L is a composition
F = A o u t ∘ R L ∘ ⋯ ∘ R 1 ∘ A i n : R d → R d , F=A_{\mathrm{out}}\circ R_L\circ\cdots\circ R_1\circ A_{\mathrm{in}}:\mathbb{R}^d\to\mathbb{R}^d, F = A out ∘ R L ∘ ⋯ ∘ R 1 ∘ A in : R d → R d ,
where A i n : R d → R k A_{\mathrm{in}}:\mathbb{R}^d\to\mathbb{R}^k A in : R d → R k and A o u t : R k → R d A_{\mathrm{out}}:\mathbb{R}^k\to\mathbb{R}^d A out : R k → R d are affine, and each register-layer R ℓ : R k → R k R_\ell:\mathbb{R}^k\to\mathbb{R}^k R ℓ : R k → R k is of the form: there exist an index j ℓ ∈ { 1 , … , k } j_\ell\in\{1,\ldots,k\} j ℓ ∈ { 1 , … , k } and parameters a ℓ ∈ R k a_\ell\in\mathbb{R}^k a ℓ ∈ R k , b ℓ ∈ R b_\ell\in\mathbb{R} b ℓ ∈ R such that ( R ℓ ( x ) ) i = x i (R_\ell(x))_i=x_i ( R ℓ ( x ) ) i = x i for i ≠ j ℓ i\ne j_\ell i = j ℓ and ( R ℓ ( x ) ) j ℓ = ReLU ( a ℓ ⋅ x + b ℓ ) (R_\ell(x))_{j_\ell}=\operatorname{ReLU}(a_\ell\cdot x+b_\ell) ( R ℓ ( x ) ) j ℓ = ReLU ( a ℓ ⋅ x + b ℓ ) .
Remark 42 (Native register form of N M N_M N M ). The network N M N_M N M of Theorem 3 is, by its construction, in register form of register width 4:
the width-3 simulator g M g_M g M of Theorem 26 is in register form by the construction of Bournez et al. [ [11 ] ;
the certificate update x 4 ← max { x 4 , ε ( x 1 , x 2 ) } x_4\leftarrow\max\{x_4,\varepsilon(x_1,x_2)\} x 4 ← max { x 4 , ε ( x 1 , x 2 )} modifies a single coordinate, computed in width 2 via max { a , b } = a + ReLU ( b − a ) \max\{a,b\}=a+\operatorname{ReLU}(b-a) max { a , b } = a + ReLU ( b − a ) ;
In particular, N M N_M N M can be passed directly to the ρ \rho ρ -emulation of Lemma 17 below without any preliminary register-form conversion.
Approximation of ReLU register networks by smooth networks
We approximate ReLU-register networks by ρ \rho ρ -networks in two steps: first one register-layer at a time (Lemma 43 ), then the entire network by telescoping (Lemma 17 ).
This is precisely Lemma 16 of the main body, which we restate and prove here.
Lemma 43 (Approximating one ReLU register-layer at width k + 2 k+2 k + 2 ). Let ρ : R → R \rho:\mathbb{R}\to\mathbb{R} ρ : R → R be continuous, non-polynomial, and C 1 C^1 C 1 at some point with non-zero derivative. Fix k ≥ 1 k\ge1 k ≥ 1 , a compact set K ⊆ R k K\subseteq\mathbb{R}^k K ⊆ R k , an index j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } , and parameters a ∈ R k a\in\mathbb{R}^k a ∈ R k , b ∈ R b\in\mathbb{R} b ∈ R . Consider the ReLU register-layer F : R k → R k F:\mathbb{R}^k\to\mathbb{R}^k F : R k → R k with F i ( x ) = x i F_i(x)=x_i F i ( x ) = x i for i ≠ j i\ne j i = j and F j ( x ) = ReLU ( a ⋅ x + b ) F_j(x)=\operatorname{ReLU}(a\cdot x+b) F j ( x ) = ReLU ( a ⋅ x + b ) . Then for every ε > 0 \varepsilon>0 ε > 0 there exists a ρ \rho ρ -network F ~ ∈ N k , k , k + 2 ρ \widetilde{F}\in\mathcal{N}^{\rho}_{k,k,k+2} F ∈ N k , k , k + 2 ρ , constructible in time poly ( k , log ( 1 / ε ) , size ( a , b ) ) \operatorname{poly}(k,\log(1/\varepsilon),\operatorname{size}(a,b)) poly ( k , log ( 1/ ε ) , size ( a , b )) , such that
sup x ∈ K ∥ F ~ ( x ) − F ( x ) ∥ ∞ ≤ ε . \sup_{x\in K}\lVert\widetilde{F}(x)-F(x)\rVert_{\infty}\le\varepsilon. x ∈ K sup ∥ F ( x ) − F ( x ) ∥ ∞ ≤ ε .
Proof. The strategy is to dedicate k k k of the k + 2 k+2 k + 2 neurons to approximating the identity on the k k k register coordinates, and the remaining 2 neurons to approximating the ReLU operation z ↦ ReLU ( a ⋅ x + b ) z\mapsto\operatorname{ReLU}(a\cdot x+b) z ↦ ReLU ( a ⋅ x + b ) . Coordinates are then assembled via the output affine map.
Step 1: ingredients. By hypothesis on ρ \rho ρ and Proposition 40 , for every compact L ⊆ R L\subseteq\mathbb{R} L ⊆ R and every η > 0 \eta>0 η > 0 there exists a single enhanced ρ \rho ρ -neuron computing a function ι η : R → R \iota_\eta:\mathbb{R}\to\mathbb{R} ι η : R → R with sup z ∈ L ∣ ι η ( z ) − z ∣ ≤ η \sup_{z\in L}|\iota_\eta(z)-z|\le\eta sup z ∈ L ∣ ι η ( z ) − z ∣ ≤ η .
By the effective ReLU emulation result of Zhang et al. [ [44 ] (see also Kidger and Lyons, [25 ] , Theorem 4.3 for existence), for activations satisfying (H1)–(H3) and every compact L ′ ⊆ R L'\subseteq\mathbb{R} L ′ ⊆ R and every η > 0 \eta>0 η > 0 , there exists a ρ \rho ρ -network R η : R → R R_\eta:\mathbb{R}\to\mathbb{R} R η : R → R of width 2 and constant depth, constructible in time poly ( log ( 1 / η ) , log B ) \operatorname{poly}(\log(1/\eta),\log B) poly ( log ( 1/ η ) , log B ) where B = sup z ∈ L ′ ∣ z ∣ B=\sup_{z\in L'}|z| B = sup z ∈ L ′ ∣ z ∣ , such that sup z ∈ L ′ ∣ R η ( z ) − ReLU ( z ) ∣ ≤ η \sup_{z\in L'}|R_\eta(z)-\operatorname{ReLU}(z)|\le\eta sup z ∈ L ′ ∣ R η ( z ) − ReLU ( z ) ∣ ≤ η .
Step 2: compact sets used. Let C a : = sup x ∈ K ∣ a ⋅ x + b ∣ C_a:=\sup_{x\in K}|a\cdot x+b| C a := sup x ∈ K ∣ a ⋅ x + b ∣ , finite by compactness of K K K , and set L ′ : = [ − C a , C a ] L':=[-C_a,C_a] L ′ := [ − C a , C a ] . Let L ⊆ R L\subseteq\mathbb{R} L ⊆ R be a compact set containing every coordinate value x i x_i x i for x ∈ K x\in K x ∈ K , i ∈ { 1 , … , k } i\in\{1,\ldots,k\} i ∈ { 1 , … , k } .
Step 3: construction of F ~ \widetilde{F} F . Set η : = ε \eta:=\varepsilon η := ε and define F ~ ∈ N k , k , k + 2 ρ \widetilde{F}\in\mathcal{N}^{\rho}_{k,k,k+2} F ∈ N k , k , k + 2 ρ as follows. The hidden layer has k + 2 k+2 k + 2 neurons:
Neurons 1 , … , k 1,\ldots,k 1 , … , k : each neuron i i i takes input x i x_i x i via the input affine map and applies the identity-emulating gadget ι η \iota_\eta ι η on L L L . By Step 1, neuron i i i outputs ι η ( x i ) \iota_\eta(x_i) ι η ( x i ) with ∣ ι η ( x i ) − x i ∣ ≤ η |\iota_\eta(x_i)-x_i|\le\eta ∣ ι η ( x i ) − x i ∣ ≤ η for x ∈ K x\in K x ∈ K .
Neurons k + 1 k+1 k + 1 and k + 2 k+2 k + 2 : jointly compute the ReLU gadget R η R_\eta R η applied to the pre-activation a ⋅ x + b a\cdot x+b a ⋅ x + b , formed via the input affine map. By Step 1, the combined output approximates ReLU ( a ⋅ x + b ) \operatorname{ReLU}(a\cdot x+b) ReLU ( a ⋅ x + b ) within η \eta η on L ′ L' L ′ .
The output affine map assembles the k k k output coordinates: for i ≠ j i\ne j i = j , set F ~ i ( x ) : = ι η ( x i ) \widetilde{F}_i(x):=\iota_\eta(x_i) F i ( x ) := ι η ( x i ) ; for i = j i=j i = j , set F ~ j ( x ) : = R η ( a ⋅ x + b ) \widetilde{F}_j(x):=R_\eta(a\cdot x+b) F j ( x ) := R η ( a ⋅ x + b ) .
Step 4: error bound. For every x ∈ K x\in K x ∈ K and every coordinate i i i :
if i ≠ j i\ne j i = j : ∣ F ~ i ( x ) − F i ( x ) ∣ = ∣ ι η ( x i ) − x i ∣ ≤ η = ε |\widetilde{F}_i(x)-F_i(x)|=|\iota_\eta(x_i)-x_i|\le\eta=\varepsilon ∣ F i ( x ) − F i ( x ) ∣ = ∣ ι η ( x i ) − x i ∣ ≤ η = ε ;
if i = j i=j i = j : ∣ F ~ j ( x ) − F j ( x ) ∣ = ∣ R η ( a ⋅ x + b ) − ReLU ( a ⋅ x + b ) ∣ ≤ η = ε |\widetilde{F}_j(x)-F_j(x)|=|R_\eta(a\cdot x+b)-\operatorname{ReLU}(a\cdot x+b)|\le\eta=\varepsilon ∣ F j ( x ) − F j ( x ) ∣ = ∣ R η ( a ⋅ x + b ) − ReLU ( a ⋅ x + b ) ∣ ≤ η = ε .
Hence ∥ F ~ ( x ) − F ( x ) ∥ ∞ ≤ ε \lVert\widetilde{F}(x)-F(x)\rVert_\infty\le\varepsilon ∥ F ( x ) − F ( x ) ∥ ∞ ≤ ε uniformly on K K K .
Step 5: constructibility. Both ι η \iota_\eta ι η and R η R_\eta R η are constructed by the proofs of Proposition 40 and Theorem 4.3 of Kidger and Lyons [ [25 ] in time poly ( log ( 1 / η ) , size ( a , b ) ) \operatorname{poly}(\log(1/\eta),\operatorname{size}(a,b)) poly ( log ( 1/ η ) , size ( a , b )) . ∎
We now lift the per-layer approximation to a network-level statement. This is precisely Lemma 17 of the main body, which we restate and prove here.
Lemma 44 (Lemma 17, restated). Let ρ : R → R \rho:\mathbb{R}\to\mathbb{R} ρ : R → R be continuous, non-polynomial, and C 1 C^1 C 1 at some point with non-zero derivative. Let F : R d → R d F:\mathbb{R}^{d}\to\mathbb{R}^{d} F : R d → R d be a ReLU-register network of register width k k k and depth L L L , let K ⊆ R d K\subseteq\mathbb{R}^{d} K ⊆ R d be compact, and let ε > 0 \varepsilon>0 ε > 0 . Then there exists a ρ \rho ρ -network F ~ ∈ N d , d , k + 2 ρ \widetilde{F}\in\mathcal{N}^{\rho}_{d,d,k+2} F ∈ N d , d , k + 2 ρ of depth O ( L ) O(L) O ( L ) , constructible in time poly ( ∣ F ∣ , log ( 1 / ε ) ) \operatorname{poly}(|F|,\log(1/\varepsilon)) poly ( ∣ F ∣ , log ( 1/ ε )) , such that
sup x ∈ K ∥ F ~ ( x ) − F ( x ) ∥ ∞ ≤ ε . \sup_{x\in K}\|\widetilde{F}(x)-F(x)\|_{\infty}\leq\varepsilon. x ∈ K sup ∥ F ( x ) − F ( x ) ∥ ∞ ≤ ε .
Proof. Write F = A o u t ∘ R L ∘ ⋯ ∘ R 1 ∘ A i n F=A_{\mathrm{out}}\circ R_L\circ\cdots\circ R_1\circ A_{\mathrm{in}} F = A out ∘ R L ∘ ⋯ ∘ R 1 ∘ A in . Let L ℓ : = max { 1 , ∥ a ℓ ∥ 1 } L_\ell:=\max\{1,\|a_\ell\|_1\} L ℓ := max { 1 , ∥ a ℓ ∥ 1 } be the Lipschitz constant of R ℓ R_\ell R ℓ in ∥ ⋅ ∥ ∞ \|\cdot\|_\infty ∥ ⋅ ∥ ∞ (since ReLU is 1-Lipschitz and ∣ a ℓ ⋅ u ∣ ≤ ∥ a ℓ ∥ 1 ∥ u ∥ ∞ |a_\ell\cdot u|\leq\|a_\ell\|_1\|u\|_\infty ∣ a ℓ ⋅ u ∣ ≤ ∥ a ℓ ∥ 1 ∥ u ∥ ∞ ); let L o u t L_{\mathrm{out}} L out be the Lipschitz constant of A o u t A_{\mathrm{out}} A out .
Step 1: compact propagation with buffer. Set K 0 : = A i n ( K ) K_0:=A_{\mathrm{in}}(K) K 0 := A in ( K ) and inductively K ℓ : = R ℓ ( K ℓ − 1 ) K_\ell:=R_\ell(K_{\ell-1}) K ℓ := R ℓ ( K ℓ − 1 ) , all compact in R k \mathbb{R}^{k} R k . Let η : = ε / L o u t \eta:=\varepsilon/L_{\mathrm{out}} η := ε / L out and define the enlarged compacts K ℓ + : = K ℓ + B η K_\ell^+:=K_\ell+B_\eta K ℓ + := K ℓ + B η (closed η \eta η -neighborhood in ∥ ⋅ ∥ ∞ \|\cdot\|_\infty ∥ ⋅ ∥ ∞ ).
Step 2: per-layer approximation. Apply Lemma 43 on K ℓ − 1 + K_{\ell-1}^+ K ℓ − 1 + with target precision
δ ℓ : = ε L o u t ⋅ ( L + 1 ) ⋅ ∏ t = ℓ + 1 L L t , \delta_\ell:=\frac{\varepsilon}{L_{\mathrm{out}}\cdot(L+1)\cdot\prod_{t=\ell+1}^{L}L_t}, δ ℓ := L out ⋅ ( L + 1 ) ⋅ ∏ t = ℓ + 1 L L t ε ,
producing a ρ \rho ρ -block R ~ ℓ ∈ N k , k , k + 2 ρ \widetilde{R}_\ell\in\mathcal{N}^{\rho}_{k,k,k+2} R ℓ ∈ N k , k , k + 2 ρ such that
sup u ∈ K ℓ − 1 + ∥ R ~ ℓ ( u ) − R ℓ ( u ) ∥ ∞ ≤ δ ℓ . \sup_{u\in K_{\ell-1}^+}\|\widetilde{R}_\ell(u)-R_\ell(u)\|_\infty\leq\delta_\ell. u ∈ K ℓ − 1 + sup ∥ R ℓ ( u ) − R ℓ ( u ) ∥ ∞ ≤ δ ℓ .
The block is constructible in time poly ( k , log ( 1 / δ ℓ ) , size ( a ℓ , b ℓ ) ) = poly ( ∣ F ∣ , log ( 1 / ε ) ) \operatorname{poly}(k,\log(1/\delta_\ell),\operatorname{size}(a_\ell,b_\ell))=\operatorname{poly}(|F|,\log(1/\varepsilon)) poly ( k , log ( 1/ δ ℓ ) , size ( a ℓ , b ℓ )) = poly ( ∣ F ∣ , log ( 1/ ε )) .
Step 3: composed network. Define F ~ : = A o u t ∘ R ~ L ∘ ⋯ ∘ R ~ 1 ∘ A i n \widetilde{F}:=A_{\mathrm{out}}\circ\widetilde{R}_L\circ\cdots\circ\widetilde{R}_1\circ A_{\mathrm{in}} F := A out ∘ R L ∘ ⋯ ∘ R 1 ∘ A in . Each R ~ ℓ \widetilde{R}_\ell R ℓ has width k + 2 k+2 k + 2 and constant depth, so F ~ \widetilde{F} F has width k + 2 k+2 k + 2 and depth O ( L ) O(L) O ( L ) .
Step 4: error telescoping. For x ∈ K x\in K x ∈ K , let ξ ℓ ( x ) : = R ℓ ∘ ⋯ ∘ R 1 ∘ A i n ( x ) ∈ K ℓ \xi_\ell(x):=R_\ell\circ\cdots\circ R_1\circ A_{\mathrm{in}}(x)\in K_\ell ξ ℓ ( x ) := R ℓ ∘ ⋯ ∘ R 1 ∘ A in ( x ) ∈ K ℓ and ξ ~ ℓ ( x ) : = R ~ ℓ ∘ ⋯ ∘ R ~ 1 ∘ A i n ( x ) \widetilde{\xi}_\ell(x):=\widetilde{R}_\ell\circ\cdots\circ\widetilde{R}_1\circ A_{\mathrm{in}}(x) ξ ℓ ( x ) := R ℓ ∘ ⋯ ∘ R 1 ∘ A in ( x ) , with E ℓ ( x ) : = ∥ ξ ~ ℓ ( x ) − ξ ℓ ( x ) ∥ ∞ E_\ell(x):=\|\widetilde{\xi}_\ell(x)-\xi_\ell(x)\|_\infty E ℓ ( x ) := ∥ ξ ℓ ( x ) − ξ ℓ ( x ) ∥ ∞ and E 0 ≡ 0 E_0\equiv0 E 0 ≡ 0 .
We claim by induction that ξ ~ ℓ ( x ) ∈ K ℓ + \widetilde{\xi}_\ell(x)\in K_\ell^+ ξ ℓ ( x ) ∈ K ℓ + and E ℓ ( x ) ≤ ∑ j = 1 ℓ δ j ∏ t = j + 1 ℓ L t E_\ell(x)\leq\sum_{j=1}^{\ell}\delta_j\prod_{t=j+1}^{\ell}L_t E ℓ ( x ) ≤ ∑ j = 1 ℓ δ j ∏ t = j + 1 ℓ L t for every x ∈ K x\in K x ∈ K and ℓ ≤ L \ell\leq L ℓ ≤ L . The base case ℓ = 0 \ell=0 ℓ = 0 is immediate. Assume both claims for ℓ − 1 \ell-1 ℓ − 1 . Then ξ ~ ℓ − 1 ( x ) ∈ K ℓ − 1 + \widetilde{\xi}_{\ell-1}(x)\in K_{\ell-1}^+ ξ ℓ − 1 ( x ) ∈ K ℓ − 1 + , so the approximation guarantee for R ~ ℓ \widetilde{R}_\ell R ℓ applies at this point, giving
E ℓ ( x ) ≤ ∥ R ~ ℓ ( ξ ~ ℓ − 1 ) − R ℓ ( ξ ~ ℓ − 1 ) ∥ ∞ + ∥ R ℓ ( ξ ~ ℓ − 1 ) − R ℓ ( ξ ℓ − 1 ) ∥ ∞ ≤ δ ℓ + L ℓ ⋅ E ℓ − 1 ( x ) . \begin{aligned}
E_\ell(x)&\leq\|\widetilde{R}_\ell(\widetilde{\xi}_{\ell-1})-R_\ell(\widetilde{\xi}_{\ell-1})\|_\infty+\|R_\ell(\widetilde{\xi}_{\ell-1})-R_\ell(\xi_{\ell-1})\|_\infty\\
&\leq\delta_\ell+L_\ell\cdot E_{\ell-1}(x).
\end{aligned} E ℓ ( x ) ≤ ∥ R ℓ ( ξ ℓ − 1 ) − R ℓ ( ξ ℓ − 1 ) ∥ ∞ + ∥ R ℓ ( ξ ℓ − 1 ) − R ℓ ( ξ ℓ − 1 ) ∥ ∞ ≤ δ ℓ + L ℓ ⋅ E ℓ − 1 ( x ) .
Solving the recurrence yields E ℓ ( x ) ≤ ∑ j = 1 ℓ δ j ∏ t = j + 1 ℓ L t E_\ell(x)\leq\sum_{j=1}^{\ell}\delta_j\prod_{t=j+1}^{\ell}L_t E ℓ ( x ) ≤ ∑ j = 1 ℓ δ j ∏ t = j + 1 ℓ L t . By the choice of δ j \delta_j δ j , each summand satisfies
δ j ∏ t = j + 1 ℓ L t = ε L o u t ( L + 1 ) ⋅ ∏ t = j + 1 ℓ L t ∏ t = j + 1 L L t ≤ ε L o u t ( L + 1 ) , \delta_j\prod_{t=j+1}^{\ell}L_t=\frac{\varepsilon}{L_{\mathrm{out}}(L+1)}\cdot\frac{\prod_{t=j+1}^{\ell}L_t}{\prod_{t=j+1}^{L}L_t}\leq\frac{\varepsilon}{L_{\mathrm{out}}(L+1)}, δ j t = j + 1 ∏ ℓ L t = L out ( L + 1 ) ε ⋅ ∏ t = j + 1 L L t ∏ t = j + 1 ℓ L t ≤ L out ( L + 1 ) ε ,
so E ℓ ( x ) ≤ L ε / ( L o u t ( L + 1 ) ) ≤ ε / L o u t = η E_\ell(x)\leq L\varepsilon/(L_{\mathrm{out}}(L+1))\leq\varepsilon/L_{\mathrm{out}}=\eta E ℓ ( x ) ≤ L ε / ( L out ( L + 1 )) ≤ ε / L out = η uniformly. This shows in particular ξ ~ ℓ ( x ) ∈ K ℓ + \widetilde{\xi}_\ell(x)\in K_\ell^+ ξ ℓ ( x ) ∈ K ℓ + , validating the induction.
Step 5: final bound. Apply A o u t A_{\mathrm{out}} A out :
∥ F ~ ( x ) − F ( x ) ∥ ∞ = ∥ A o u t ( ξ ~ L ) − A o u t ( ξ L ) ∥ ∞ ≤ L o u t ⋅ E L ( x ) < ε \|\widetilde{F}(x)-F(x)\|_\infty=\|A_{\mathrm{out}}(\widetilde{\xi}_L)-A_{\mathrm{out}}(\xi_L)\|_\infty\leq L_{\mathrm{out}}\cdot E_L(x)<\varepsilon ∥ F ( x ) − F ( x ) ∥ ∞ = ∥ A out ( ξ L ) − A out ( ξ L ) ∥ ∞ ≤ L out ⋅ E L ( x ) < ε
uniformly on K K K .
Constructibility. The constants L ℓ L_\ell L ℓ and L o u t L_{\mathrm{out}} L out are computable from the affine parameters of F F F in linear time. Each δ ℓ \delta_\ell δ ℓ has log ( 1 / δ ℓ ) = poly ( ∣ F ∣ , log ( 1 / ε ) ) \log(1/\delta_\ell)=\operatorname{poly}(|F|,\log(1/\varepsilon)) log ( 1/ δ ℓ ) = poly ( ∣ F ∣ , log ( 1/ ε )) bits. By Step 2, each R ~ ℓ \widetilde{R}_\ell R ℓ is constructible in time poly ( ∣ F ∣ , log ( 1 / ε ) ) \operatorname{poly}(|F|,\log(1/\varepsilon)) poly ( ∣ F ∣ , log ( 1/ ε )) , and the composition is linear in L L L . □ \square □
:::
Robust hardness transfer
Theorem 45. (Robust hardness transfer ReLU → ρ \to\rho → ρ ). Fix d ≥ 1 d \ge1 d ≥ 1 and k ≥ d k \ge d k ≥ d , and let ρ \rho ρ satisfy hypotheses ( H 1 ) (H1) ( H 1 ) –( H 3 ) (H3) ( H 3 ) of Theorem 10 . If δ \delta δ -robust verification (resp. δ \delta δ -robust bounded-time reachability) is NP-hard for width-k k k ReLU-register networks in dimension d d d , then the corresponding problem is NP-hard for width-( k + 2 ) (k+2) ( k + 2 ) ρ \rho ρ -networks.
Proof. We give a polynomial-time many-one promise-preserving reduction. Given an instance ( N , Init , R , δ ) (N,\operatorname{Init},R,\delta) ( N , Init , R , δ ) of δ \delta δ -verification for a ReLU-register network N N N of width k k k , apply Lemma 44 on the compact K : = Init K := \operatorname{Init} K := Init with target precision ε : = δ / 4 \varepsilon:= \delta/4 ε := δ /4 to obtain a width-( k + 2 ) (k+2) ( k + 2 ) ρ \rho ρ -network N ~ \widetilde{N} N satisfying sup x ∈ K ∥ N ~ ( x ) − N ( x ) ∥ ∞ ≤ δ / 4 \sup_{x\in K}\lVert\widetilde{N}(x)-N(x)\rVert_{\infty} \le\delta/4 sup x ∈ K ∥ N ( x ) − N ( x ) ∥ ∞ ≤ δ /4 . Output the instance ( N ~ , Init , R + δ , δ / 4 ) (\widetilde{N},\operatorname{Init},R^{+\delta},\delta/4) ( N , Init , R + δ , δ /4 ) , where R + δ R^{+\delta} R + δ denotes the closed δ \delta δ -neighborhood of R R R .
YES preservation. If there exists x ∈ Init x \in\operatorname{Init} x ∈ Init with N ( x ) ∈ R + δ N(x) \in R^{+\delta} N ( x ) ∈ R + δ , then dist ( N ~ ( x ) , R ) ≤ dist ( N ( x ) , R ) + δ / 4 ≤ δ + δ / 4 \operatorname{dist}(\widetilde{N}(x),R) \le\operatorname{dist}(N(x),R)+\delta/4 \le\delta+\delta/4 dist ( N ( x ) , R ) ≤ dist ( N ( x ) , R ) + δ /4 ≤ δ + δ /4 , so N ~ ( x ) ∈ R + ( δ + δ / 4 ) ⊆ ( R + δ ) + δ / 4 \widetilde{N}(x) \in R^{+(\delta+\delta/4)} \subseteq(R^{+\delta})^{+\delta/4} N ( x ) ∈ R + ( δ + δ /4 ) ⊆ ( R + δ ) + δ /4 : the output is YES at the new promise gap δ / 4 \delta/4 δ /4 .
NO preservation. If dist ( N ( x ) , R ) > 2 δ \operatorname{dist}(N(x),R)>2\delta dist ( N ( x ) , R ) > 2 δ for all x ∈ Init x \in\operatorname{Init} x ∈ Init , then dist ( N ( x ) , R + δ ) > δ \operatorname{dist}(N(x),R^{+\delta})>\delta dist ( N ( x ) , R + δ ) > δ , hence dist ( N ~ ( x ) , R + δ ) ≥ dist ( N ( x ) , R + δ ) − δ / 4 > 3 δ / 4 = 2 ⋅ ( δ / 4 ) + δ / 4 > 2 ⋅ ( δ / 4 ) \operatorname{dist}(\widetilde{N}(x),R^{+\delta}) \ge\operatorname{dist}(N(x),R^{+\delta})-\delta/4>3\delta/4=2\cdot(\delta/4)+\delta/4>2\cdot(\delta/4) dist ( N ( x ) , R + δ ) ≥ dist ( N ( x ) , R + δ ) − δ /4 > 3 δ /4 = 2 ⋅ ( δ /4 ) + δ /4 > 2 ⋅ ( δ /4 ) , so the output is NO.
For bounded-time reachability with unary T T T , apply the same reduction with K = [ 0 , 1 ] d K=[0,1]^d K = [ 0 , 1 ] d and ε : = δ / ( 4 ⋅ S T ) \varepsilon:= \delta/(4\cdot S_T) ε := δ / ( 4 ⋅ S T ) where S T : = ∑ i = 0 T − 1 L i S_T := \sum_{i=0}^{T-1}L^i S T := ∑ i = 0 T − 1 L i and L L L is a Lipschitz constant of N N N on K K K ; the standard error-recurrence telescoping (cf. Step 4 of Lemma 44 ) controls the iterated error within δ / 4 \delta/4 δ /4 across T T T iterations.
The reduction is polynomial-time by the constructibility bound of Lemma 44 .
:::
Theorem 46. (NP-membership for robust verification of smooth networks). Fix d ≥ 1 d \ge1 d ≥ 1 , and let ρ \rho ρ satisfy hypotheses ( H 1 ) (H1) ( H 1 ) –( H 3 ) (H3) ( H 3 ) of Theorem 10 . Then δ \delta δ -robust verification (resp. robust bounded-time reachability with unary T T T ) for ρ \rho ρ -networks of dimension d d d belongs to NP.
Proof. A nondeterministic verifier guesses a rational x ∈ Init x \in\operatorname{Init} x ∈ Init with polynomially many bits (justified below) and evaluates y ~ : = N ( x ) \widetilde{y}:=N(x) y := N ( x ) to precision δ / 4 \delta/4 δ /4 using polynomial-time evaluation of ρ \rho ρ (by (H3)) and exact rational arithmetic for the affine layers.
Witness bit-complexity. By hypothesis (H3), ρ \rho ρ admits a polynomial-time-computable Lipschitz constant L ρ L_\rho L ρ on every bounded interval. Combined with the Lipschitz constants of the affine layers, N N N is Lipschitz with constant L N = poly ( input ) L_N=\operatorname{poly}(\text{input}) L N = poly ( input ) on K = Init K=\operatorname{Init} K = Init . By Lemma 43 applied at precision δ / 4 \delta/4 δ /4 , there is a ReLU-equivalent N R e L U N^{\mathrm{ReLU}} N ReLU with sup x ∈ K ∥ N ( x ) − N R e L U ( x ) ∥ ∞ ≤ δ / 4 \sup_{x\in K}\lVert N(x)-N^{\mathrm{ReLU}}(x)\rVert_{\infty}\le\delta/4 sup x ∈ K ∥ N ( x ) − N ReLU ( x ) ∥ ∞ ≤ δ /4 . Apply Lemma 36 to N R e L U N^{\mathrm{ReLU}} N ReLU : any feasible real witness x ∈ Init x \in\operatorname{Init} x ∈ Init for the ReLU instance can be replaced by a rational witness of bit complexity poly ( input ) \operatorname{poly}(\text{input}) poly ( input ) . The promise gap of δ \delta δ tolerates the cumulative error 2 ⋅ δ / 4 = δ / 2 2\cdot\delta/4=\delta/2 2 ⋅ δ /4 = δ /2 , ensuring that the rational witness preserves the YES/NO classification.
Verification. The verifier evaluates y ~ \widetilde{y} y to precision δ / 4 \delta/4 δ /4 . Under the δ \delta δ vs. 2 δ 2\delta 2 δ promise, dist ( y ~ , R ) ≤ δ + δ / 4 \operatorname{dist}(\widetilde{y},R)\le\delta+\delta/4 dist ( y , R ) ≤ δ + δ /4 in the YES case and dist ( y ~ , R ) ≥ 2 δ − δ / 4 > δ + δ / 4 \operatorname{dist}(\widetilde{y},R)\ge2\delta-\delta/4>\delta+\delta/4 dist ( y , R ) ≥ 2 δ − δ /4 > δ + δ /4 in the NO case, so the approximate output unambiguously certifies the correct case.
Conclusion. Combining Theorem 45 with NP-hardness of robust ReLU verification at width 4 (the unary-T T T case of Theorem 7, equivalently Corollary 14 ), and Theorem 46 for membership, yields Theorem 10 .
On binary T T T for ρ \rho ρ . The argument above relies on T T T unary so that the cumulative approximation error T ⋅ L ρ T ⋅ ε s t e p T\cdot L_\rho^T\cdot\varepsilon_{\mathrm{step}} T ⋅ L ρ T ⋅ ε step remains controllable in polynomial time. With T T T binary, the same calculation requires ε s t e p ≤ δ / ( 4 ⋅ 2 ∣ T ∣ ⋅ L ρ 2 ∣ T ∣ ) \varepsilon_{\mathrm{step}}\le\delta/(4\cdot2^{|T|}\cdot L_\rho^{2^{|T|}}) ε step ≤ δ / ( 4 ⋅ 2 ∣ T ∣ ⋅ L ρ 2 ∣ T ∣ ) , which has Ω ( L ρ 2 ∣ T ∣ ) \Omega(L_\rho^{2^{|T|}}) Ω ( L ρ 2 ∣ T ∣ ) bits of precision, doubly exponential in the input. Whether δ \delta δ -robust bounded-time reachability of ρ \rho ρ -networks at width 6 admits a NEXP-style hardness statement at binary T T T remains open.
Approximation hardness for ρ \rho ρ -networks. The approximation-hardness of Corollary 14 extends to ρ \rho ρ -networks at width 6 via the same reduction: under (H1)–(H3) there exists η > 0 \eta> 0 η > 0 such that approximating the worst-case output of a width-6 ρ \rho ρ -network within additive error η \eta η is NP-hard (unary T T T ). The argument is identical to the proof above, using that the Ω ( 1 ) \Omega(1) Ω ( 1 ) promise gap of Corollary 14 is preserved up to a constant by the ρ \rho ρ -emulation. Combined with Corollary 14 , this yields a unified intractability picture for ReLU and all common smooth activations at constant width.
Proof of Corollary 8
Corollary (Corollary 8, restated). Verification of feedforward width-4 ReLU networks on convex I n i t , A c c ⊆ [ 0 , 1 ] 4 \mathrm{Init}, \mathrm{Acc} \subseteq[0,1]^4 Init , Acc ⊆ [ 0 , 1 ] 4 is NP-complete.
Proof. NP-membership. Apply Lemma 36 with T = 1 T = 1 T = 1 (no iteration): a nondeterministic verifier guesses a rational x ∈ I n i t x \in\mathrm{Init} x ∈ Init of polynomial bit complexity, evaluates N ( x ) N(x) N ( x ) exactly, and checks N ( x ) ∈ A c c N(x) \in\mathrm{Acc} N ( x ) ∈ Acc .
NP-hardness. We reduce from Theorem 7(i). Given a T T T -bounded reachability instance ( N M , I n i t , A c c , T ) (N_M,\mathrm{Init},\mathrm{Acc},T) ( N M , Init , Acc , T ) with T T T in unary, where N M N_M N M and I n i t , A c c \mathrm{Init},\mathrm{Acc} Init , Acc are as constructed in Appendix § 12 .§ 3 , output the unrolled feedforward network N : = N M [ T ⋅ C M ] N := N_M^{[T \cdot C_M]} N := N M [ T ⋅ C M ] together with I n i t \mathrm{Init} Init and A c c \mathrm{Acc} Acc unchanged. The unrolled N N N has width 4, depth T ⋅ C M ⋅ D M = poly ( ∣ M ∣ , T ) T \cdot C_M \cdot D_M = \operatorname{poly}(|M|,T) T ⋅ C M ⋅ D M = poly ( ∣ M ∣ , T ) , and is polynomial-time constructible since T T T is unary.
It remains to verify the equivalence ∃ x ∈ I n i t : N ( x ) ∈ A c c ⟺ ∃ x ∈ I n i t , ∃ t ≤ T ⋅ C M : N M [ t ] ( x ) ∈ A c c \exists x \in\mathrm{Init}: N(x) \in\mathrm{Acc} \Longleftrightarrow\exists x \in\mathrm{Init}, \exists t \le T \cdot C_M: N_M^{[t]}(x) \in\mathrm{Acc} ∃ x ∈ Init : N ( x ) ∈ Acc ⟺ ∃ x ∈ Init , ∃ t ≤ T ⋅ C M : N M [ t ] ( x ) ∈ Acc . The reverse direction is immediate by absorption: in the construction of Appendix § 12 .§ 3 , A c c \mathrm{Acc} Acc corresponds to “state q F q_F q F reached and x 4 = 0 x_4 = 0 x 4 = 0 ”. Since q F q_F q F is the unique accepting (and thus terminal) state of M M M , once the trajectory enters A c c \mathrm{Acc} Acc , N M N_M N M acts as the identity on A c c \mathrm{Acc} Acc at every subsequent iteration, so N M [ T ⋅ C M ] ( x ) ∈ A c c N_M^{[T \cdot C_M]}(x) \in\mathrm{Acc} N M [ T ⋅ C M ] ( x ) ∈ Acc as well. The forward direction is trivial (take t = T ⋅ C M t = T \cdot C_M t = T ⋅ C M ). □
Statements for various activation functions
The hypotheses of Theorem 10 (ρ \rho ρ continuous, non-polynomial, polynomial-time computable, C 1 C^1 C 1 at some point with non-zero derivative) are mild and cover every smooth activation in modern use. The following table summarizes which standard activations satisfy the assumptions and inherit the consequent complexity statements at width 6.
Table 2. Coverage of Theorem 10 on standard activations.
For exact verification (without robustness), much stronger lower bounds hold for several of these activations. The following result of Wurm [2024, 2023b] shows that exact verification is R \mathbb{R} R -hard for a broad class of activations, including those permitting transcendental constraints.
Theorem 47 [43 , 42 ] . With identity nodes allowed:
Verification is R \mathbb{R} R -complete for any non-linear polynomial ρ \rho ρ , and R \mathbb{R} R -hard whenever ρ \rho ρ coincides with a non-linear polynomial on an interval.
Verification is ∃ R \exists\mathbb{R} ∃ R -hard for any activation ρ \rho ρ that allows pp-defining a function coinciding with the exponential on an interval (in particular, the exponential, ELU, e − ∣ x ∣ e^{-|x|} e − ∣ x ∣ , the Gaussian e − x 2 e^{-x^2} e − x 2 , arctan, and the Gallant–White cosine-smasher).
These results explain why we restrict our analysis to the robust variant: exact verification falls outside the standard polynomial hierarchy, while robust verification recovers NP-completeness (Theorem 10 ).
Neural ODEs at bounded dimension
Our results are stated for discrete iterated networks. In this section we transfer them to Neural ODEs [14 ] via the natural correspondence established by Duan et al. [ [15 ] , obtaining a Lipschitz piecewise-affine vector field of dimension 5 whose splitting-method-discretized flow simulates an arbitrary Turing machine. Verification hardness transfers automatically. The pure continuous-time question remains open with a precise technical obstruction.
The Duan et al. correspondence
Duan et al. [ [15 ] establish that vanilla feedforward networks, not only residual ones, are exact numerical discretizations of (non-autonomous) dynamical systems. Their Theorem 1 shows that for every flow map ϕ τ \phi^\tau ϕ τ of a Lipschitz ODE on a compact set, there exists a vanilla leaky-ReLU FNN of width d d d approximating it; the construction proceeds via splitting of an associated neural ODE. The mechanism implicit in their construction also yields the converse direction we need: every leaky-ReLU FNN of width exactly d d d with non-singular layers is the splitting-method iteration of an explicit non-autonomous piecewise-affine vector field. We state and use this converse direction below.
Lemma 48 (Splitting interpretation, after Duan et al. [ [15 ] ). Let σ α \sigma_\alpha σ α be the leaky-ReLU activation, α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and let N : R d → R d N:\mathbb{R}^d \to\mathbb{R}^d N : R d → R d be a vanilla feedforward leaky-ReLU network of depth L L L , with all hidden layers of width exactly d d d and non-singular weight matrices. Then there exists a Lipschitz piecewise-affine vector field v : R d × [ 0 , L ] → R d v:\mathbb{R}^d \times[0,L] \to\mathbb{R}^d v : R d × [ 0 , L ] → R d , piecewise constant in t t t on each unit interval [ k , k + 1 ) [k,k+1) [ k , k + 1 ) and computable in time poly ( size ( N ) ) \operatorname{poly}(\operatorname{size}(N)) poly ( size ( N )) from the parameters of N N N , such that N N N is exactly the time-L L L output of a Lie–Trotter splitting discretization of the non-autonomous ODE x ˙ = v ( x , t ) \dot{x}=v(x,t) x ˙ = v ( x , t ) at step size 1. In particular, N ( x 0 ) N(x_0) N ( x 0 ) equals the L L L -th iterate of the splitting scheme started at x 0 x_0 x 0 .
Proof. For each layer ℓ ∈ { 1 , … , L } \ell\in\{1,\ldots,L\} ℓ ∈ { 1 , … , L } , the layer x ↦ σ α ( W ℓ x + b ℓ ) x \mapsto\sigma_\alpha(W_\ell x+b_\ell) x ↦ σ α ( W ℓ x + b ℓ ) is the Lie–Trotter composition (Trotter [ [39 ] , see e.g. Holden et al. [ [21 ] ) of the time-1 flow of an affine ODE x ˙ = ( W ℓ − I ) x + b ℓ \dot{x}=(W_\ell-I)x+b_\ell x ˙ = ( W ℓ − I ) x + b ℓ (whose flow at t = 1 t=1 t = 1 realizes x ↦ W ℓ x + b ℓ x \mapsto W_\ell x+b_\ell x ↦ W ℓ x + b ℓ when W ℓ W_\ell W ℓ is non-singular, after re-parameterization; see Duan et al. [ [15 ] Section 3.5–3.6) and the time-1 flow of the activation ODE x ˙ = ( σ α − I ) ( x ) \dot{x}=(\sigma_\alpha-I)(x) x ˙ = ( σ α − I ) ( x ) rescaled appropriately. Specifically, x ˙ = v ( x , t ) \dot{x}=v(x,t) x ˙ = v ( x , t ) for t ∈ [ ℓ − 1 , ℓ ) t \in[\ell-1,\ell) t ∈ [ ℓ − 1 , ℓ ) , where v v v encodes both ingredients of layer ℓ \ell ℓ , gives the required non-autonomous vector field. Composing L L L unit splitting steps reproduces exactly N N N . □
From ReLU to leaky-ReLU at width +1. Lemma 48 requires leaky-ReLU rather than ReLU. The two activations are related by the elementary identity ReLU ( x ) = σ α ( x ) − α x 1 − α \operatorname{ReLU}(x)=\frac{\sigma_\alpha(x)-\alpha x}{1-\alpha} ReLU ( x ) = 1 − α σ α ( x ) − α x , which expresses ReLU as a linear combination of one leaky-ReLU neuron and one identity register. By keeping x x x alongside σ α ( x ) \sigma_\alpha(x) σ α ( x ) in a single extra register, every ReLU neuron at width w w w can be emulated by a leaky-ReLU subnetwork at width w + 1 w+1 w + 1 , with the same depth modulo a constant. We record this as a folklore lemma.
Lemma 49 (ReLU → \to → leaky-ReLU emulation at width +1). For every fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and every ReLU network N ∈ N n , n , w R e L U N \in\mathcal{N}^{\mathrm{ReLU}}_{n,n,w} N ∈ N n , n , w ReLU , there exists a leaky-ReLU network N ~ ∈ N n , n , w + 1 σ α \widetilde{N} \in\mathcal{N}^{\sigma_\alpha}_{n,n,w+1} N ∈ N n , n , w + 1 σ α with the same depth up to a constant factor, such that N ~ ( x ) = N ( x ) \widetilde{N}(x)=N(x) N ( x ) = N ( x ) for all x ∈ R n x \in\mathbb{R}^n x ∈ R n .
Proof. For each ReLU neuron y = ReLU ( z ) y=\operatorname{ReLU}(z) y = ReLU ( z ) in N N N , the identity ReLU ( z ) = σ α ( z ) − α z 1 − α \operatorname{ReLU}(z)=\frac{\sigma_\alpha(z)-\alpha z}{1-\alpha} ReLU ( z ) = 1 − α σ α ( z ) − α z allows us to compute y y y as a linear combination of σ α ( z ) \sigma_\alpha(z) σ α ( z ) and z z z . Implementing this in a vanilla leaky-ReLU FNN requires keeping z z z alongside σ α ( z ) \sigma_\alpha(z) σ α ( z ) between layers; one extra register suffices for this passthrough, where the identity wire is itself realized by a single leaky-ReLU neuron via Proposition 40. The depth increases by a constant per layer. □
Neural ODE universality at dimension 5
Combining Theorem 3 (width-4 ReLU universality) with Lemma 49 (ReLU → \to → leaky-ReLU at width 5) and Lemma 48 (leaky-ReLU width d ↔ d \leftrightarrow d ↔ non-autonomous ODE in dimension d d d ) yields the following.
Theorem 50 (Discretized Neural ODE consequence at dimension 5). For every length bound n ≥ 1 n \ge1 n ≥ 1 , there exists a polynomial-time constructible non-autonomous Lipschitz piecewise-affine vector field f n : R 5 × [ 0 , + ∞ ) → R 5 f_n : \mathbb{R}^{5} \times[0,+\infty) \to\mathbb{R}^{5} f n : R 5 × [ 0 , + ∞ ) → R 5 , piecewise constant in t t t on each unit interval and realizable layer-by-layer as a leaky-ReLU vanilla neural network of width 5, and a fixed convex acceptance region R a c c O D E ⊆ [ 0 , 1 ] 5 R_{\mathrm{acc}}^{\mathrm{ODE}} \subseteq[0,1]^{5} R acc ODE ⊆ [ 0 , 1 ] 5 specified by rational linear inequalities, such that the following holds. For every deterministic Turing machine M M M over { 0 , 1 } \{0,1\} { 0 , 1 } and every input w ∈ { 0 , 1 } ∗ w \in\{0,1\}^{*} w ∈ { 0 , 1 } ∗ with ∣ w ∣ ≤ n |w| \le n ∣ w ∣ ≤ n , there is a polynomial-time-computable initial condition ξ 0 ( M , w ) ∈ [ 0 , 1 ] 5 \xi_0(M,w) \in[0,1]^{5} ξ 0 ( M , w ) ∈ [ 0 , 1 ] 5 and an integer step count L M = poly ( ∣ M ∣ ) L_M = \operatorname{poly}(|M|) L M = poly ( ∣ M ∣ ) such that the Lie-Trotter splitting discretization sequence { ξ k } k ≥ 0 \{\xi_k\}_{k\ge0} { ξ k } k ≥ 0 of ξ ˙ = f n ( ξ , t ) \dot{\xi}=f_n(\xi,t) ξ ˙ = f n ( ξ , t ) at step size 1, started at ξ 0 ( M , w ) \xi_0(M,w) ξ 0 ( M , w ) , satisfies: M M M accepts w ⟺ ∃ k ≥ 0 , ξ k ⋅ L M ∈ R a c c O D E w \Longleftrightarrow\exists k \ge0,\ \xi_{k\cdot L_M} \in R_{\mathrm{acc}}^{\mathrm{ODE}} w ⟺ ∃ k ≥ 0 , ξ k ⋅ L M ∈ R acc ODE . Taking M M M to be a fixed universal Turing machine U U U , f n f_n f n becomes a single non-autonomous vector field parameterized by length only, so the discretized flow simulates any M M M on any input of length ≤ n \le n ≤ n .
Caveat on continuous flow. The discretization sequence { ξ k } \{\xi_k\} { ξ k } is what reproduces the network iteration; it is not in general equal to the continuous flow ξ : [ 0 , + ∞ ) → R 5 \xi: [0,+\infty) \to\mathbb{R}^{5} ξ : [ 0 , + ∞ ) → R 5 of ξ ˙ = f n ( ξ , t ) \dot{\xi}=f_n(\xi,t) ξ ˙ = f n ( ξ , t ) sampled at integer times. Splitting methods are only first-order accurate in the step size, and for step size 1 the gap is real. The continuous flow exists and is unique by Lipschitz of f n f_n f n , but its values at integer times need not encode TM configurations. Furthermore, the vector field is non-autonomous (piecewise constant in t t t , with one piece per unit step); whether the construction can be carried out with an autonomous vector field is left open. See Appendix § 15 .§ 4 for related open questions.
Proof. By Theorem 3, the width-4 ReLU network N N N simulates a universal Turing machine on convex inputs [ 0 , 1 ] 4 [0,1]^4 [ 0 , 1 ] 4 . By Lemma 49 , an associated width-5 leaky-ReLU network N ~ : [ 0 , 1 ] 5 → [ 0 , 1 ] 5 \widetilde{N} : [0,1]^5 \to[0,1]^5 N : [ 0 , 1 ] 5 → [ 0 , 1 ] 5 realizes the same iteration on the embedded set { ( x , 0 ) : x ∈ [ 0 , 1 ] 4 } ⊆ [ 0 , 1 ] 5 \{(x,0):x \in[0,1]^4\} \subseteq[0,1]^5 {( x , 0 ) : x ∈ [ 0 , 1 ] 4 } ⊆ [ 0 , 1 ] 5 . By Lemma 48 applied to N ~ \widetilde{N} N , there is a non-autonomous Lipschitz piecewise-affine vector field f n : R 5 × [ 0 , + ∞ ) → R 5 f_n : \mathbb{R}^{5} \times[0,+\infty) \to\mathbb{R}^{5} f n : R 5 × [ 0 , + ∞ ) → R 5 , piecewise constant in t t t on unit intervals, whose Lie-Trotter splitting discretization at step 1 over L M = poly ( ∣ M ∣ ) L_M=\operatorname{poly}(|M|) L M = poly ( ∣ M ∣ ) time intervals reproduces N ~ \widetilde{N} N . Since R a c c O D E = Acc × { 0 } R_{\mathrm{acc}}^{\mathrm{ODE}}=\operatorname{Acc}\times\{0\} R acc ODE = Acc × { 0 } (with Acc \operatorname{Acc} Acc from the verification recipe of Section 4.1) closes the equivalence. □
Reading. Width 4 in the discrete network and dimension 5 in the Neural ODE are the same quantity up to the leaky-ReLU emulation overhead. The “+1” is the cost of moving from ReLU to leaky-ReLU, the splittable activation required by the Duan correspondence. The question of whether Theorem 3 can be carried out directly with leaky-ReLU at width 4 (which would yield a dimension-4 Neural ODE), or whether the non-autonomous vector field can be made autonomous, is left open.
Verification hardness transfers
The verification spectrum of Theorem 7 transfers to Neural ODEs by Theorem 50.
Corollary 51 (Verification spectrum for Neural ODEs at dimension 5). For Lipschitz piecewise-affine Neural ODEs ξ ˙ = f ( ξ , t ) \dot{\xi}=f(\xi,t) ξ ˙ = f ( ξ , t ) in dimension 5, with convex initial and acceptance regions R i n i t O D E , R a c c O D E ⊆ [ 0 , 1 ] 5 R_{\mathrm{init}}^{\mathrm{ODE}}, R_{\mathrm{acc}}^{\mathrm{ODE}} \subseteq[0,1]^5 R init ODE , R acc ODE ⊆ [ 0 , 1 ] 5 , the discretized reachability problem “does the splitting-discretized trajectory enter R a c c O D E R_{\mathrm{acc}}^{\mathrm{ODE}} R acc ODE within T T T discretization steps?” is NP-complete with T T T unary, NEXP-complete with T T T binary, and RE-complete (undecidable) without a time bound.
An analogous transfer of Theorem 10 (smooth ρ \rho ρ at width 6) to Neural ODEs requires extending the correspondence [15 ] from leaky-ReLU to other activations. The Duan et al. argument is stated for leaky-ReLU and relies specifically on its invertibility; we leave the extension to tanh, GELU, sigmoid, Swish, and other smooth activations as an open direction.
Practical reading. A practitioner verifying a low-dimensional Neural ODE faces the full hardness spectrum already at dimension 5. The empirical observation that complete verifiers degrade rapidly with integration time [23 , 40 ] is, on this account, an intrinsic complexity-theoretic phenomenon and not a solver artifact: integration time plays the role of Turing-machine time, and the hardness ladder is unconditional on solver design.
Open: pure continuous-time exact simulation
Theorem 50 establishes universality of Neural ODEs under splitting-method discretization . The discretized flow at integer times reproduces TM steps exactly. The continuous flow at non-integer times is well-defined (by Lipschitz of f f f ) but need not encode any meaningful TM configuration.
A natural strengthening would be: a Lipschitz piecewise-affine f : R d → R d f : \mathbb{R}^{d} \to\mathbb{R}^{d} f : R d → R d whose continuous flow satisfies ξ ( n ) = N [ n ] ( ξ 0 ) \xi(n) = N^{[n]}(\xi_{0}) ξ ( n ) = N [ n ] ( ξ 0 ) for every integer n n n , for N N N a non-trivial non-linear PA map. Whether this is achievable is open, and we record two related questions.
Three known regimes. For the broader question of continuous-time TM simulation, three regimes are established in the literature:
Polynomial (rather than piecewise-affine) vector fields [10 ] (analytic flow, but no longer in the Neural-ODE class as commonly used).
Piecewise-constant discontinuous fields, e.g. PCD systems [4 , 26 ] (closed-form jumps at cell boundaries, but not Lipschitz).
Splitting-method discretization (Theorem 50): exact simulation at discretization times, with continuous interpolation between them.
The Lipschitz piecewise-affine class, the class most aligned with practical Neural ODEs, is not covered by any of these.
Two open questions. We highlight two natural open questions for future work, in increasing order of strength:
(Robust continuous-time) Does there exist an autonomous Lipschitz piecewise-affine vector field f : R d → R d f : \mathbb{R}^{d} \to\mathbb{R}^{d} f : R d → R d (for some constant d d d ) such that the continuous flow simulates a universal Turing machine in the following robust sense: for every machine M M M and input w w w , the trajectory enters an ε \varepsilon ε -neighborhood of a designated accepting region in finite time iff M M M accepts w w w ?
(Exact continuous-time) Does there exist such an f f f with ξ ( n ) = N [ n ] ( ξ 0 ) \xi(n) = N^{[n]}(\xi_{0}) ξ ( n ) = N [ n ] ( ξ 0 ) exactly at integer times, for some non-trivial PA map N N N derived from M M M ?
We leave both questions for future work.