cs.CCNov 2, 2026

The Complexity of ReLU Network Synthesis from a Parameter Multiset

Authors: Dimitrios Myrisiotis

Organizations: GREAT BAY UNIVERSITY, CHINA

Abstract

We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, and a bound on the number of neurons (output included). The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture. Matching two labeled examples exactly is already NP\mathsf{NP}-complete, so we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is Σ2PΣ_2^{\mathsf P}-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in DP\mathsf{DP} for every fixed neuron bound and is DP\mathsf{DP}-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is Σ2PΣ_2^{\mathsf P}-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is NPPP\mathsf{NP}^{\mathsf{PP}}-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess.

Figures & tables

Explore similar work

Oct 8, 2026

NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks

A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an Lp(Rd,Rm)L^p(\mathbb{R}^d,\mathbb{R}^m) approximation constraint. For every fixed d≥1d \ge 1, m≥1m \ge 1, and 1≤p<∞1 \le p < \infty, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least d+2d+2. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the LpL^p-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.
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.
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.