  In this paper we investigate formal verification problems for Neural Network
computations. Various reachability problems will be in the focus, such as:
Given symbolic specifications of allowed inputs and outputs in form of Linear
Programming instances, one question is whether valid inputs exist such that the
given network computes a valid output? Does this property hold for all valid
inputs? The former question's complexity has been investigated recently by
S\"alzer 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 $\exists \mathbb R$
for every non-linear polynomial and $\exists \mathbb R$-hard for the
exponential function and various sigmoidal functions. For the completeness
results, linking the verification tasks with the theory of Constraint
Satisfaction Problems turns out helpful.
