Reachability in Simple Neural Networks

DOI10.3233/FI-222160MaRDI QIDQ6070612zbMATH OpenOpenAlexFDO

Authors Marco Sälzer, Martin Lange

Publication date 23 November 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityformal specification and verificationmachine learning

Mathematics Subject Classification ID

Computer science (68-XX)

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 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.

Recommendations

• Hardness results for neural network approximation problems
• Complexity of network training for classes of Neural Networks
• Star-based reachability analysis of deep neural networks
• Complexity of training ReLU neural network
• scientific article; zbMATH DE number 4155875

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
• Classification-based financial markets prediction using deep neural networks
• Combinatorial optimization. Theory and applications.
• Formal verification of piece-wise linear feed-forward neural networks
• Reachability is NP-complete even for the simplest neural networks
• Reducibility among combinatorial problems
• Reluplex: a calculus for reasoning about deep neural networks
• Reluplex: an efficient SMT solver for verifying deep neural networks
• The polynomial-time hierarchy

Cited in

(2)

• Reachable sets of classifiers and regression models: (non-)robustness analysis and robust training
• Reachability analysis for neural feedback systems using regressive polynomial rule inference

This page was built for publication: Reachability in Simple Neural Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6070612)