Reachability Is NP-Complete Even for the Simplest Neural Networks
This work is incremental, as it refines and extends previous NP-completeness results for neural network reachability, impacting theoretical computer science and AI safety by clarifying computational limits.
The paper addresses the computational complexity of the reachability problem in neural networks, showing that it is NP-complete even for simple networks with one layer and minimal parameter requirements, correcting flaws in prior proofs.
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.