mlsanityData to 7 Oct 2026

Reachability Is NP-Complete Even for the Simplest Neural Networks

arXiv 2108.13179 ↗First posted 30 Aug 2021cs.CC cs.LGcited by 27

Not on the map. Why?

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.

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

Builds on

8 of 15 references.

References · 8

  1. 2017A Survey on Deep Learning in Medical Image Analysiscited by 1,182
  2. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  3. 2019A Survey of Deep Learning Techniques for Autonomous Drivingcited by 401
  4. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  5. 2019A Survey of the Recent Architectures of Deep Convolutional Neural Networkscited by 211
  6. 2018Reachability Analysis of Deep Neural Networks with Provable Guaranteescited by 93
  7. 2017Verifying Properties of Binarized Deep Neural Networkscited by 77
  8. 2016Classification-based Financial Markets Prediction using Deep Neural Networkscited by 25

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 2; 2024: 6; 2025: 8; 2026: 5.

27 papers.

Sort:

By area:

  1. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  2. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  3. 2025Neural Network Verification is a Programming Language Challengecited by 12
  4. 2025Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasonscited by 11
  5. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  6. 2022Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networkscited by 8
  7. 2024Provably Safe Neural Network Controllers via Differential Dynamic Logiccited by 7
  8. 2024A Certified Proof Checker for Deep Neural Network Verification in Imandracited by 7
  9. 2022Revisiting the Adversarial Robustness-Accuracy Tradeoff in Robot Learningcited by 6
  10. 2022Reachability In Simple Neural Networkscited by 5
  11. 2023OccRob: Efficient SMT-Based Occlusion Robustness Verification of Deep Neural Networkscited by 5
  12. 2025Abstraction-Based Proof Production in Formal Verification of Neural Networkscited by 5
15 more
  1. 2022Learning Provably Stabilizing Neural Controllers for Discrete-Time Stochastic Systemscited by 4
  2. 2024Revisiting Differential Verification: Equivalence Verification with Confidencecited by 4
  3. 2025Proof Minimization in Neural Network Verificationcited by 4
  4. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  5. 2022Verifying And Interpreting Neural Networks using Finite Automatacited by 2
  6. 2025Verifying Quantized Graph Neural Networks is PSPACE-completecited by 2
  7. 2026Provably Explaining Neural Additive Modelscited by 1
  8. 2026Random Parameter Noise Does Not Make Exact ReLU Verification Easycited by 1
  9. 2023STR-Cert: Robustness Certification for Deep Text Recognition on Deep Learning Pipelines and Vision Transformerscited by 0
  10. 2024Robustness Verifcation in Neural Networkscited by 0
  11. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  12. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  13. 2026The Complexity of Verifying Feedforward Neural Networks in Quantised Settingscited by 0
  14. 2026Rethinking Evaluation Paradigms in IBP-based Certified Trainingcited by 0
  15. 2026Security Properties of Neural Networks as Decision Problemscited by 0