Reachability Is NP-Complete Even for the Simplest Neural Networks
Marco Sälzer, Martin Lange
Abstract
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.
Topics & Concepts
ReachabilityArtificial neural networkMathematical proofSimple (philosophy)Upper and lower boundsComputer scienceReachability problemDeep neural networksTheoretical computer scienceMathematicsArtificial intelligenceGeometryMathematical analysisEpistemologyPhilosophyAdversarial Robustness in Machine LearningAdvanced Neural Network ApplicationsMachine Learning and Algorithms