The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911361649344512 |
|---|---|
| author | Stargalla, Moritz Hertrich, Christoph Reichman, Daniel |
| author_facet | Stargalla, Moritz Hertrich, Christoph Reichman, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Computational Complexity of Counting Linear Regions in ReLU Neural Networks Stargalla, Moritz Hertrich, Christoph Reichman, Daniel Computational Complexity Discrete Mathematics Machine Learning Neural and Evolutionary Computing Combinatorics 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. |
| title | The Computational Complexity of Counting Linear Regions in ReLU Neural Networks |
| topic | Computational Complexity Discrete Mathematics Machine Learning Neural and Evolutionary Computing Combinatorics |
| url | https://arxiv.org/abs/2505.16716 |