Complexity of Reachability and Verification Problems in Neural Networks
Abstract
In this paper we investigate formal verification problems for Neural Network computations under a complexity theoretic point of view. Various reachability problems will be in the focus, such as: Given symbolic specifications of allowed inputs and outputs in form of Linear Programming instances, do valid inputs exist such that the given network computes a valid output? Does this property hold for all valid inputs? The complexity of this question has been investigated recently by Sälzer and Lange for nets using the Rectified Linear Unit and the identity function as their activation functions. We complement their achievements by showing that the problem is NP-complete for piecewise linear functions with rational coefficients that are not linear, NP-hard for almost all suitable activation functions including non-linear ones that are continuous on an interval, complete for the Existential Theory of the Reals ∃R for every non-linear polynomial and ∃R-hard for the exponential function and (almost) all sigmoidal functions. For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. Then we relate the above problems to robustness questions, such as: Can an input be altered by just a little bit to change the output by a lot? Is the function computed by a network continuous with given parameters? And if not globally, is it continuous for a certain input? Is it Lipschitz-robust for a given L? These questions are formalized and their complexity is classified in dependence of the network's internal structure.
Related
- On the Architectural Complexity of Neural Networks
- Approximation of solutions of parameter-dependent problems by residual neural networks
- Error Analysis for Solving Elliptic Interface Problems with Randomized Neural Networks
- Efficient and Accurate Lift-and-Decoupling Generalized Transferable Neural Networks for Elliptic and Moving Interface Problems
- A Framework Integrating the Dynamic Stiffness Matrix with Physics-Informed Neural Networks for Solving Eigenvalue Problems and Analysing Dynamic Response
BibTeX
@misc{wurm2026complexity,
title = {{Complexity of Reachability and Verification Problems in Neural Networks}},
author = {Adrian Wurm},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-04692383v3},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Complexity of Reachability and Verification Problems in Neural Networks
AU - Adrian Wurm
PY - 2026
DA - 2026/10/05
PB - HAL
UR - https://hal.science/hal-04692383v3
AB - In this paper we investigate formal verification problems for Neural Network computations under a complexity theoretic point of view. Various reachability problems will be in the focus, such as: Given symbolic specifications of allowed inputs and outputs in form of Linear Programming instances, do valid inputs exist such that the given network computes a valid output? Does this property hold for all valid inputs? The complexity of this question has been investigated recently by Sälzer and Lange for nets using the Rectified Linear Unit and the identity function as their activation functions. We complement their achievements by showing that the problem is NP-complete for piecewise linear functions with rational coefficients that are not linear, NP-hard for almost all suitable activation functions including non-linear ones that are continuous on an interval, complete for the Existential Theory of the Reals ∃R for every non-linear polynomial and ∃R-hard for the exponential function and (almost) all sigmoidal functions. For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. Then we relate the above problems to robustness questions, such as: Can an input be altered by just a little bit to change the output by a lot? Is the function computed by a network continuous with given parameters? And if not globally, is it continuous for a certain input? Is it Lipschitz-robust for a given L? These questions are formalized and their complexity is classified in dependence of the network's internal structure.
ER -