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

CardsList
  1. Parameterized Hardness of Zonotope Containment and Neural Network Verification

    Sep 26, 2025Vincent Froese, Moritz Grillo, Christoph Hertrich +1Neural Network VerificationParameterized Complexity

  2. Random Parameter Noise Does Not Make Exact ReLU Verification Easy

    Jul 15, 2026Mojtaba SoltanalianNeural Network VerificationReLU Neural Networks

  3. A Witnessing Duality for ReLU Network Depth

    Oct 28, 2026Dimitrios MyrisiotisReLU Neural NetworksCircuit Complexity