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

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

    Oct 8, 2026Sangrock LeeReLU Neural NetworksNeural Network Approximation Theory

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

    Jul 15, 2026Mojtaba SoltanalianNeural Network VerificationReLU Neural Networks

  3. Parameterized Hardness of Zonotope Containment and Neural Network Verification

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