Reachability Is NP-Complete Even for the Simplest Neural Networks

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.

References in corpus (4)

• A Survey on Deep Learning in Medical Image Analysis
• A Survey of the Recent Architectures of Deep Convolutional Neural Networks
• A Survey of Deep Learning Techniques for Autonomous Driving
• A Unified View of Piecewise Linear Neural Network Verification