Marco Sälzer ; Martin Lange - Reachability In Simple Neural Networks

fi:9219 - Fundamenta Informaticae, October 14, 2023, Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
Reachability In Simple Neural NetworksArticle

Authors: Marco Sälzer ; Martin Lange

    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.


    Volume: Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
    Published on: October 14, 2023
    Accepted on: October 6, 2023
    Submitted on: March 16, 2022
    Keywords: Computer Science - Computational Complexity,Computer Science - Machine Learning

    Consultation statistics

    This page has been seen 55 times.
    This article's PDF has been downloaded 32 times.