The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Moritz Stargalla; Christoph Hertrich; Daniel Reichman

cs.CCMay 22, 2025

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Authors: Moritz Stargalla, Christoph Hertrich, Daniel Reichman

Organizations: University of Technology Nuremberg · Worcester Polytechnic Institute

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.

Figures & tables

Paper	Definitions
Montúfar et al. [31] (2014)	5
Pascanu et al. [33] (2014)	4
Raghu et al. [36] (2017)	1 , 5 (*)
Arora et al. [1] (2018)	5
Serra et al. [39] (2018)	1 , 2 (*)
Hanin and Rolnick [17] (2019)	2 , 4

Table 1: List of papers that use one or several definitions. Additional notes on the papers marked with an asterisk can be found in the footnote 3 3 3 Raghu et al. [36] do not use Definition 1 explicitly, but they define activation patterns and derive a bound on the total number of activation patterns, which is equivalent to bounding the number of activation regions. The bound of Serra et al. [39] holds for Definition 2 , compare the discussion in [ 7 , Section 5] . The mixed-integer program counts the number of activation regions ( Definition 1 ). Rolnick and Kording [37] only treat cases where Definitions 2 and 5 are equivalent. Tseran and Montúfar [41] consider activation regions of maxout networks, which is conceptually slightly different from the activation regions defined in this paper. Huchette et al. [20] actually define activation regions using Definition 1 , but then later state that they disregard low dimensional linear regions. Therefore, their definition is equivalent to Definition 2 . Zanotti [48] defines linear regions as the closure of open connected regions. Lezeau et al. [27] define linear regions as closures of open connected regions. .

Figure 1: A ReLU network (left) computing the function

f(x,y)=\max(-y,\min(0,-x))

(right). The closed connected regions (center left) and the activation regions (center right) are displayed. The slice

\{(x,0):x\geq 0\}

is contained in the two closed connected regions with functions

0

(red) and

-y

(blue). We have

R_{6}=R_{5}=R_{4}=3

R_{3}=4

R_{2}=5

and

R_{1}=7

. In anti-clockwise direction starting from the region with value 0, the activation patterns are

010110

000000

001001

101001

100000

110010

and

110110

(neurons are ordered from the upper left to the lower right).

Figure 2: A ReLU network

N

computing

\min(y,\max(-1,-x),\max(3-2x,-x))

(this function was first considered by Zanotti [47, Figure 1] ). An activation region of

N

is either a blue line, blue point, or a full dimensional cell as defined by the blue lines. There are four closed connected regions as indicated by the colors. The line between the points

(1,-1)

and

(3,-3)

belongs to the green as well as the orange region. In particular, the orange closed connected region is not the closure of a union of activation regions.

Figure 3: The function

\max(0,x)+\max(0,-y)-\max(0,x-y)+\min(\max(0,x-2),\max(0,y-2))-2\min(\max(0,x-1),\max(0,y-1))

. We have

R_{6}=7

R_{5}=8

, and

R_{4}=9

Figure 4: The function

T_{1}

(left),

T_{2}

(center) and its linear regions (right).

Figure 5: The functions

g_{\phi}(x)=1-\max(0,x_{1})-\max(0,1-x_{1}-x_{2})

(left),

h_{\phi,\varepsilon}(x)=\max(0,\varepsilon-1+g_{\phi}(x))

(center left), and

f_{N_{\phi}}(x)=\max(0,T_{2}(x)+\varepsilon-1+g_{\phi}(x))

(right) for the

\mathsf{SAT}

formula

\phi(x)=(\neg x_{1})\land(x_{1}\lor x_{2})

with the satisfying assignment

(0,1)

and

\varepsilon=0.4

. The function

f_{N_{\phi}}

is only nonzero in the gray region, which is contained in the

\varepsilon

-square (orange) around the only satisfying point of

\phi

(black).

Figure 6:

T_{1,\delta}

(left),

T_{2,\delta}

and its linear regions (center) for

\delta=0.2

, and

C_{I}^{0},C_{I}^{1}

for all

I\subseteq[2]

(right).

ReLU Neural Networks

Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.

See all 111 papers

NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
Oct 8, 2026Sangrock LeeReLU Neural Networks Neural Network Approximation Theory
FAMU–FSU College of Engineering, Florida State University, Tallahassee, FL, 32310
Characterizing the Discrete Geometry of ReLU Networks
Jun 5, 2026Blake B. Gaines, Jinbo BiNeural Representation Geometry ReLU Neural Networks
Department of Computer Science University of Connecticut
Shallower ReLU Network Representations via Exact Linear Algebra
Jul 22, 2026Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7Shallow Neural Networks ReLU Neural Networks
University of Technology Nuremberg · Brandenburg University of Technology Cottbus–Senftenberg · University of Copenhagen +3

Oct 8, 2026J/K move · Enter open · S save

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

Sangrock Lee

FAMU–FSU College of Engineering, Florida State University, Tallahassee, FL, 32310

ReLU Neural Networks Neural Network Approximation Theory Neural Network Compression

Open paper AskPDF arXiv

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(\mathbb{R}^d,\mathbb{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.

Abstract

ReLU Neural Networks

Explore similar work

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

Characterizing the Discrete Geometry of ReLU Networks

Shallower ReLU Network Representations via Exact Linear Algebra