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

arXiv:2610.11313v1 Announce Type: new Abstract: 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 L^p(R^d,R^m) approximation constraint. For every fixed d ge 1, m ge 1, and 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+2. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the L^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.

Source: arXiv cs.LG | 2026-10-09