Reachability is NP-complete even for the simplest neural networks

DOI10.1007/978-3-030-89716-1_10OpenAlexW3208223916MaRDI QIDQ2695495

Martin Lange, Marco Sälzer

Publication date: 31 March 2023

Full work available at URL: https://arxiv.org/abs/2108.13179

zbMATH Keywords

computational complexitymachine learningformal specification and verification

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Reachability in Simple Neural Networks ⋮ T4V: exploring neural network architectures that improve the scalability of neural network verification

Uses Software

• ImageNet
• AlexNet

Cites Work

• A new polynomial-time algorithm for linear programming
• A survey of safety and trustworthiness of deep neural networks: verification, testing, adversarial attack and defence, and interpretability
• Reluplex: an efficient SMT solver for verifying deep neural networks
• Classification-based financial markets prediction using deep neural networks
• Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks
• Reluplex: a calculus for reasoning about deep neural networks

This page was built for publication: Reachability is NP-complete even for the simplest neural networks