Reachability is NP-complete Even For the Simplest Neural Networks
Published in International Conference on Reachability Problems 2021 (RP21), 2021
Recommended citation: https://link.springer.com/chapter/10.1007/978-3-030-89716-1_10
We investigate the complexity of the reachability problem for (deep) neural networks: does it compute valid output given some valid input? It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We repair some flaws in the original upper and lower bound proofs. We then show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer, as well as neural networks with minimal requirements on the occurring parameters.’