The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

2025/05/22 by Moritz Stargalla, Christoph Hertrich, Stargalla, Moritz +3 · 1 citation
Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Neural Networks and Applications #Neural and Evolutionary Computing (cs.NE) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2505.16716

openalex publication_date 2025/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.

Citations

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ²
• Bounds on the Number of Pieces in Continuous Piecewise Affine Functions
• Decomposition Polyhedra of Piecewise Linear Functions
• Tropical Expressivity of Neural Networks
• When Deep Learning Meets Polyhedral Theory: A Survey
• Training Neural Networks is NP-Hard in Fixed Dimension
• Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions
• Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks
• On the Number of Regions of Piecewise Linear Neural Networks
• Training Fully Connected Neural Networks is ∃ℝ-Complete
• On the Expected Complexity of Maxout Networks
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Tight Hardness Results for Training Depth-2 ReLU Networks
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Reverse-Engineering Deep ReLU Networks
• Lipschitz regularity of deep neural networks: analysis and efficient estimation
• Bounding and Counting Linear Regions of Deep Neural Networks
• Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks
• On the Expressive Power of Deep Neural Networks
• On the Number of Linear Regions of Deep Neural Networks

Cited by

• Parameterized Hardness of Zonotope Containment and Neural Network Verification

Related

• Complexity of Linear Regions in Deep Networks
• Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations
• Bounding and Counting Linear Regions of Deep Neural Networks
• On the Number of Linear Regions of Convolutional Neural Networks
• The Evolution of the Interplay Between Input Distributions and Linear Regions in Networks