The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
The paper investigates counting linear regions in ReLU neural networks using six different mathematical definitions of a linear region. It proves that counting is generally intractable, showing NP-hardness for many definitions and demonstrating that it can be done in polynomial space for some definitions. The findings highlight the computational difficulty of determining the network's structure.