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

Identifying the minimum number of neurons required to achieve a specified accuracy in neural networks is a significant challenge. This paper explores the complexity of designing feedforward neural networks with ReLU activation functions and demonstrates that it is NP-hard to determine the minimum number of neurons needed to approximate an $L^{p}$ function with a two-hidden-layer ReLU network. A polynomial-time reduction from the Geometric Set Cover Problem is used to prove the NP-hardness of the ReLU network structure minimization. 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.