# Reachability Is NP-Complete Even for the Simplest Neural Networks

arXiv: https://arxiv.org/abs/2108.13179 · HTML: https://mlsanity.com/paper/2108.13179/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 15 references that are in the map.
- First posted on arXiv 30 Aug 2021.

## Builds on (most cited first, 8 of 8)

- [A Survey on Deep Learning in Medical Image Analysis](https://mlsanity.com/paper/1702.05747/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [A Survey of Deep Learning Techniques for Autonomous Driving](https://mlsanity.com/paper/1910.07738/) (2019)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [A Survey of the Recent Architectures of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1901.06032/) (2019)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Verifying Properties of Binarized Deep Neural Networks](https://mlsanity.com/paper/1709.06662/) (2017)
- [Classification-based Financial Markets Prediction using Deep Neural Networks](https://mlsanity.com/paper/1603.08604/) (2016)

## Built on by (most cited first, 27 of 27)

- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Neural Network Verification is a Programming Language Challenge](https://mlsanity.com/paper/2501.05867/) (2025)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Fundamental Limits in Formal Verification of Message-Passing Neural Networks](https://mlsanity.com/paper/2206.05070/) (2022)
- [Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networks](https://mlsanity.com/paper/2208.09872/) (2022)
- [Revisiting the Adversarial Robustness-Accuracy Tradeoff in Robot Learning](https://mlsanity.com/paper/2204.07373/) (2022)
- [Provably Safe Neural Network Controllers via Differential Dynamic Logic](https://mlsanity.com/paper/2402.10998/) (2024)
- [A Certified Proof Checker for Deep Neural Network Verification in Imandra](https://mlsanity.com/paper/2405.10611/) (2024)
- [Reachability In Simple Neural Networks](https://mlsanity.com/paper/2203.07941/) (2022)
- [Learning Provably Stabilizing Neural Controllers for Discrete-Time Stochastic Systems](https://mlsanity.com/paper/2210.05304/) (2022)
- [OccRob: Efficient SMT-Based Occlusion Robustness Verification of Deep Neural Networks](https://mlsanity.com/paper/2301.11912/) (2023)
- [Abstraction-Based Proof Production in Formal Verification of Neural Networks](https://mlsanity.com/paper/2506.09455/) (2025)
- [Revisiting Differential Verification: Equivalence Verification with Confidence](https://mlsanity.com/paper/2410.20207/) (2024)
- [Proof Minimization in Neural Network Verification](https://mlsanity.com/paper/2511.08198/) (2025)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Verifying And Interpreting Neural Networks using Finite Automata](https://mlsanity.com/paper/2211.01022/) (2022)
- [Verifying Quantized Graph Neural Networks is PSPACE-complete](https://mlsanity.com/paper/2502.16244/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [Random Parameter Noise Does Not Make Exact ReLU Verification Easy](https://mlsanity.com/paper/2607.14375/) (2026)
- [STR-Cert: Robustness Certification for Deep Text Recognition on Deep Learning Pipelines and Vision Transformers](https://mlsanity.com/paper/2401.05338/) (2023)
- [Robustness Verifcation in Neural Networks](https://mlsanity.com/paper/2403.13441/) (2024)
- [Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation](https://mlsanity.com/paper/2405.08645/) (2024)
- [Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing](https://mlsanity.com/paper/2510.18591/) (2025)
- [The Complexity of Verifying Feedforward Neural Networks in Quantised Settings](https://mlsanity.com/paper/2605.29537/) (2026)
- [Rethinking Evaluation Paradigms in IBP-based Certified Training](https://mlsanity.com/paper/2606.02134/) (2026)
- [Security Properties of Neural Networks as Decision Problems](https://mlsanity.com/paper/2609.39768/) (2026)

## Abstract (arXiv)

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.