# Reachability In Simple Neural Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 15 Mar 2022.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [Reachability Is NP-Complete Even for the Simplest Neural Networks](https://mlsanity.com/paper/2108.13179/) (2021)
- [Classification-based Financial Markets Prediction using Deep Neural Networks](https://mlsanity.com/paper/1603.08604/) (2016)

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

- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [Complexity of Injectivity and Verification of ReLU Neural Networks](https://mlsanity.com/paper/2405.19805/) (2024)
- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [The Reachability Problem for Neural-Network Control Systems](https://mlsanity.com/paper/2407.04988/) (2024)
- [The Complexity of Verifying Feedforward Neural Networks in Quantised Settings](https://mlsanity.com/paper/2605.29537/) (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 specifications over the input/output dimension given by conjunctions of linear inequalities. We recapitulate the proof and repair some flaws in the original upper and lower bound proofs. Motivated by the general result, we show that NP-hardness already holds for restricted classes of simple specifications and neural networks. Allowing for a single hidden layer and an output dimension of one as well as neural networks with just one negative, zero and one positive weight or bias is sufficient to ensure NP-hardness. Additionally, we give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.