cs.LGNov 2, 2026

Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification

Authors: Olivier Bournez, Johanne Cohen, Adrian Wurm

Organizations: Institut Polytechnique de Paris, LIX 91128 Palaiseau, France · LISN, CNRS, Université Paris-Saclay 91190 Gif-sur-Yvette, France · Computer Science Institute BTU Cottbus-Senftenberg D-03046 Cottbus, Germany

Abstract

We study the iterates of a fixed ReLU network NN of width 4, that is, the discrete-time system xk+1=N(xk)x_{k+1} = N(x_k) on [0,1]4[0,1]^4. Equivalently, xkx_k is the output of a weight-tied network made of kk copies of NN, or of a recurrent network with no external input, started at x0x_0. We prove that every deterministic Turing machine MM admits such a network NMN_M. The network can be constructed in polynomial time from MM. Each iteration has depth poly(∣M∣)\mathrm{poly}(|M|). The iterates of NMN_M simulate MM exactly on every encoded tape. The number of iterations is proportional to the running time of MM. Moreover, the fourth coordinate irreversibly flags every point of the convex cube [0,1]4[0,1]^4 whose simulation reads an invalid digit. This flag is the certificate that makes hardness reductions sound on convex input regions, the regime of practical verifiers. Convex regions were previously inaccessible because of a continuity obstruction inherent to ReLU networks. The correspondence has three consequences. First, reachability for iterated width-4 ReLU networks spans the full complexity hierarchy along the single axis of the time bound: it is NP-complete for a unary bound, NEXP-complete for a binary bound and RE-complete (undecidable) with no bound. Second, two extra neurons of width suffice to extend the hardness to every common smooth activation: at width 6, the robust verification problem (a promise problem with δ/2δδ/2δ gap) is NP-complete for tanh⁡\tanh, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant. Third, the whole spectrum transfers to discretized Neural ODEs in dimension 5.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 26, 2025

Parameterized Hardness of Zonotope Containment and Neural Network Verification

Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posed by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, we prove that, for all ℓ≥2\ell\ge 2, deciding positivity (and thus surjectivity) of a function f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} computed by an ℓ\ell-layer ReLU network is W[ℓ−1\ell-1]-hard when parameterized by the input dimension dd. The case ℓ=2\ell=2 implies that zonotope non-containment (a problem that is of independent interest in computational geometry, control theory, and robotics) is W[1]-hard with respect to the ambient dimension dd. Moreover, we show that approximating the maximum within any multiplicative factor and computing the LpL_p-Lipschitz constant for p∈(0,∞]p\in(0,\infty] in ℓ\ell-layer networks is NP-hard and W[ℓ−1\ell-1]-hard with respect to dd. For ℓ≥3\ell\ge 3, approximating the LpL_p-Lipschitz constant is NP- and W[ℓ−2\ell-2]-hard. We further show that the above problems are NP- and W[tt]-hard (for all t≥1t\ge 1) with respect to ℓ\ell for constant dd. Notably, our hardness results imply that the naive enumeration-based methods for these fundamental problems running in n(ℓ−1)d⋅poly⁡(N)n^{(\ell-1) d}\cdot\operatorname{poly}(N) time are all essentially optimal under the Exponential Time Hypothesis.
Jul 15, 2026

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to [−2,2][-2,2], and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption NP⊈BPP\mathrm{NP}\not\subseteq\mathrm{BPP}, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level σ⋆=2−11σ_\star=2^{-11} for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in [−1,1][-1,1]. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula ΦΦ with mm clauses, a four-ReLU-per-clause construction satisfies max⁡x∈[0,1]ngΦ(x)=(m−unsat⁡(Φ))/3\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in mm survives the aggregate perturbation of all coefficients with probability at least 1−e−m/81-e^{-m/8}. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.
Oct 28, 2026

A Witnessing Duality for ReLU Network Depth

A depth lower bound for ReLU networks asserts that every sufficiently shallow network fails on some input. What does a proof of such a bound compute? We study this question for exact computation of the maximum of nn real inputs, with depth measured by the number of hidden layers. For every separately fixed prime qq and depth bound KK, we give a uniform TC0\mathsf{TC}^0 refuter for rational networks with at most KK hidden layers and more than qKq^K inputs, provided that the reduced denominators of their nonbias weights are not divisible by qq. Biases may be arbitrary rationals. The refuter finds a rational input on which the network fails, and its correctness is provable in VTC0\mathbf{VTC}^0, the bounded-arithmetic theory of uniform constant-depth threshold computation. The underlying numerical depth lower bound follows from Averkov, Hojny and Merkert (ICLR 2025), extending Haase, Hertrich and Loho (ICLR 2023); our contribution is an internal proof that makes its geometric argument into a feasible refuter. On the construction side, VTC0\mathbf{VTC}^0 verifies locally checkable certificates for the balanced integer-weight maximum network of depth ⌈log⁡2n⌉\lceil\log_2 n\rceil. At q=2q=2, the construction and refuter meet: for each fixed KK, the theory verifies that integer-nonbias-weight networks with arbitrary rational biases can compute the maximum with at most KK hidden layers exactly when n≤2Kn\le 2^K. We also give certified rational constructions of polynomial encoding length and depth O(log⁡n/log⁡log⁡n)O(\log n/\log\log n). These results instantiate a witnessing duality: bounded proofs of certified existence and of refutation correspond, respectively, to threshold-computable constructors and refuters whose guarantees the theory proves.