# Complexity of Reachability and Verification Problems in Neural Networks

Adrian Wurm

<figure><img src="image_1.png" /></figure>

## To cite this version:

Adrian Wurm. Complexity of Reachability and Verification Problems in Neural Networks. 2025. [hal-04692383v2](https://hal.science/hal-04692383v2)

HAL Id: hal-04692383

https://hal.science/hal-04692383v2

Preprint submitted on 24 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complexity of Reachability and Verification Problems in Neural Networks

Adrian Wurm

BTU Cottbus-Senftenberg, Lehrstuhl Theoretische Informatik, Platz der Deutschen Einheit 1, 03046 Cottbus, Germany, https://www.b-tu.de/wurm@b-tu.de

**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 in [27] 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 $\mathbb{R}$ for every non-linear polynomial and $\mathbb{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.

## 1 Introduction

Given the huge success of utilizing Neural Networks, NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, addressing tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [27]) just collect non-exclusively some areas for further reading: Image recognition [23], natural language processing [15], autonomous driving [13], applications in medicine [24], and prediction of stock markets [12], just to mention a few. Khan et al. [22] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is [7]. Among the many different aspects of areas where the use of Neural Networks seems beneficial, some also involve
safety-critical systems like autonomous driving or power grid management. In such a setting, when security issues become important, aspects of certification come into play [17].

In the present article we are interested in studying certain verification problems for NNs that help us to guarantee properties that we want a network to have. Starting point is the work by Sälzer and Lange [27] which itself is based on [21, 26]. The authors of these papers analyze the computational complexity of one particular such verification task. It deals with a reachability problem in networks using the Rectified Linear Unit together with the identity as its activation function. In such a net, specifications describe the set of valid inputs and outputs in form of two Linear Programming instances. The question then is to decide whether a valid input exists such that the network's result on that input is a valid output, i.e., whether the set of valid outputs is reachable from that of valid inputs. The problem is shown to be NP-complete [27]. Obviously, one can consider a huge variety of networks obtained by changing the underlying activation functions, for there are of course many activations frequently used in NN frameworks. In addition we can alter the decision problem from reachability to various other verification tasks. In the present work we thus extend the problem in [27] for commonly used activation functions and show that for most of them it will be complete either in (classical) NP or in the presumably larger class $\exists\mathbb{R}$, which captures the so-called existential theory of the reals.

Our first group of main results are as follows: The reachability problem is in P for linear activations, in NP for semilinear activations, NP-hard for all non-linear activations that are continuous on an interval, and $\exists\mathbb{R}$-hard for (almost) all sigmoidal functions such as $f(x) = 1/(1 + e^{-x})$ and arctan, as well as for several other commonly used activations. These results imply, for example, NP-completeness for frequently used activations such as (Leaky) ReLU, Heaviside and Signum. A most helpful tool for establishing these results is linking the problems under consideration to the area of constraint satisfaction problem CSP and known complexity results for special instances of the latter. This connection will provide us with a classification of a vast set of activation functions in the complexity classes between P and $\exists\mathbb{R}$. We also consider a variant of the reachability problem asking whether for all valid inputs the computed output is necessarily valid and establish several complexity results as well.

The second major subject area of investigation when dealing with network verification are various robustness properties as examined, for example, in [10, 26]. As a typical practical problem, it is desirable, that an autonomous driving car can still classify a road sign should that be a bit dirty, or that an AI is still able to detect a financial fraud even when a certain amount or transaction is scantly manipulated. We therefore require a network to have robustness against small input changes, random as well as adversarial ones. We will explore several ways to formalize this and compare them.

Another important requirement for verification in nets arises from minimization. A network is often desired to be as small as possible, not only because it can be evaluated faster, but also because verification is easier in a small network.
It is sometimes possible, for example, to detect nodes that carry essentially the same information, or sets of nodes whose information can be retrieved linearly or approximately, respectively, from the remaining nodes. This implies that no information is lost should those nodes be deleted. This motivates studying further decision problems, such as whether a network can be replaced by another network with less nodes computing the same function or whether a certain subset of nodes is actually dispensable and could be removed without changing the function.

The above problems are compared to each other and classified by how difficult they are to answer depending on the set of activation functions that the network has access to. The main results here are: All of them are decidable for semi-algebraic functions, the problems are easiest to solve when we only use linear functions, manageable for semi-linear functions and quite likely undecidable for functions with a curvature related to the exponential function.

One comment concerning computational model is in place here: The networks in principle are allowed to compute with real numbers, so the valid inputs we are looking for belong to some space $\mathbb{R}^n$. However, the network itself is specified by its discrete structure and rational weights defining the linear combinations computed by its single neurons. Should one move on to activations that are not semi-linear, an issue to be discussed is the computational model in which one performs the network calculations. If, for example, the common sigmoid activation $f(x) = 1/(1 + e^{-x})$ is used, it has to be specified in which sense it is computed by the net, exactly or approximately, and at which costs these operations are being performed.

The paper is organized as follows: In Section 2 we collect basic notions, recall the definition of feedforward neural nets as well as useful facts about Constraint Satisfaction Problems. Section 3 studies various activation functions and their impact on the complexity of reachability problems. We show that the reachability problem is basically the same as the CSP containing the graphs of the activation functions together with relations necessary to express linear programming instances. We conclude that the problem is NP-hard for every sensible non-linear activation. For several activation functions we prove even stronger results, namely hardness or completeness for the presumably much larger class $\exists\mathbb{R}$. We next complement those results in Section 4 by studying Verification of Interval property and Network Equivalence, two problems closely related to reachability. We show in particular that they can be reduced to each other. The same is done in Section 5 for the robustness properties and for Network Minimization in Section 6. We finish with outlining some future research. The paper is an extension of the two conference publications [29] and [30], including also some new results.
# 2 Preliminaries and Definitions

## 2.1 Network decision problems

We start by defining the problems we are interested in; here, we follow the definitions and notions of [27] for everything related to neural networks. The networks considered are exclusively feedforward. In their most general form, they can process real numbers and contain rational weights.

**Definition 1.** A (feedforward) neural network $N$ is a layered graph that represents a function of format $\mathbb{R}^n \to \mathbb{R}^m$, for some $n, m \in \mathbb{N}$. The first layer with label $\ell = 0$ is called the input layer and consists of $n$ nodes called input nodes. The input value $x_i$ of the $i$-th node is also taken as its output $y_{0i} := x_i$. A layer $1 \le \ell \le L-2$ is called hidden and consists of $k(\ell)$ nodes called computation nodes. The $i$-th node of layer $\ell$ computes the output $y_{\ell i} = \sigma_{\ell i}(\sum_j c_{ji}^{(\ell-1)} y_{(\ell-1)j} + b_{\ell i})$. Here, the $\sigma_{\ell i}$ are (typically nonlinear) activation functions (to be specified later on) and the sum runs over all output neurons of the previous layer. The $c_{ji}^{(\ell-1)}$ are real constants which are called weights, and $b_{\ell i}$ is a real constant called bias. The outputs of all nodes of layer $\ell$ combined gives the output $(y_{\ell 0}, \dots, y_{\ell (k-1)})$ of the hidden layer. The final layer $L-1$ is called output layer and consists of $m$ nodes called output nodes. The $i$-th node computes an output $y_{(L-1)i}$ in the same way as a node in a hidden layer. The output $(y_{(L-1)0}, \dots, y_{(L-1)(m-1)})$ of the output layer is considered the output $N(x)$ of the network $N$.

Note that above, as in [27], we allow several different activation functions in a single network. This basically is because for some results technically the identity is necessary as a second activation function beside the 'main' activation function used. As usual for neural networks, we consider different choices for the activation functions used, but concentrate on the most frequently used ones, namely $ReLU(x) = max\{0, x\}$, Heaviside, simple deviations of them and various sigmoidal functions. We name nodes after their internal activation function, so we call nodes with activation function $\sigma(x) = x$ identity nodes and nodes with activation function $\sigma(x) = ReLU(x)$ ReLU-nodes for example. In the next definition, we recall from [29] the definition of the decision problems NNReach, VIP and NE. These problems have been investigated in [17] and [1], specifically NNReach in [29], [27] and [21]. Since we want to study complexity in the Turing model, we restrict all weights and biases in a NN to the rational numbers. The problems involve instances of Linear Programming LP in decision version. Recall that such an instance consists of a system of (componentwise) linear inequalities $A \cdot x \le b$ for a rational matrix $A$ and vector $b$ of suitable dimensions. We use these linear sets because they behave well when processed by simple activation functions and they are suitable for practical purposes, because they allow to approximate more complicated sets very well. The terminology of LP-specifications has its origin in software verification.
## 2.2 Basics on Constraint Satisfaction Problems CSP

As we shall see, analyzing the complexity of the reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [9]. Here, we collect the basic notions and results necessary for our purposes.

Informally, a CSP deals with the question whether values from a set A can be assigned to a set of variables so that given conditions (constraints) hold. These conditions are taken from a set of relations over A that, together with the set A, define the CSP. This can be formalized as follows:

**Definition 2.** A (relational) signature is a pair $\tau = (\mathbf{R}, a)$, where $\mathbf{R}$ is a finite set of relation symbols and $a: \mathbf{R} \to \mathbb{N}$ is a function called the arity.

A (relational) $\tau$-structure is a tuple $\mathcal{A} = (A, \mathbf{R}^A)$, where $A$ is a set called the domain and $\mathbf{R}^A$ is a set containing precisely one relation $R^A \subseteq A^{a(R)}$ for each relation symbol $R \in \mathbf{R}$.

An instance of a CSP over a given $\tau$-structure is a conjunction of constraints, where a single constraint restricts a variable tuple to belong to a particular relation of the structure under a suitable assignment of values from the domain to the variables. For the entire instance one then asks for the existence of an assignment satisfying all its constraints.

**Definition 3.** Let $\tau$ be a signature and $\mathcal{A}$ a $\tau$-structure with domain $A$ and relations $\mathbf{R}$. We always assume equality to be among the structure's relations. Let $X = \{x_1, x_2, \dots\}$ be a countable set of variables.

a) A constraint for $\mathcal{A}$ is an expression $R(y_1, \dots, y_{a(R)})$, where $R \in \mathbf{R}$, $a(R)$ its arity and all $y_i \in X$. For $z \in A^{a(R)}$ we say that $R(z)$ is true over $\mathcal{A}$ iff $z \in R^A$.

b) A formula $\psi$ is called primitive positive if it is of the form

$$ \exists x_{n+1} \dots \exists x_t : \psi_1 \wedge \dots \wedge \psi_k, $$

where each $\psi_i$ either is a constraint, $\top$ (true), or $\bot$ (false).

A formula with no free variables is a sentence.

c) The decision problem CSP($\mathcal{A}$) is the following: Let $n \in \mathbb{N}$ and a primitive positive $\tau$-sentence over $X$, i.e., a finite collection of constraints involving variables $\{x_1, \dots, x_n\} \subset X$ be given. The question then is, whether there exists an assignment $f: \{x_1, \dots, x_n\} \to \mathcal{A}$ for the variables such that each given constraint is true under the assignment $f$, i.e., all $R(f(y_1), \dots, f(y_{a(R)}))$ are true.

The size of an instance is $n+m$, where $m$ denotes the number of constraints.

**Example 1 (folklore).** Consider as domain the real numbers $\mathbb{R}$, together with the binary order relation $\leq$, the ternary relation $R_+$ defined via $R_+(x, y, z) \Leftrightarrow x + y = z$, and the unary relation $R_{=1}(x) \Leftrightarrow x = 1$. Then CSP($\mathbb{R}$; $\leq, R_+, R_{=1}$) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data. Reducing the former to the latter is obvious, for
the reverse direction first multiply all inequalities with a sufficiently large natural number to obtain integer coefficients only. Now observe that any natural number $n$ can be expressed as (one component of) a solution of a set of constraints involving $a = 1$ and doubling a number via $c = b + b$. This way, the binary expansion of $n$ can be constructed with $O(\log n)$ constraints. Apply this construction similarly to a variable $x$ of an instance of LP to obtain the term $n \cdot x$; now adding as constraint the equation $nx = 1$ similarly allows to express rational numbers as coefficients. Clearly the size of the resulting CSP instance is polynomially bounded in the (bit-)size of the given LP instance. Note that due to the theory of Linear Programming an instance with rational data has the same answer, independently of whether the considered domain is $\mathbb{R}$ or $\mathbb{Q}$.

**Definition 4.** A relation $R$ is called primitive positive definable (pp-definable) over $\mathcal{A}$, iff it can be defined by a primitive positive formula $\psi$ over $\mathcal{A}$, i.e.,

$$R(x_1, ..., x_n) \Leftrightarrow \exists x_{n+1}, ..., \exists x_t: \psi(x_1, ..., x_t).$$

It was shown by Jeavons, Bulatov and Krokhin [6] that CSP($\mathcal{A}$) and CSP($\mathcal{A}'$), where the latter structure arises from the former by attaching finitely many relations being pp-definable over $\mathcal{A}$, are linear-time equivalent. The obvious idea of replacing every occurrence of the new relation suffices to prove the statement. This argument will be used below once in a while.

**Definition 5.** a) A set $R \subseteq \mathbb{R}^n$ is called semilinear, iff it is a boolean combination of half-spaces<fnref n="1" />.

b) A set $R \subseteq \mathbb{R}^n$ is called essentially convex, iff for any two points $x, y \in \mathbb{R}^n$ the line segment $[x, y]$ contains only finitely many points that are not in $R$. If $R \subseteq \mathbb{R}^n$ is not essentially convex, any two points for which the property fails are called witnesses for the set not being essentially convex.

This gives us access to the following results of Bodirsky, Jonsson and von Oertzen:

**Theorem 1 ( [5]).** a) Let $R_1, ..., R_n$ be semilinear relations. Then CSP($\mathbb{Q}$; $\leq, R_+, R_1, ..., R_n$) is in $P$ if $R_1, ..., R_n$ are essentially convex and is NP-complete otherwise.

b) Let $R_1, ..., R_n$ be relations such that at least one of them is not essentially convex witnessed by two rational points. Then CSP($\mathbb{R}$; $\leq, R_+, R_1, ..., R_n$) is NP-hard.<fnref n="2" />

## 3 Complexity Results for Reachability

We shall now study the complexity of the reachability problem for various sets of activation functions used by the neural network under consideration. The

<footnote n="1">¹ i.e., finite unions, intersections and complements of sets of the form $Ax \leq b$</footnote>

<footnote n="2">² Note that we can not switch between the domains $\mathbb{Q}$ and $\mathbb{R}$ at will any more after dropping semilinearity with rational coefficients, for it could in this case change solvability.</footnote>
starting point will be the result from [21, 27] that NNReach(`id`, `ReLU`) is NP-
complete. We analyze the problem for a larger repertoire of activation functions,
formalized as follows:

**Definition 6.** Let $F$ be a set of activation functions from $\mathbb{R}$ to $\mathbb{R}$. If a neural network $N$ uses only activations from the set $F$, we call $N$ an $F$-network.

An instance of the reachability problem for neural networks NNReach($F$)
consists of an $F$-network $N$ and two instances of LP in decision version, one
with the input variables of $N$ as variables, and the other with the output variables
of $N$ as variables. These instances are also called input and output specification,
respectively. The problem is to decide if there exists an $x \in \mathbb{R}^n$ that satisfies the
input specification such that the output $N(x)$ satisfies the output specification.

**Definition 7.** Let $N$ be an $F$-network. The problem verification of interval property VIP($F$) consists of the same instances as for NNReach($F$), except for the output specification being the open polyhedron, meaning the interior of the solution space. This is due to technical reasons that will later on simplify the reductions. The question is whether for all $x \in \mathbb{R}^n$ satisfying the input specification, $N(x)$ will satisfy the output specification (cf. [17]).

As for NNReach, we denote by (A, B, N) such an instance, assuming n is
obvious from the context, by abuse of notation we ignore b.

The Network Equivalence problem NE($F$) is the decision problem whether
two $F$-networks describe the same function or not.

The size of an instance in the above problems is given as the sum of the
(usual) bit-sizes of the two LP instances and $T \cdot L$; here, $T$ denotes the number
of neurons in the net $N$ and $L$ is the maximal bit-size of any of the weights and
biases.

We omit $F$ in the notation if it is obvious from the context and write
VIP($N$, $A$, $B$) if VIP($F$) holds for the instance ($N$, $A$, $B$). The notations for the
other problems are similar.

To obtain results on the complexities of the above problems, in a first step it
will be very helpful to relate them to instances of certain CSP problems which
can be attached to a network canonically. This relation is made precise in the
following theorem. The fact that input and output specifications are LP instances
causes, that the structures below naturally contain the relations $R_{=1}$, $R_+$, and
$\le$. Further relations then will be determined by the activation functions used.

**Theorem 2.** For any set of unary real functions $F = \{f_1, \dots, f_s\}$, interpreted as relations via their graphs, CSP($\mathbb{R}; \le, R_+, R_{=1}, f_1, \dots, f_s$) and NNReach($id, f_1, \dots, f_s$) are linear-time equivalent.

*Proof.* We prove both directions explicitly for the case $s = 1$, then the conclusion
for $s > 1$ is immediate. For reducing NNReach(`id`, `f`) to CSP($\mathbb{R}; \le, R_+, R_{=1}, f$),
let $N$ be a network using `id` and `f` as activation functions. The weights and
biases of $N$ are assumed to be rational numbers. The variable set of the CSP
we construct contains one variable for each input and output node of $N$. For
each node $v$ in a hidden layer we introduce two variables $v_{sum}$ and $v_f$. Note
that according to Example 1 any linear inequality with rational coefficients can
be expressed as an instance of CSP($\mathbb{R}; \le, R_+, R_{=1}$) of linear size. Thus, the
input and output specifications of $N$ can be expressed as a set of constraints
in CSP($\mathbb{R}; \le, R_+, R_{=1}$) using the corresponding variables, which is of linear size
with respect to the size of those specifications. For the nodes in the hidden
layers, we proceed similarly. If node $v$ receives a linear sum $\sum_{i=1}^k c_i \cdot u_i + b$ as
its input, where $c_i, b$ are the rational weights and bias and the $u_i$ represent
the outputs of the previous layer, then as in Example 1 we add the constraint
$v_{sum} = \sum_{i=1}^k c_i \cdot u_{i,f} + b$ to the constructed instance. In case $v$ has $f$ as activation, we
add the constraint $v_f = f(v_{sum})$ and if $v$ was an $id$-node we add the constraint
$v_f = v_{sum}$. Obviously, the size of the CSP instance is linearly bounded in that
of the given net. Moreover, NNReach($id, f$) is solvable for $N$ if and only if the
above CSP has a solution.

For the reduction in the other direction, we translate an instance of CSP($\mathbb{R}; \le, R_+, R_{=1}, f$) into an instance of NNReach($id, f$) with only one hidden layer. For each variable in the instance we introduce a node in the input layer and encode all constraints of the form $\le, R_+$ and $R_{=1}$ into the input specification. For every constraint $y = f(x)$ we introduce a new $f$-node $\bar{x}$ in the hidden layer connected only to $x$ with bias 0 and weight 1. Next, we allocate an identity-node $\bar{y}$ in the hidden layer connected only to $y$ also with bias 0 and weight 1 for the connections. Finally, we require both nodes $\bar{x}$ and $\bar{y}$ to be equal by adding the equation $\bar{x} = \bar{y}$ to the output-specification.

It is obvious that both reductions can be performed for different functions in $F$, so the statement holds for the entire set. $\blacksquare$

Note that the proof does not depend on formalizing the specifications as LP
instances. It would similarly hold if the specifications would be given by (in-)
equality systems involving polynomials and adding a relation for multiplication
on the CSP-side. However, in this case checking feasibility of the specifications
is already difficult, see below.

Before studying NNReach for different activations, we briefly discuss a more
technical issue, namely the necessity of adding $id$ as activation.

The above proof implies that using an injective activation allows to omit $id$, if we drop the condition that the network has to be layered, meaning that a connection can skip layers:

**Lemma 1.** Let $f$ be injective, then $\text{NNReach}(id, f)$ and $\text{NNReach}(f)$ are linear-time equivalent.

*Proof.* Given the proof of Theorem 2 it only remains to avoid $id$-nodes when reducing an instance of CSP($\mathbb{R}; \le, R_+, R_{=1}, f$) to one of $\text{NNReach}(f)$. Identity nodes were used to propagate the value of a node $y$ in order to include a constraint $y = f(x)$ in the output specification. Instead, if $f$ is injective one can use a network node for $f(x)$ and one for $y$ and connect them with biases 0 and
weights 1 and −1, respectively, to an f-activation node computing $f(f(x) - y)$. Use another f-node to compute $f(0)$. This is possible by demanding a further in-put node to have value 0. Finally, in the output specification we add the equality between these two nodes with values $f(f(x) - y)$ and $f(0)$; injectivity provides the equivalence of this condition with $f(x) = y$. ■

For example, for nets using sigmoidal activation functions identity activations are not necessary.

Sälzer and Lange [27] asked whether for the NP-completeness result involving id and ReLU as activations one can avoid id as activation. Though ReLU is not injective, this in fact holds as well, even when we do not allow connections to skip layers:

**Proposition 1.** *The following problems are linear-time equivalent:*

i) CSP($\mathbb{R}$; $\leq$, $R_+$, $R_{=1}$, ReLU),

ii) NNReach(id, ReLU) and

iii) NNReach(ReLU) with only one hidden layer.

*As consequence, all three problems are NP-complete.*

*Proof.* Given the NP-completeness of NNReach(id, ReLU) and Theorem 2 above, it remains to reduce NNReach(id, ReLU) to NNReach(ReLU) in linear time. Towards this goal, we show that an identity node can be replaced by two ReLU-nodes in the following way: In the neural net to be constructed use two copies of the identity node and let both have the same incoming and outgoing connections as the original node. Replace the identity map by the ReLU map in both and invert all incoming and outgoing weights as well as the bias in the second one. Delete the initial identity node. This does not change the computed function of the network, because

$$
\begin{align*}
\sum_{i=1}^{n} a_i x_i + b &= \max\{0, \sum_{i=1}^{n} a_i x_i + b\} + \min\{0, \sum_{i=1}^{n} a_i x_i + b\} \\
&= \max\{0, \sum_{i=1}^{n} a_i x_i + b\} - \max\{0, -\left(\sum_{i=1}^{n} a_i x_i + b\right)\} \\
&= \text{ReLU}\left(\sum_{i=1}^{n} a_i x_i + b\right) - \text{ReLU}\left(-\left(\sum_{i=1}^{n} a_i x_i + b\right)\right) \\
&= \text{ReLU}\left(\sum_{i=1}^{n} a_i x_i + b\right) - \text{ReLU}\left(\sum_{i=1}^{n} (-a_i) x_i - b\right)
\end{align*}
$$

Applying this to every node gives us at most twice as many nodes with at most four times as many connections, thus the construction runs in linear time. ■

Theorem 2 enables us treating network reachability complexity questions by using the rich fund of complexity results for CSP problems of various types.
It is easily seen that NNReach(id) is by the previous theorem equivalent to CSP($\mathbb{R}$; $\leq$, $R_+$, $R_{=1}$, id) which in turn is equivalent to LP by Example 1, a problem well known to belong to P in Turing model complexity [20].

In [27] it was shown that NNReach(id, ReLU) is NP-complete, the link to CSPs however provides us with a much shorter proof. We will make use of Theorem 1 and apply Theorem 2:

**Corollary 1.** Let $f_1, \dots, f_s$ be unary real functions. If their graphs $g_1, \dots, g_s$ are semilinear with rational coefficients, then NNReach(id, $f_1, \dots, f_s$) is in P if and only if $g_1, \dots, g_s$, interpreted as binary relations, are essentially convex, and NP-complete otherwise. If at least one of the graphs $g_1, \dots, g_s$ is not essentially convex witnessed by two rational points, then NNReach(id, $f_1, \dots, f_s$) is NP-hard.

Though Corollary 1 certainly is not that surprising from the CSP point of view, it gives an elegant way to argue about the complexity of reachability problems for neural networks. Of interest now is to investigate the latter for many more activation functions. NP-hardness is for example the case for $f(x) = n^x, n \in \mathbb{N}, n > 1$, the witnesses are $f(0) = 1$ and $f(1) = n$, but not necessarily for $f(x) = e^x$ for it lacks a second rational point. Other activation functions that immediately give us NP-hardness this way are all non-linear rational functions (including polynomials) with rational coefficients, the square-root, all other rational roots, and the binary logarithm (logarithm to the base 2). Reasonable non-linear functions that lack rational points can be compressed to do so, such as $f(x) = \sin(\frac{x}{\pi})$ instead of $f(x) = \sin(x)$.

Moreover, if we use the strong version that requires semilinearity, we get that NNReach(id, f) is NP-complete for f being either the absolute value, the floor or ceiling function on a bounded domain, the sign or the Heaviside function, piecewise linear functions such as

$$f_{\alpha}(x) = \begin{cases} -1 & \text{if } x \leq -\alpha \\ \frac{x}{\alpha} & \text{if } -\alpha < x < \alpha, \\ 1 & \text{if } x \geq \alpha \end{cases},$$

the ReLU function, Leaky ReLU given via

$$R_{\alpha}(x) = \begin{cases} x & \text{if } x \geq 0 \\ \alpha x & \text{if } x < 0, \alpha \in \mathbb{Q} \end{cases}$$

as well as all their scalar generalizations and any other non-trivial rational step function such as the indicator function on an interval.

We will now see a much more powerful version of the NP-hardness part of Corollary 1:

**Theorem 3.** NNReach(id, f) is NP-hard for any non-linear function $f: \mathbb{R} \to \mathbb{R}$ that is continuous on an interval $[a, b] \subseteq \mathbb{R}$. This applies in particular to $f(x) = \frac{x}{1+e^{-x}}$ and all sigmoidal functions such as $f(x) = \frac{1}{1+e^{-x}}$, $f(x) = \frac{x}{\sqrt{1+x^2}}$ and $f(x) = \tanh(x)$ the hyperbolic tangent.
*Proof.* By the previous Corollary, it suffices to show that with such a function $f$ we can pp-define a new function $\bar{f}$ that excludes an interval witnessed by two rational points. The construction of $\bar{f}$ proceeds in several steps.

First, by density of $\mathbb{Q}$ there exist $\bar{a}, \bar{b} \in [a, b] \cap \mathbb{Q}$, $\bar{a} < \bar{b}$ so that $f|_{[\bar{a}, \bar{b}]}$ is still non-linear and continuous, we apply a linear transformation on the argument of $f$ so that we can assume $\bar{a} = 0$ and $\bar{b} = 1$. This is pp-definable for rational $\bar{a}, \bar{b}$ and neither changes non-linearity nor continuity. There must exist $c, d \in [0, 1] \cap \mathbb{Q}$, such that

$$f\left(\frac{c+d}{2}\right) \neq \frac{f(c)+f(d)}{2},$$

for $f$ would otherwise fulfill Cauchy's functional equation and therefore be linear.

Apply again a linear transformation on the argument that maps $c$ to 0 and $d$ to 1 and call the resulting function $\hat{f}$. By construction,

$$\hat{f}\left(\frac{1}{2}\right) \neq \frac{\hat{f}(0)+\hat{f}(1)}{2}$$

Define the function $\bar{f} : \mathbb{R} \to \mathbb{R}$ by $\bar{f}(x) = \hat{f}(x) + \hat{f}(1-x) - \hat{f}(0) - \hat{f}(1)$, this is primitive positive, for addition, affine transformation and the constants 0 and 1 are pp-definable in $(\mathbb{R}; \leq, R_+, R_{=1})$. It also matches the requirements for Corollary 1 part 2: The rational points are $\bar{f}(0) = 0$ and $\bar{f}(1) = 0$ and the function must exclude an interval because

$$\bar{f}\left(\frac{1}{2}\right) = \hat{f}\left(\frac{1}{2}\right) + \hat{f}\left(\frac{1}{2}\right) - \hat{f}(0) - \hat{f}(1) = 2\left(\hat{f}\left(\frac{1}{2}\right) - \frac{\hat{f}(0) + \hat{f}(1)}{2}\right) \neq 0$$

and by continuity. ■

<figure><img src="image_3.png" /></figure>

Note that any sensible/common activation function is either linear or of this type. We have shown that in the latter case, together with the identity as activation function, we have an NP-hard reachability problem. Theorem 3 however only states NP-hardness for this vast set of reachability problems. One might wonder about membership in NP. Our next main result will show that membership in NP and thus NP-completeness is unlikely for many of the activations, because reachability becomes complete for a complexity class conjectured to be much larger than NP.

**Definition 8 (cf. [28]).** The problem of deciding whether a system of polynomial equations with integer coefficients is solvable over $\mathbb{R}$ is called the Existential Theory of the Reals ETR. The complexity class $\exists\mathbb{R}$ is defined as the set of all decision problems that reduce to ETR in polynomial time. A problem is called $\exists\mathbb{R}$-complete if it is in $\exists\mathbb{R}$ and ETR reduces to the problem in polynomial time.

It was shown by Canny [8] that ETR is in PSPACE and it is easily seen that ETR is NP-hard. These are currently the best known bounds and it is widely believed that $NP \subset \exists\mathbb{R} \subset PSPACE$.
ETR can be formulated as CSP($\mathbb{R}$, $E$), where $E$ is the set of all polynomial relations $R_p := \{x \in \mathbb{R}^n | p(x)\nabla 0, \nabla \in \{=, <, \leq\}, p \in \mathbb{Z}[x_1, ..., x_n]\}$ and inequalities. Note that $E$ does not have finite signature any more, this issue has to be resolved before talking about algorithms and complexities of the CSP, for the encoding into Turing Machines is only possible for finite sets of relations. However, $E$ is a first-order reduct of $(\mathbb{R}; 1, +, \cdot)$, any integer polynomial can be described by the integers, addition, multiplication and logical combinations of these like we did for LP in Example 1. It thus suffices to represent the relations by their first-order definition. The integer coefficients can be assumed to be encoded in binary by the same ongoing that we used in Example 1.

For the results on ETR, we need the following new concept:

**Definition 9.** Let $\tau$ and $\sigma$ be finite relational signatures, $\mathcal{A}$ a $\tau$-structure and $\mathcal{B}$ a $\sigma$-structure. A primitive positive interpretation $I$ of $\mathcal{B}$ in $\mathcal{A}$ consists of:

* A natural number $d \in \mathbb{N}$ called the dimension,

* a primitive positive $\tau$-formula $\delta_I(x_1, ..., x_d)$ called the domain formula,

* for each atomic $\sigma$-formula $\phi(y_1, ..., y_k)$, a primitive positive $\tau$-formula $\phi_I(\bar{x}_1, ..., \bar{x}_k)$ called the defining formulas and

* a surjective map $h: D \to B$ called the coordinate map, where $D := \{(a_1, ..., a_d) | a_1, ..., a_d \in A, \mathcal{A} \models \delta_I(a_1, ..., a_d)\}$, A the domain of $\mathcal{A}$ and $B$ the domain of $\mathcal{B}$

so that the following holds for every atomic $\sigma$-formula $\phi$ and all $\bar{a}_1, ..., \bar{a}_k \in D$:

$$ \mathcal{A} \models \phi(h(\bar{a}_1), ..., h(\bar{a}_k)) \Leftrightarrow \mathcal{A} \models \phi_I(\bar{a}_1, ..., \bar{a}_k) $$

It was shown in [4] (Theorem 3.1.4), that if such a pp-interpretation of $\mathcal{B}$ in $\mathcal{A}$ exists, then there is a polynomial-time reduction from CSP($\mathcal{B}$) to CSP($\mathcal{A}$).

The next lemma will provide us with two versions of ETR that are more suitable for our reachability-problems:

**Lemma 2.** ETR is polynomial-time (in fact linear-time) equivalent to

a) ETR on the domain $\mathbb{R}^+ := \{x \in \mathbb{R} | x \geq 0\}$, denoted by $ET(\mathbb{R}^+)$

b) ETR on the domain $\mathbb{R} \cap (0, \frac{1}{n}]$ for any $n \in \mathbb{N}$ denoted by $ET(\mathbb{R} \cap (0, \frac{1}{n}])$.

*Proof.* a) We can easily reduce an instance of $ET(\mathbb{R}^+)$ into an instance of ETR by additionally demanding that its variables have to be positive:

$$ x \geq 0 \Leftrightarrow \exists y \in \mathbb{R} : y^2 = x. $$

For the reverse direction, pp-interpret $(\mathbb{R}, +, \cdot)$ 2-dimensional ($d = 2$) in $(\mathbb{R}^+, +, \cdot)$ as follows: The domain of the interpretation structure is the set of pairs

$$ D = \{(a, b) | a, b \in \mathbb{R}^+, a \cdot b = 0\}, \text{ so } \delta_I(a, b) \Leftrightarrow a \cdot b = 0. $$

For every variable $x$ in the ETR-instance, the interpreting pair $(a, b)$ consists of its positive part $a = \max(x, 0)$ and its negative part $b = \max(-x, 0)$, thus at
least one of them must be zero, the coordinate map is therefore $h(a, b) = a - b$. 1 is interpreted by $1_I(a, b) \Leftrightarrow a = 1$. The sum $(a, b) +_I (c, d) = (e, f) \Leftrightarrow a + c = e \wedge b + d = f$ could violate the rule that the product of the parts has to be zero, meaning $(a + c, b + d)$ is in general not in the domain $D$. Repair it via

$$ (a, b) +_I (c, d) = (e, f) \Leftrightarrow \exists \varepsilon : a + c - \varepsilon = e \wedge b + d - \varepsilon = f. $$

Finally we define multiplication employing the same idea:

$$ (a, b) \cdot_I (c, d) = (e, f) \Leftrightarrow \exists \varepsilon : ac + bd - \varepsilon = e \wedge ad + bc - \varepsilon = f. $$

b) We can again translate an instance of ET($\mathbb{R} \cap (0, \frac{1}{n}]$) into an instance of ETR by requiring its variables to be in $(0, \frac{1}{n}]$.

For the reverse direction, we first use part a) so we can work with $\mathbb{R}^+$. Note that we can replace $\mathbb{R}^+$ by $\mathbb{R} \cap [n, \infty)$ by a 1-dimensional pp-interpretation $I$ with domain $D = \{a | a \ge n\}$, so $\delta_I(a) \Leftrightarrow T$ and $h(a) = a - n$, so the defining formula for 1 is

$$ 1_I(a) \Leftrightarrow a = n + 1 $$

and for addition

$$ a +_I b = c \Leftrightarrow a + b = c + n. $$

For multiplication we have

$$ a \cdot_I b = c \Leftrightarrow (a - n) \cdot (b - n) = (c - n). $$

The final domain is the set $D = (0, \frac{1}{n}]$, we map every $x \ge n$ to its inverse $h_J(x) = \frac{1}{x}$. This allows us to interpret multiplication:

$$ a \cdot b = c \Leftrightarrow h_J(a) \cdot h_J(b) = h_J(c) $$

Addition is a bit more complicated,

$$ a + b = c \Leftrightarrow \frac{1}{h_J(a)} + \frac{1}{h_J(b)} = \frac{1}{h_J(c)} $$

is not sufficient, for $\frac{1}{h_J(a)}$, $\frac{1}{h_J(b)}$, $\frac{1}{h_J(c)} \notin (0, \frac{1}{n}]$. We additionally need

$$ \begin{aligned} \frac{1}{h_J(a)} + \frac{1}{h_J(b)} = \frac{1}{h_J(c)} &\Leftrightarrow \frac{h_J(b) + h_J(a)}{h_J(a) \cdot h_J(b)} = \frac{1}{h_J(c)} \\ &\Leftrightarrow (h_J(b) + h_J(a)) \cdot h_J(c) = h_J(a) \cdot h_J(b) \\ &\Leftrightarrow h_J(b) \cdot h_J(c) + h_J(a) \cdot h_J(c) = h_J(a) \cdot h_J(b) \end{aligned} $$

All of the multiplications in the last step give us values that are smaller than $\frac{1}{n}$, because we multiply values $\varphi(a), \varphi(b), \varphi(c)$ that are smaller than $\frac{1}{n}$. The addition on the left side could give us a result bigger than $\frac{1}{n}$, but only if the initial equation was incorrect (in which case we want the last equation to be unsolvable). ■
The following theorem will provide us with NNReach problems that are hard or even complete for $\exists\mathbb{R}$.

**Theorem 4.** a) NNReach(id, f) is $\exists\mathbb{R}$-complete for f any non-linear polynomial and $\exists\mathbb{R}$-hard for f any function that coincides with a non-linear polynomial on an interval.

b) NNReach(id, f) is $\exists\mathbb{R}$-hard in the following cases:

i) for any function f that allows to pp-define a function that coincides with the exponential function on an interval, including in particular the exponential function itself, the function $\text{ELU}(x) := \begin{cases} x & \text{if } x \ge 0 \\ \lambda(e^x - 1) & \text{if } x \le 0 \end{cases}$ where $\lambda \in \mathbb{Q}$, and the function $f(x) = e^{-|x|}$

ii) for the Gaussian function $f(x) = e^{-x^2}$

iii) for the arctan function $f(x) = \arctan(x)$ and

iv) for the Gallant-White cosine-smasher $f(x) = \begin{cases} 0 & x \le -\frac{\pi}{2} \\ \frac{1+\cos(\frac{3}{2}\pi)}{2} & x \in [-\frac{\pi}{2}, \frac{\pi}{2}] \\ 0 & x \ge \frac{\pi}{2} \end{cases}$

*Proof.* a) For p a polynomial, NNReach(id, p) obviously reduces to ETR, for p can be pp-defined by addition, multiplication and rational constants.

For completeness, we want to pp-define $f(x) = x^2$, let therefore $p(x) = \sum_{i=0}^{n} a_i x^i$ with $a_n = 1, n \ge 2$. Then $p(x + k)$ is pp-definable in $(\mathbb{R}; \le, +, 1, p)$ for every $k \in \mathbb{N}$, where we interpret the function p as a binary relation again. The idea is now to find a linear combination of these $p(x + k)$ that is equal to $x^2$ by inductively pp-defining polynomials of smaller degrees. We have

$$ \begin{aligned} p(x + k) &= \sum_{i=0}^{n} a_i (x + k)^i = \sum_{i=0}^{n} a_i \sum_{j=0}^{i} \binom{i}{j} x^j k^{i-j} = \sum_{i=0}^{n} \sum_{j=0}^{i} a_i \binom{i}{j} x^j k^{i-j} \\ &= \sum_{j=0}^{n} \sum_{i=j}^{n} a_i \binom{i}{j} x^j k^{i-j} = \sum_{j=0}^{n} x^j \sum_{i=j}^{n} a_i \binom{i}{j} k^{i-j} \end{aligned} $$

Note that for every $x^j$, the dominant term for $k \to \infty$ is the last one ($i = n$, namely $a_n \binom{n}{j} k^{n-j} = \binom{n}{j} k^{n-j}$), note that it diverges to $+\infty$, so it is non-zero for all but finitely many inputs. In every polynomial $p_{1,k} := p(x + k)$, $k \in \mathbb{N}$, the highest degree monomial is always $x^n$ with coefficient 1. The polynomials $p_{2,k}(x) := p_{1,k}(x) - p(x)$, $k \in \mathbb{N}$ have no $x^n$ term, they are at most of degree $n-1$. The $x^{n-1}$ term does not vanish for all but finitely many of the $p_{2,k}(x)$, since from every $p_{1,k}$ we subtracted the same polynomial, but the coefficients of the $x^{n-1}$ terms of $p_{1,k}$ grow linear in $k$. Take the first such polynomial with an $x^{n-1}$-term and divide it by its leading coefficient.

Repeat this step until a constant polynomial is reached. Now we have constructed for every $i \in \{0, ..., n\}$ a polynomial that is exactly of degree $i$, so they form a basis of $\langle 1, x, x^2, ..., x^n \rangle$. We can therefore pp-define $f(x) = x^2 \in$
$\langle 1, x, x^2, ..., x^n \rangle$. It remains to show that CSP($\mathbb{R}$; $\leq$, $R_+$, $R_{=1}$, $(\cdot)^2$) is ETR-hard. Multiplication can be pp-defined in ($\mathbb{R}$; $\leq$, $R_+$, $R_{=1}$, $(\cdot)^2$) via

$$a \cdot b = \frac{(a+b)^2 - a^2 - b^2}{2}$$

This concludes the proof, for multiplication was the only relation missing for ETR and the proof of Lemma 2 shows that it suffices to have multiplication on an arbitrary interval.

b), i) It suffices by Lemma 2 to reduce ET($\mathbb{R}^+$) to NNReach(id, $e^{(\cdot)}$), this is possible in linear time:

Positivity, additions and rational constants can be encoded in NNReach(id) as before. It remains to define multiplication, by Theorem 2 it suffices to pp-define it in ($\mathbb{R}$; $\leq$, $R_+$, $R_{=1}$, $e^{(\cdot)}$):

$$\begin{align*} x \cdot y = z &\Leftrightarrow (x+1) \cdot (y+1) = (z+1) + x + y \\ &\Leftrightarrow \log(x+1) + \log(y+1) = \log((z+1) + x + y) \end{align*}$$

The logarithm is pp-definable as the inverse of the exponential function.

To show that the exponential function on an arbitrary interval $[a, b]$ already suffices, observe that it enables the multiplication on the interval $[e^a - 1, e^b - 1]$

$$R_{\bullet, [e^{a-1}, e^{b-1}]} := \{x, y, z \mid x \cdot y = z \wedge x, y \in [e^a - 1, e^b - 1]\}.$$

It remains to show that multiplication $R_{\bullet, [e^{a-1}, e^{b-1}]}$ on an interval suffices to pp-define multiplication on $(0, \frac{1}{n}]$. Choose $e^a - 1 < \alpha < \beta < e^b - 1$ with $\alpha, \beta \in \mathbb{Q}$ and choose $n$ so that $\frac{1}{n} \leq \beta - \alpha$. For $x, y, z \in (0, \frac{1}{n}]$ we have

$$\begin{align*} x \cdot y = z &\Leftrightarrow (x + \alpha) \cdot (y + \alpha) = z + \alpha x + \alpha y + \alpha^2 \\ &\Leftrightarrow (x + \alpha) \cdot (y + \alpha) - z - \alpha^2 = \alpha x + \alpha y \end{align*}$$

The multiplication $(x + \alpha) \cdot (y + \alpha)$ can be performed, because both values are in $[\alpha, \beta]$. The subtraction of the rational constant $\alpha^2$ and variable $z$ are possible as well. Thus, the value $t = (x + \alpha) \cdot (y + \alpha) - z - \alpha^2$ is pp-definable in $(\mathbb{R}^+; \leq, R_+, R_{=1}, e^{(\cdot)}|_{[a,b]}$). Observe that

$$\begin{align*} x \cdot y = z &\Leftrightarrow (x + \alpha) \cdot (y + \alpha) - z - \alpha^2 = \alpha x + \alpha y \\ &\Leftrightarrow t = \alpha x + \alpha y \\ &\Leftrightarrow \frac{t}{2} + \alpha^2 = \frac{\alpha x + \alpha y}{2} + \alpha^2 \\ &\Leftrightarrow \frac{t}{2} + \alpha^2 = \alpha \left( \frac{x+y}{2} + \alpha \right) \end{align*}$$

For division by 2, demand a new variable $t'$ to fulfill $t = t' + t'$, adding $x, y$ and $\alpha$ is also possible, as well as the multiplication of $\alpha$ and $\frac{x+y}{2} + \alpha$, for both are in $[\alpha, \beta]$. This proves the first statement.
It follows that also the activation functions ELU($x$) := $\begin{cases} x & \text{if } x \ge 0 \\ \lambda(e^x - 1) & \text{if } x \le 0 \end{cases}$ and the function $f(x) = e^{-|x|}$ both result in ETR-hard NNReach-problems.

b), ii) We have that $f(2x) = e^{-(2x)^2} = e^{-4x^2} = (e^{-x^2})^4 = f(x)^4$. This means that we can pp-define the function

$$g : (0, \infty) \to \mathbb{R}, g(x) = x^4|_{(1, \infty)}$$

by $g(x) = f(2 \cdot f^{-1}(x))$. By $f^{-1}$ we mean any of the preimages of $x$ under $f$. Such a preimage can be pp-defined and the value of $g(x)$ is the same for both preimages. Now $\exists \mathbb{R}$-hardness follows by Lemma 2 and Theorem 4 a).

b), iii) It suffices again to pp-define a non-linear polynomial on an interval. To achieve this, recall that $\arccot(x) = \frac{\pi}{2} - \arctan(x)$ and that $\arctan(1) = \frac{\pi}{4}$ is pp-definable, so we can easily switch to $\arccot$. Next, recall

$$\arccot(x) + \arccot(y) = \arccot\left(\frac{xy - 1}{x + y}\right)$$

for $x, y > 0$. It follows that

$$\begin{aligned} \arccot(x) + \arccot(4x^3 + 3x) &= \arccot\left(\frac{4x^4 + 3x^2 - 1}{4x^3 + 4x}\right) \\ &= \arccot\left(\frac{(4x^2 - 1)(x^2 + 1)}{4x(x^2 + 1)}\right) = \arccot\left(\frac{(2x)^2 - 1}{2x + 2x}\right) = 2\arccot(2x) \end{aligned}$$

The non-linear polynomial $f(x) = 4x^3 + 3x$ can therefore be pp-defined by

$$f(x) = \cot(2\arccot(2x) - \arccot(x))$$

which concludes the proof.

b), iv) It suffices again to pp-define a non-linear polynomial on an interval. To achieve this, recall that $\cos(2x) = 2\cos^2(x) - 1$

The non-linear polynomial $f(x) = 2x^2 - 1$ can therefore be pp-defined by

$$f(x) = \frac{\cos(2 \cdot \arccos(x)) - 1}{2}$$

which concludes the proof. ■

*Remark 1.* Note that NNReach($id, e^{(\cdot)}$) is equivalent to CSP($\mathbb{R}$; $R_+$, $R_-$, 1, $e^{(\cdot)}$), also known as Tarski's exponential function problem. It is not even known whether this problem is decidable or not (cf. [25]). Similar connections between network decision problems and Tarski's exponential function problem have recently been made in [18].

An activation that is particulary hard to tackle is the sigmoid function $\sigma(x) := \frac{1}{1+e^{-x}}$. We now aim to show that pretty much every sigmoidal function leads to an ETR-hard NNReach problem. We will make use of the following result on functions with two-dimensional input:
**Theorem 5 (Miltzow and Schmiermann).**

Let $f: U \to R$ be a $C^3$-function where $(0,0) \in U \subseteq R^2$ so that $f(0,0) = 0$, all partial derivatives $f_x, f_y, f_{xx}, f_{xy}$ and $f_{yy}$ are rational in $(0,0)$, either $f_x(0,0) \neq 0$ or $f_y(0,0) \neq 0$ and $f$ is curved in $(0,0)$, meaning $(f_y^2 f_{xx} - 2f_x f_y f_{xy} + f_x^2 f_{yy})(0,0) \neq 0$. Let further $T: \mathbb{N} \to \mathbb{Q}_{>0}$ be a bounded function where the binary representation of $T(n)$ is computable in polynomial time in the representation if $n$. Then, CSP($\mathbb{R}; +, \{(x,y) \mid f(x,y) = z\}, x = \delta, x \ge 0$) is $\exists\mathbb{R}$-hard, even when considering only instances where $\delta = T(n)$, with $n$ being the number of variables.

If furthermore $U, \{(x, y) \in U \mid f(x, y) = 0\}$ and $\{(x, y) \in U \mid f(x, y) \ge 0\}$ are semi-algebraic, then CSP($\mathbb{R}; +, \{(x, y) \mid f(x, y) = 0\}, x = \delta, x \ge 0$) is $\exists\mathbb{R}$-complete.

We now derive a simplified version formulated for unary functions.

**Corollary 2.** Let $\sigma: \mathbb{R} \to \mathbb{R}$ be a $C^3$-function, then CSP($\mathbb{R}; +, \le, 1, \sigma$) is $\exists\mathbb{R}$-hard if one of the following holds:

i) $\sigma'(0), \sigma''(0) \in \mathbb{Q}$ and $\sigma''(0) \neq 0$.

ii) $\exists a \in \mathbb{R}$ pp-definable in $(\mathbb{R}; +, \le, 1, \sigma)$ so that $\sigma''(a) \in \mathbb{Q}\setminus\{0\}$.

If furthermore $\sigma$ is semi-algebraic, then CSP($\mathbb{R}; +, \le, 1, \sigma$) is $\exists\mathbb{R}$-complete in both cases.

*Proof.* i) Let $T \equiv 1$ and let $f(x, y) := \sigma(x) - \sigma(0) - y$, so $f$ is pp-definable by $\sigma$ and vice-versa. To compare CSP($\mathbb{R}; +, \{(x, y) \mid f(x, y) = 0\}, x = \delta = 1, y \ge 0$) with CSP($\mathbb{R}; +, \le, 1, \sigma$), first observe that $f(0, 0) = \sigma(0) - \sigma(0) - 0 = 0$, that $0 \neq f_y(0, 0) = -1 \in \mathbb{Q}$, $f_y(0, 0) = 0 \in \mathbb{Q}$ and that $f_x(0, 0) = \sigma'(0)$, $f_{xx}(0, 0) = \sigma''(0)$. A one-dimensional $C^3$-function is curved in 0 iff $\sigma''(0) \neq 0$. The relations $\le$ and $x \ge 0$ can easily be pp-defined by each other if we have access to the relation $+$.

Furthermore, $+, \le$ and $1$ are semi-linear, so includedness in ETR only depends on the semi-algebraicity of $\sigma$.

ii) In i), we can drop the condition $\sigma'(0) \in \mathbb{Q}$ by replacing $\sigma$ with $\bar{\sigma} := \sigma(x) + \sigma(-x)$, for we then still have $\bar{\sigma}''(0) = 2\sigma''(0) \in \mathbb{Q}\setminus\{0\}$ and $\bar{\sigma}'(0) = \sigma'(0) - \sigma'(0) = 0 \in \mathbb{Q}$. Also, semi-algebraicity and $C^3$ will not be lost.

The function $g(x) := \sigma(x + a)$ has all remaining properties required in i). $\blacksquare$

**Example 2.** The sigmoid (logistic) function $\sigma(x) = \frac{1}{1+e^{-x}}$ has the second derivative $\sigma''(x) = -\frac{(e^x-1)e^x}{(e^x+1)^3}$, which is zero iff $x = 0$.

If $e^a \in \mathbb{Q}$, it follows that $\sigma''(a) \in \mathbb{Q}$. This is for example the case for $a = -\ln(3)$, which is pp-definable via $\sigma(a) = \frac{1}{4}$.

The hyperbolic tangent also leads to an $\exists\mathbb{R}$-hard NNReach-Problem, for it is only a linear transformation of the logistic function. The same goes for its inverse, the hyperbolic areatangent.

# 4 Network Equivalence and Verification of Interval Property

In this section, we study the complexity of the decision problems VIP and NE introduced in Definition 7. They serve a similar purpose as NNReach, as many
verification tasks can only be formulated as a property that a bigger set of inputs should have simultaneously. Here, solving the complementary question, meaning the search for a counterexample, is often not suitable, because such a certificate could become hard to represent. We will see that in a lot of cases these problems are essentially the same.

**Theorem 6.** Let $F$ be a set of activation functions such that $sign, id \in F$.

a) NE($F$) one-one reduces to the complement of NNReach($F$) in linear time. Consequently, NE(id) is in $P$.

b) NNReach($F$) one-one reduces to the complement of NE($F$) in linear time. Consequently, NE(ReLU) is co-NP-complete and NE($f$) is co-NP-hard for any non-linear $f$ that is continuous on an interval.

c) NE truth-table reduces to NE with just one output neuron in linear time independent of the set of activation functions.

The same holds for Heaviside or a similar step function instead of sign, id can independently be replaced by ReLU.

*Proof.* a) If the networks $N_1$ and $N_2$ from the NE-instance have different numbers of layers, we "copy" the output of the "flatter" one by the identity function until both have the same height. The idea is now to construct a network $N$ that has the same input dimension as $N_1$ and $N_2$ and computes 0 on an input $x$ if and only if $y_1 = N_1(x) = N_2(x) = y_2$ and $\pm 1$ otherwise.

To achieve this we put both networks $N_1$ and $N_2$ into one network $N$ by contracting the corresponding input nodes and add one layer that computes the difference between the outputs of $N_1$ and $N_2$. More precisely, it computes for every output dimension $i$ the signum of the difference $y_i = sign(y_{1,i} - y_{2,i})$. We have equivalence of $N_1$ and $N_2$ iff all $y_i$ are always 0. We then add another layer that computes the signum of their weighted sum $y = sign(\sum_{i=1}^{m} 2^i \cdot y_i)$, which is 0 iff all $y_i$ are 0. In the last two layers we compute $z = sign(sign(y+1) - sign(y-1))$ which is 1 iff $y = \pm 1$ and 0 iff $y = 0$. $N$ together with the output specification $z \ge \frac{1}{2}$ is now an NNReach($F$)-instance that is true iff $N_1$ and $N_2$ are not equivalent.

b) We construct two new networks $N_1, N_2$ depending on the network $N$ and the specifications that form the instance of NNReach($F$). The idea is that $N_1(x) = 0$ iff both input and output specification of $N$ are fulfilled and -1 otherwise and that $N_2$ computes $-1$ independent of the input. The specification is a conjunction of equations of the form

$$ (E_k) \sum_{i=1}^{n} a_{i+k} v_{i,k} \geq a_k $$

for rational $a_{i+k}, a_k$ and the $v_{i,k}$ either all in the input or all in the output layer. For each such equation $E_k$, we introduce two connected sign-nodes that compute $\lambda_k = sign(sign(\sum_{i=1}^{n} a_{i+k} v_{i,k} - a_k) + \frac{1}{2})$. For every input, the result $\lambda_k$ is 1 if and only if the condition $E_k$ is fulfilled and $-1$ otherwise. We introduce
another sign-node that computes $\lambda = \text{sign}(\sum_{k=1}^{m} \lambda_k - m)$, the result is 0 if and only if all specifications are fulfilled and -1 otherwise, $\lambda$ is the overall network's output.

The second network $N_2$ that we construct has the same number of input-nodes $v_1, ..., v_l$ as $N$ and computes $\text{sign}(\text{sign}(v_1) - 2)$ which is $-1$ independent of the input. This means that the NNReach($F$)-instance $N$ is solvable if and only if the NE($F$)-instance $(N_1, N_2)$ returns false, implying $N_1$ and $N_2$ do not compute the same function.

c) To truth-table reduce NE on NE with just one output dimension, we ask for every output dimension if both networks always compute the same value. If that is always the case, we accept, otherwise we reject. ■

The following results can be proved by similar methods.

**Theorem 7.** Let $F$ be a set of activation functions.

a) VIP($F$) truth-table reduces to the complement of NNReach($F$) in linear time. Consequently, VIP(id) is in $P$ and VIP(ReLU) is in co-NP.

b) Let $F$ contain at least one among the functions $H$ (the Heaviside function), sign or ReLU. Then NNReach($F$) one-one reduces to the complement of VIP($F$) in linear time.

c) VIP($F$) truth-table reduces to VIP($F$) with just one output condition in linear time, meaning the output constraint is just one strict inequality.

*Proof.* a) To reduce VIP to the complement of NNReach, we ask for every output constraint that describes $B$ if its negation is satisfiable. If that is the case at least once, we reject, otherwise we accept. Note that this way every strict inequality describing an open half space becomes a non strict inequality describing the complement of an open half space, which is a closed half space.

b) For both $H$ and sign, we construct an instance of VIP equivalent to the negation of an instance $(N, A, B)$ of NNReach($F$). Let $H \in F$. The input constraints $A$ stay the same, the network $N'$ is a copy of $N$ with two additional layers following the original output layer. The first one contains for each output constraint $\sum_{i=1}^{k} a_i x_i \le b$ in $B$ an $H$-node computing $\bar{a} = H(b - \sum_{i=1}^{k} a_i x_i)$. The second added layer is the output layer of $N'$ and contains only one $H$-node computing $\hat{a} = H(\sum_{i=1}^{k} \bar{a}_i - n)$. The output $\hat{a}$ of $N'$ is 1 if the output of $N$ is in $B$ and 0 otherwise. We therefore choose the interval $[-\frac{1}{2}, \frac{1}{2}]$ as output constraint of VIP. Now

$$ \text{NNReach}(F)(N, A, B) \Leftrightarrow \neg \text{VIP}(F)(N', A, (-\frac{1}{2}, \frac{1}{2})) $$

The proof for sign is analogous.

For ReLU $\in F$, we choose again the same input constraints $A$ and the network $N'$ is a copy of $N$ with two additional layers after the previous output
layer. This time, the first layer contains for each output constraint $\sum_{i=1}^{k} a_i x_i \le b$
in B a ReLU-node computing $\bar{a} = ReLU(\sum_{i=1}^{k} a_i x_i - b)$ and the second added
layer (again the output layer) contains only one ReLU-node computing $\hat{a} =$
ReLU($\sum_{i=1}^{k} \bar{a}_i$). The constraints are simultaneously fulfilled if and only if $\hat{a} = 0$,
so

$$NNReach(F)(N, A, B) \Leftrightarrow -VIP(N', A, (0, \infty))$$

c) To truth-table reduce VIP to VIP with just one condition, we ask for every output constraint that describes B if it is always satisfied. If that is the case for every condition, we accept, otherwise we reject. ■

**Theorem 8.** Let F be a set of activation functions containing id or ReLU and H or sign.

a) NE(F) one-one reduces to VIP(F) in linear time.

b) VIP(F) one-one reduces to NE(F) in linear time.

*Proof.* a) Follows by Theorem 6 a) and Theorem 7.

b) Let $(N, A, B)$ be a VIP(F)-instance and assume that $id, sign \in F$, the proof for ReLU and/or H is analogous. We construct two networks $N_1$ and $N_2$ so that $N_1(x) = 1$ when $x \in A, N(x) \notin B$ and $N_1(x) = -1$ otherwise, and $N_2(x) = -1$ independent of $x$. $N_2$ is the network N with the following nodes attached: For every input condition $\sum_{i=1}^{n} a_{i+k}v_{i,k} \ge a_k$ we add two nodes computing $b_k = sign(sign(a_k - \sum_{i=1}^{n} a_{i+k}v_{i,k}) + \frac{1}{2})$. We have $b_k = 1$ if the condition holds and $b_k = -1$ otherwise. The next node computes $b = sign(\sum_{k=1}^{\ell} \frac{b_k}{\ell} - 1)$, which is 0 if all input conditions are simultaneously fulfilled and $-1$ otherwise. For the output constraints, we apply a similar construction to the output nodes to obtain a node computing $c = -1$ if the conditions hold and $c = 1$ otherwise. The overall output of $N_1$ is $d = sign(b + c - \frac{1}{2})$, which is 1 iff $x \in A, N(x) \notin B$ and $-1$ otherwise. $N_2$ computes $sign(sign(x_i) - 2)$ for any input $x_i$, so it is always $-1$. This means that VIP$(N, A, B)$ does not hold, meaning there is an input in A that is not mapped to B, iff $N_1$ and $N_2$ are not equivalent. ■

# 5 Complexity Results for Robustness

It is in the nature of AI applications, that the data that is later on processed differs from the training data, sometimes just slightly, sometimes by a lot. If one wants to classify inputs, it is often difficult to find optimal separating hyperplanes with respect to the training data due to the high dimensionality. The margins are often rather small, meaning the border separating two classes of inputs is very close to at least one of the given points. This means that when
operating the network in practice, a small measurement error might push the data right over this border and lead to misclassification, as well as a slightly but maliciously manipulated data set might fool an AI system implemented to detect safety issues or fraud. It is therefore desirable to have evidence that for certain inputs, a deviation that is small in some metric sense will not lead to a different classification. Such questions were examined, for example, in [26], we use them to assess the computed function in a more metric way similar to [10]. We formalize them in the following definition:

**Definition 10.** Let N be a NN, $N_i$ the projection of N on the i-th output dimension, $1 \le j \le m$ an output dimension, $\bar{x} \in \mathbb{R}^n$, $\varepsilon, \delta \in \mathbb{Q}_{\ge 0} \cup \{\infty\}$ and d a metric on $\mathbb{R}^n$ as well as $\mathbb{R}^m$.

a) The classification of a network input $x$ is the output dimension $1 \le i \le m$ with the biggest value $N_i(x)$, which is interpreted as the attribute that the input is most likely to have. We say that N has $\varepsilon$-classification robustness in $\bar{x}$ with respect to d iff the classification of every input $x$ that is $\varepsilon$-close to $\bar{x}$ is the same as for $\bar{x}$, meaning

$$CR_d(N, \varepsilon, \bar{x}, j) :\Leftrightarrow \forall x : d(x, \bar{x}) \le \varepsilon \Rightarrow \arg\max_i N_i(x) = j$$

and arbitrary $\varepsilon$-classification robustness iff

$$aCR_d(N, \varepsilon, \bar{x}) :\Leftrightarrow \exists j \in \{1, ..., m\} : CR_d(N, \varepsilon, \bar{x}, j)$$

b) We say that N has $\varepsilon$-$\delta$-standard robustness in $\bar{x}$ with respect to $d_\lambda$ iff N interpreted as a function is $\varepsilon$-$\delta$-continuous in $\bar{x}$, meaning

$$SR_d(N, \varepsilon, \delta, \bar{x}) :\Leftrightarrow \forall x : d(x, \bar{x}) \le \varepsilon \Rightarrow d(N(\bar{x}), N(x)) \le \delta$$

c) We say that N has $\varepsilon$-$L$-Lipschitz robustness in $\bar{x}$ with respect to d iff

$$LR_d(N, \varepsilon, L, \bar{x}) :\Leftrightarrow \forall x : d(x, \bar{x}) \le \varepsilon \Rightarrow d(N(\bar{x}), N(x)) \le L \cdot d(\bar{x}, x)$$

d) For a specific set F of activation functions, by abuse of notation we denote by $CR_d(F)$ the decision problem whether $CR_d(N, \varepsilon, \bar{x}, j)$ holds where we allow as input only networks N that use functions from F as activations, the notations for the other problems are defined similarly.

We denote by $d_p$ the metric induced by the p-Norm, meaning $d_p(x, y) = (\sum_{i=1}^{n} (x_i - y_i)^p)^{\frac{1}{p}}$.

Note that $d_1$ and $d_\infty$ share the property that all $\varepsilon$-balls $B_{\varepsilon,d}(x)$ are semi-linear sets and that they can also be described as instances of Linear Program Feasibility.

The property aCR seems redundant and unnatural at first, it is however not equivalent to CR at an extent that one could hastily assume. Note that it is in general already very hard to calculate the solution of just one network computation $N(x)$ for given N and x for certain activation functions, the result does not
even have to be rational or algebraic any more. It might on a theoretical level even be impossible to determine the output dimension yielding the largest value, i.e., to tell whether $N(x)_i \ge N(x)_j$, even though in practice that is easily done for almost all sensible instances. This possible undecidability arises from the fact that in the Turing model one is not capable of precisely computing certain sig- moidal functions, which is why seemingly obvious reductions from CR to aCR fail. Assume, for example, that an activation similar to the exponential function is included. In this case the problem might become harder than Tarski's expo- nential function problem, which is not even known to be decidable. Checking the properties aCR and CR is therefore not necessarily of the same computational complexity. Moreover, we need aCR as a technical tool in reduction proofs later on.

In network decision problems, $d_1$ and $d_\infty$ behave fundamentally different than the other $p$-metrics for they are the only ones that lead to linear constraints. General polynomial systems tend to have a higher computational complexity than linear ones, compare for example $\exists \mathbb{R}$ (NP-hard) with LP (in P) or Hilbert's tenth problem (undecidable) with integer linear systems (NP-complete). The following proposition partially covers the linear part of our network decision problems.

**Proposition 2.** Let $F$ be a set of piecewise linear activation functions.

a) The problems VIP($F$) and NE($F$) are in co-NP.

b) Let $d \in \{d_1, d_\infty\}$. Then $\text{SR}_d(F)$, $\text{CR}_d(F)$ and $\text{LR}_d(F)$ are in co-NP. This is specifically the case for $F = \{\text{ReLU}\}$.

*Proof.* Finding a witness for violation of the conditions works essentially the same for all the above problems, we will perform it for VIP.

The idea of the proof is that an instance is not satisfiable iff there exists an $x \in \mathbb{R}^n$ fulfilling the input specifications so that $N(x)$ does not fulfill the output specifications, meaning at least one of the equations does not hold. We then guess this equation along with some data that narrows down how the computation on such an $x$ could behave.

For a no-instance, let $x$ be an input violating the specifications. The certificate for the instance not to be solvable is not $x$ itself, because we would need to guarantee that it has a short representation. Instead, the certificate provides the information for every computation node, in which of the linear intervals its input is (for ReLU-nodes for example whether it returns zero or a positive value) when the network computes $N(x)$ together with the index of the violated output specification. This leaves us with a system like Linear Programming of linear inequalities that arise in the following way:

All of the input specifications $\sum_{i=1}^n a_i x_i \le b$ and the violated output specifica-
tion $\sum_{i=1}^m a_i N(x)_i > b$ are already linear. For each $\sigma$-node computing

$$
y_{\ell i} = \sigma \left( \sum_{j} c_{ji}^{(\ell-1)} y_{(\ell-1)j} + b_{\ell i} \right)
$$
that is by the certificate on an interval $[\alpha, \beta]$ where $\sigma(x)$ coincides with $a \cdot x + b$, we add the linear conditions

$$ \alpha \leq \sum_{j} c_{ji}^{(\ell-1)} y_{(\ell-1)j} + b_{\ell i} \leq \beta $$

and

$$ y_{\ell i} = a \cdot \sum_{j} c_{ji}^{(\ell-1)} y_{(\ell-1)j} + b_{\ell i} + b $$

The only difference to linear programming is that some of the equations are strict and some are not. This decision problem is also well known to still be in P by [19], Lemma 14.

The proof works in the same way for the other problems, as the negation of their instances can be formulated as a linear programming instance. For network equivalence for example, one would guess the output dimension that is unequal at some point, encode the computation of both networks, and demand that the outputs in the guessed dimensions are not the same, which can be expressed as a linear inequality. ■

The proof fails for non-linear metrics such as $d_2$, for the resulting equation system is not linear any more.

**Lemma 3.** Let $F$ be a set of activations containing ReLU. For any $\lambda \in [1, \infty]$, there are polynomial time reductions from $d = d_\infty$ or $d = d_1$ to $d = d_\lambda$ for $CR_d(F)$, a$CR_d(F)$ and $SR_d(F)$.

*Proof.* We will show how to reduce from $d_1$ for a network $N$ by constructing a network $N'$ that shows the same behavior in $\mathbb{B}_{\varepsilon,1}(\bar{x})$ as the given network and a sufficiently similar behavior on $\mathbb{B}_{\varepsilon,\lambda}(\bar{x})$. The proof for $d_\infty$ is analogous, as it only relies on the $\varepsilon$-ball to be a convex semi-linear set.

The idea for all three problems is to first retract a superset of the $\varepsilon$-ball to it so that $N' = N \circ T$, where $T(B_{\varepsilon,\lambda}(\bar{x})) = B_{\varepsilon,1}(\bar{x})$.

Let $(N, \varepsilon, \bar{x}, j)$ be an instance of $CR_1(F)$. The equivalent instance $(N', \varepsilon, \bar{x}, j)$ of $CR_\lambda(F)$ is constructed as follows:

We first insert $n$ new layers before the initial input layer, the first of them becomes the new input layer. These layers perform a transformation $T$ that has the following properties:

* $\forall x \in \mathbb{B}_{\varepsilon,1}(\bar{x}) : T(x) = x$. This ensures that if the initial instance failed the property $CR_1(F)$, the new one fails $CR_\infty(F)$.

* $\forall x \in \mathbb{B}_{\varepsilon,\lambda}(\bar{x}) : T(x) \in \mathbb{B}_{\varepsilon,1}(\bar{x})$. This ensures that if the initial instance fulfilled the property $CR_1(F)$, the new one fulfills $CR_\infty(F)$.

Such a function is for example

$$ T(x)_i = \text{ReLU}(x_i) - \text{ReLU}(x_i + \sum_{j=1}^{i-1} |T(x)_j| - \varepsilon) - (\text{ReLU}(-x_i) + \text{ReLU}(-x_i + \sum_{j=1}^{i-1} |T(x)_j| - \varepsilon)) $$
because $\mathbb{B}_{\varepsilon,1}(\bar{x}) \subseteq \mathbb{B}_{\varepsilon,\lambda}(\bar{x})$ and $T(x) \in \mathbb{B}_{\varepsilon,1}(\bar{x}) \forall x \in \mathbb{R}^n$.

For CR the reduction is complete, for aCR it is essentially the same. For SR$_{λ}$ we perform as one further step a transformation P of N(x) into a one-dimensional output, namely $P(N(x)) = \sum_{i=1}^{m} |N(x)_i|$. It is easily seen that $N(x) \in \mathbb{B}_1(\varepsilon) \Leftrightarrow P(N(x)) \in \mathbb{B}_1(\varepsilon) = [0, \varepsilon]$. ■

The previous Theorem as well as the following Proposition rely on the semi-linearity of the final sets, a crucial property when using the Ellipsoid Method. This is the reason why we restrict ourselves to metrics where balls are semi-linear sets. When moving on to $d_λ$ for arbitrary $λ$, we cross the presumably large gap in computational complexity between NP and $\exists \mathbb{R}$.

**Proposition 3.** Let $\lambda \in \{1, \infty\}$. Then $\text{VIP}(\{id\})$, $\text{NNReach}(id)$, $\text{NE}(id)$, $\text{SR}_\lambda(\{id\})$, $\text{CR}_\lambda(\{id\})$, aCR$_\lambda(\{id\})$ and LR$_\lambda(\{id\})$ are in P.

*Proof.* $\text{NNReach}(id)$ is a special case of Linear Programming Feasibility. For the other problems, we argue that their complements are in P=co-P. Note that LPF is still in P if we allow strict linear inequalities. The complements of $\text{VIP}(\{id\})$, $\text{NE}(id)$, $\text{SR}_\lambda(\{id\})$, $\text{CR}_\lambda(\{id\})$, aCR$_\lambda(\{id\})$ and LR$_\lambda(\{id\})$ are global disjunc-tions of LP-instances of linear size, so all of these Problems are in P. ■

The following easy to prove lemma allows us to strengthen a couple of results on complexities in the semi-linear range of network verification.

**Lemma 4 ([29]).** An identity node can be expressed by two ReLU nodes without changing the computed function.

As consequence, adding *id* to the set *F* of allowed activations already con-taining ReLU does not change the computational complexity. Furthermore, when reducing one such problem to another one, we can assume *id* to be among the activations and freely use it in the reductions, this is used to show:

**Proposition 4.** Let *F* be a set of activation functions.

i) aCR$_d(F)$ is polynomial time reducible to CR$_d(F)$.

ii) If *d* is induced by a *p*-norm and if ReLU ∈ *F*, then CR$_d(F)$ is polynomial time reducible to aCR$_d(F)$.

*Proof.* i) To see if aCR$_d(N, \varepsilon, \bar{x})$ holds, check CR$_d(N, \varepsilon, \bar{x}, j)$ for all possible $j$ and see if one of them holds.

ii) For the reverse direction, let $(N, \varepsilon, \bar{x}, j)$ be an instance of CR$_d(F)$. We will construct an instance $(N_h, \varepsilon, \bar{x})$ of aCR so that

$$CR_d(N, \varepsilon, \bar{x}, j) \Leftrightarrow aCR_d(N_h, \varepsilon, \bar{x})$$

The idea is to apply a function *f* on the output that collects any possible overlap of all dimensions other than *j*. This function is then modified to a function *h* with 3 output dimensions described by a network $N_h$, where one dimension is the constant zero function, and it is guaranteed to be negative in both remaining
dimensions at some point. Also, iff $f$ was at some point positive, which happens exactly if there was an overlap, so should at least one component of $h$ be. Since $h$ is at some point negative in the second and third dimension, the only candidate for the pointwise biggest output dimension is the first, and this is the case iff there was an overlap in the output of the initial network. This means that $CR_d(N, \varepsilon, \bar{x}, j) \Leftrightarrow CR_d(N_h, \varepsilon, \bar{x}, 1) \Leftrightarrow aCR_d(N_h, \varepsilon, \bar{x})$. It remains to show that such functions $f, h$ exist and that they can be described by a network $N_h$.

Note that the following functions can be computed by neural networks that are modifications of $N$:

$$f(x) = \sum_{i=1}^{m} ReLU(N(x)_i - N(x)_j)$$

$$g(x) = f(x) - ReLU(f(x) - 1)$$

Note that $f(x) \ge 0$ and $f(x) = 0$ iff $j$ is the index for a maximal component. Furthermore if $f(x) \ge 1$, then $g(x) = 1$ and if $f(x) \in [0, 1]$ then $g(x) = f(x)$. Thus, $g \equiv 0$ iff $CR_d(N, \varepsilon, \bar{x}, j)$. Now define $h$ as

$$h(x) = (0, g(x) - \frac{2}{\delta}ReLU(x_1 - \bar{x}_1), g(x) - \frac{2}{\delta}ReLU(\bar{x}_1 - x_1)).$$

Where $\delta \in \mathbb{Q}$ is chosen so that $\delta < \varepsilon$, meaning $\bar{x} + \delta e_1, \bar{x} - \delta e_1 \in \mathbb{B}_{\varepsilon,d}(\bar{x})$ where $e_1 = (1, 0, ..., 0)$.

Let $N_h$ be the network computing $h$. When asked if $aCR_\lambda(N_h, \varepsilon, \bar{x})$, the second and third dimensions of $h$ cannot be the pointwise biggest, the only possible candidate is 0 (j=1) because $h_2(\bar{x} + \delta e_1), h_3(\bar{x} - \delta e_1) \le -1$. Also, $g$ is constantly 0 iff $CR_\lambda(N, \varepsilon, \bar{x}, j)$ holds, on the other hand $g \equiv 0$ holds iff $aCR_\lambda(N_h, \varepsilon, \bar{x})$, so $CR_\lambda(N, \varepsilon, \bar{x}, j) \Leftrightarrow aCR_\lambda(N_h, \varepsilon, \bar{x})$. ■

**Proposition 5.** Let $F$ be a set of activation functions. We have that

i) $SR_\infty(F)$ is linear time reducible to VIP($F$),

ii) $CR_\infty(F)$ is linear time reducible to VIP($F$),

iii) if $id \in F$, then $SR_\infty(F)$ is linear time reducible to $CR_\infty(F)$,

iv) if ReLU $\in F$, then $CR_d(F)$ is linear time reducible to $SR_d(F)$ for any metric $d$.

*Proof (Proposition 5).* i) Let $(N, \varepsilon, \delta, \bar{x})$ be an instance of $SR_\infty(F)$. To construct an equivalent instance of VIP($F$), we introduce two copies of the network $N$ and view them as one big network $N'$ with an input dimension twice the input dimension of $N$. We demand by input specification that the input of the first copy of $N$ is $\bar{x}$ and the input of the second copy is in the $\varepsilon$-ball of $\bar{x}$ with respect to $\| \cdot \|_\infty$, which is equivalent to $\forall i \in \{1, ..., n\} : -\varepsilon \le \bar{x}_i - x_i \le \varepsilon$, a linear equation system that we denote $A$. Similarly, we demand by output specification that $N(x)$ is in the $\delta$-ball of $N(\bar{x})$, which is equivalent to $\forall i \in \{1, ..., m\} : -\delta \le N(\bar{x})_i - N(x)_i \le \delta$, we denote this system $B$. This gives us the VIP($F$)-instance $(N', A, B)$ for which we have VIP$(N', A, B) \Leftrightarrow SR(N, \varepsilon, \delta, \bar{x})$.
ii) Let $(N, \varepsilon, \bar{x}, j)$ be an instance of $CR_{\infty}(F)$. We construct an equivalent instance of $VIP(F)$ as follows. The network remains $N$, the input specifications are $\forall i \in \{1, ..., n\} : \bar{x}_i - \varepsilon \le x_i \le \bar{x}_i + \varepsilon$ and the output specification is $\bigwedge_{i=1}^{m} N(x)_i \le N(x)_j$.

iii) Let $(N, \varepsilon, \delta, \bar{x})$ be an instance of $SR_{\infty}(F)$ with $m$ the output dimension of $N$. To construct an equivalent instance $(N', \varepsilon, \bar{x}, 2m+1)$ of $CR_{\infty}(F)$, we perform the computation of two copies of the network $N$ in parallel, which constitutes a new network $N'$ as follows:

<figure><img src="image_4.png" /><figcaption>Fig. 1. Idea iii)</figcaption></figure>

The first copy is shifted by one layer, so the layer that was the input layer is now in the first hidden layer with no incoming connections and the bias of node $i$ is $\bar{x}_i$, so that first copy just computes the value $N(\bar{x})$. The input layer of $N'$ is the input layer of the second copy, so the second copy of $N$ computes $N(x)$. We add a layer of id-nodes at the end of it that does not change the output but let it have the same number of layers as the first copy. We add one layer connecting both copies after the old output layer, this one becomes the new output layer, and it computes

$$(N(x)_1 - N(\bar{x})_1, ..., N(x)_m - N(\bar{x})_m, N(\bar{x})_1 - N(x)_1, ..., N(\bar{x})_m - N(x)_m, \delta).$$
The node corresponding to the last value $N'(x)_{2m+1} = \delta$ has no incoming connections and bias $\delta$. We have that $\forall i \in \{1, ..., m\} : |N(\bar{x})_i - N(x)_i| \le \delta$ iff $\forall i \in \{1, ..., m\} : N(\bar{x})_i - N(x)_i \le \delta \wedge N(x)_i - N(\bar{x})_i \le \delta$, so the two instances are in fact equivalent.

iv) Let $(N, \varepsilon, \bar{x}, j)$ be an instance of $CR_d(F)$. We construct an equivalent instance $(N', \varepsilon, 0, \bar{x})$ of $SR_d(F)$ as follows: We add two additional layers after the old output layer. The first one computes $\alpha_i = \text{ReLU}(N(x)_i - N(x)_j)$ for all $i$, these values are all 0 everywhere on $B_{d,\varepsilon}(\bar{x})$ iff $CR_d(N, \varepsilon, \bar{x}, j)$ holds. The next added layer computes $\beta = \text{ReLU}(\sum_{i=1}^m \alpha_i)$, this value is 0 everywhere on $B_{d,\varepsilon}(\bar{x})$ iff $CR_d(N, \varepsilon, \bar{x}, j)$ holds. Now we have that $CR_d(N, \varepsilon, \bar{x}, j) \Leftrightarrow SR_d(N', \varepsilon, 0, \bar{x}) \wedge N'(\bar{x}) = 0$, so it remains to encode that last condition as a $SR_d(F)$-instance. The function

$$f(x) := \sum_{i=1}^{n} \text{ReLU}(x_i - \bar{x}_i) + \text{ReLU}(\bar{x}_i - x_i)$$

is 0 in $\bar{x}$ and strictly positive everywhere else and there exists an $F$-network $N_f$ computing $f$. The networks $N'$ and $N_f$ can be combined to an $F$-network $N''$ computing $g(x) = \text{ReLU}(N' - N_f)(x)$. If $SR_d(N', \varepsilon, 0, \bar{x})$ holds, then

$$N'(\bar{x}) = 0 \Leftrightarrow g(x) = 0 \forall x \in B_{\varepsilon}(\bar{x}) \Leftrightarrow SR_d(N'', \varepsilon, 0, \bar{x}).$$

The conditions $SR_d(N', \varepsilon, 0, \bar{x})$ and $SR_d(N'', \varepsilon, 0, \bar{x})$ can be formalized as a single $SR_d$ instance by merging both nets $N'$ and $N''$ into a single larger one, so the reduction is in fact many-one. ■

**Proposition 6.** Let $F$ be a set of activation functions. If $id \in F$, then $NE(F)$ is linear time reducible to $CR_d(F)$ for any metric $d$.

*Proof.* Let $(N, N')$ be an instance of $NE(F)$. We merge both networks $N$ and $N'$ into one network $N''$ by identifying/contracting their corresponding inputs and subtracting their corresponding outputs both ways to obtain the output layer

$$(N(x)_1 - N'(x)_1, ..., N(x)_m - N'(x)_m, N'(x)_1 - N(x)_1, ..., N'(x)_m - N(x)_m, 0).$$

The last output node is always 0, this can be forced by introducing an id-node that has bias 0 and no incoming connections. Now

$$NE(N, N') \Leftrightarrow CR_d(N'', \infty, 0, 2m + 1),$$

which concludes the proof. ■

Note that for Lipschitz robustness and standard robustness also global variants make sense:

**Definition 11.** Let $N$ be a NN, $\bar{x} \in \mathbb{R}^n$ and $\varepsilon, \delta \in \mathbb{Q}_{\ge 0}$. We say that $N$ has (global) $\varepsilon$-$\delta$-standard robustness wrt the metric $d$ iff it has $\varepsilon$-$\delta$-standard robustness in every $\bar{x} \in \mathbb{R}^n$:

$$\text{glob-SR}_d(N, \varepsilon, \delta) := \forall x, \bar{x} : d(x - \bar{x}) \le \varepsilon \Rightarrow d(N(\bar{x}) - N(x)) \le \delta.$$
We define glob-LR<sub>d</sub> analogously; note that it coincides with L-Lipschitz continuity independently of ε.

This equivalence does not hold for local Lipschitz robustness: The function $x \cdot \chi_Q(x)$ is $\varepsilon$-1-Lipschitz robust in 0 for every $\varepsilon$, but not Lipschitz-continuous in any $\varepsilon$-ball around 0.

**Remark 2.** Global arbitrary $\varepsilon$-classification robustness glob-aCR<sub>d</sub> for a network N, meaning it has arbitrary $\varepsilon$-classification robustness in every input $x \in \mathbb{R}^n$, hardly ever happens at all. We have that only very artificial functions map inputs to different classes and still have global (arbitrary) classification robustness, for between two areas of different classification, there must be a dividing strip of diameter $\varepsilon$ in which both classifications must be choosable. The function $f: \mathbb{R} \to \mathbb{R}^2$, where

$$f = \begin{pmatrix} f_1 \\ f_2 \end{pmatrix} \quad \text{with} \quad f_1(x) = \begin{cases} 0, & \text{for } x \le -1 \\ x+1, & \text{for } -1 \le x \le -\frac{1}{2} \\ \frac{1}{2}, & \text{for } -\frac{1}{2} \le x \le \frac{1}{2} \\ x-1, & \text{for } \frac{1}{2} \le x \le 1 \\ 1, & \text{for } 1 \le x \end{cases}, \quad f_2(x) = 1 - f_1(x)$$

for example is globally 1-classification robust. Such functions, however, are unlikely for a network of "natural origin" for these areas of equal classification do not occur in usual training methods.

**Theorem 9.** Let F be a set of activation functions containing ReLU. Then:

i) glob-SR<sub>∞</sub>(F) reduces to NE(F).

ii) glob-SR<sub>∞</sub>(F), LR<sub>∞</sub>(F) and glob-LR<sub>∞</sub>(F) are co-NP-hard.

*Proof. i)* We reduce an instance $(N, \varepsilon, \delta)$ of glob-SR<sub>∞</sub>(F) to an instance $(N', N'')$ of NE(F) by using the ReLU-function to check whether certain values are positive or not and by forcing the differences $\|\bar{x}_i - x_i\|_{\infty}$ to be smaller than $\varepsilon$, again with the use of ReLU-nodes. We construct the network $N'$ as follows: The input $(x, y) = (x_1, ..., x_n, y_1, ..., y_n)$ has twice the dimension of the input of N. On the first half $(x_1, ..., x_n)$ we execute N to obtain $N(x)$. For each of the $y_i$ in the second half, we compute

$$f(y_i) = \varepsilon \cdot (\text{ReLU}(y_i) - \text{ReLU}(y_i - 1) - \frac{1}{2})$$

by ReLU-nodes in the first hidden layer, a bias of $-\frac{1}{2}$ in the second and a weight of $\varepsilon$ in the third. Note that $im(f) = [-\varepsilon, \varepsilon]$, we interpret $f(y_i)$ as $\bar{x}_i - x_i$. We now execute N again, this time on $(x_1 + f(y_1), ..., x_n + f(y_n))$ to obtain $N(x + \bar{x} - x) = N(\bar{x})$. We compute both $N(x) - N(\bar{x})$ and $N(\bar{x}) - N(x)$ by ReLU-nodes with bias $-\delta$ to obtain

$$N'(x, y) = (\text{ReLU}(N(\bar{x})_1 - N(x)_1 - \delta), \text{ReLU}(N(x)_1 - N(\bar{x})_1 - \delta), \dots)$$

$$\text{ReLU}(N(\bar{x})_m - N(x)_m - \delta), \text{ReLU}(N(x)_m - N(\bar{x})_m - \delta)).$$
SR<sub>∞</sub><sup>G</sup>(N, ε, δ) holds iff N' is constantly 0. The second network N'' consists of 2n input nodes, no hidden layer and 2m output nodes with all weights and biases 0. This network will compute 0 independently of the input, so

$$SR_{\infty}^{G}(N, \varepsilon, \delta) \Leftrightarrow NE(N', N'').$$

ii) We reduce an instance ϕ of 3-SAT with n clauses to an instance (N, ∞, n - 1/2) of the complement of glob-SR<sub>∞</sub>({ReLU}). The idea is to associate pairs of literals and their negations with pairs of nodes with the property that at least one of these nodes must have the value zero. We then interpret the zero-valued node as false and the other one, that may have any value in [0, 1], as true and replace ∧ and ∨ by gadgets that work with the function Ψ: ℝ → [0, 1] defined as x ↦ ReLU(x) - ReLU(x - 1). Note that it is easily constructable in a ReLU-network and Ψ|<sub>[0,1]</sub> = id|<sub>[0,1]</sub>.

For the reduction, introduce for each variable a inϕ an input variable α₁ and use the first two hidden layers to compute α₂ := Ψ(α₁). Use the third hidden layer to propagate α₂ as well as to compute ¬α₂ := 1 - α₂. In the fourth hidden layer compute α := 2·ReLU(α₂ - 1/2) for every atom as well as for the negations. Note that α = 0 or ¬α = 0 and the other one can be anything in [0, 1]. In the fifth and sixth hidden layer compute for every clause (a, b, c) the value Ψ(α + β + γ). In the seventh layer, add all nodes from the sixth layer, this is the overall output of the network. If the instance of 3-SAT is solvable, then N(x) = n is reachable via setting the true atoms to 1 and the false ones to 0. The value N(y) = 0 is always reachable, just assign every variable the value 1/2. This means that if the 3-SAT instance is solvable, then x and y are witnesses that glob-SR<sub>∞</sub>(N, ∞, n - 1/2) is false. On the other hand, if the 3-SAT instance is not solvable, then for every input Ψ(α + β + γ) = 0 for at least one of the clauses, so N(x) ≤ n - 1. Now we always have that N(y) ≥ 0 because Ψ ≥ 0, so |N(x) - N(y)| ≤ n - 1 and glob-SR<sub>∞</sub>(N, ∞, n - 1/2) is true.

We reduce 3-SAT to LR<sub>∞</sub>(F) and glob-LR<sub>∞</sub>(F) in the same way, the instance for LR<sub>∞</sub>(F) is (N, 1/2, 2n - 1, (1/2, ..., 1/2)) with the same network N as constructed above for glob-SR<sub>∞</sub>({ReLU}). We chose n - 1 < 1/ε < n so that LR<sub>∞</sub>(N, 1/2, 2n - 1, (1/2, ..., 1/2)) is equivalent to glob-SR<sub>∞</sub>(N, ∞, n - 1/2). This is true because the minimum of N(x) is 0 attained in (1/2, ..., 1/2) and the maximum is either n if the 3-SAT instance is satisfiable or at most n - 1 if it is not, taken on the boundary of the unit hypercube. The growth between the minimum and the maximum is linear because the intersection points where ReLU is not differentiable are in (1/2, ..., 1/2) and on the boundary of the unit hypercube, but never in between.

The instance (N, 1/2, 2n - 1) constructed by the reduction to glob-LR<sub>∞</sub>(F) is the same, because no other pair of points x, x̄ will lead to a steeper descent if the network was derived from a SAT-instance that is not satisfiable. This is because the steepest descent must necessarily point to the minimum if the function is linear along the connecting line and no other local minimum exists. ■

**Corollary 3.** glob-SR<sub>∞</sub>({ReLU}), NE({ReLU}), CR<sub>∞</sub>({ReLU}), SR<sub>∞</sub>({ReLU}), LR<sub>∞</sub>({ReLU}) and VIP({ReLU}) are co-NP-complete.
*Proof.* VIP($\{ReLU\}$) is in co-NP by Theorem 2 and glob-SR$_{∞}$($\{ReLU\}$) is co-NP hard by Theorem 9, ii). The chain of reductions in between is provided by Theorem 9 i), Theorem 6, and Proposition 5 iv), i).

# 6 Network Minimization

In this section, we want to analyze different criteria whether a network is unnecessarily huge. The evaluation of a function given as a network becomes easier and faster for small networks, it is therefore desirable to look for a tradeoff between accuracy and runtime performance, as for example discussed in [11, 16]. In the worst case, a long computation in an enormously huge network that was assumed to depict the training data more accurate due to its size, could lead to round-off errors in both the training and the evaluation, making the overall accuracy worse than in a small network.

**Definition 12.** Let $F$ be a set of activations. An $F$-network $N$ is called minimal, if no other $F$-network with fewer nodes than $N$ computes the same function. The decision problem $\text{MIN}(F)$ asks whether a given $F$-network $N$ is minimal. In that case we write $\text{MIN}(N)$.

**Definition 13.** Let $N$ be a network and $K$ the set of nodes of $N$.

a) Let $Y \subseteq K$ be a subset of the nodes, $G_N$ the underlying graph of $N$ and $G'_N$ its subgraph induced by $K \setminus Y$. The network $N'$ whose underlying graph is $G'_N$ and where all activations, biases and weights are the same as at the corresponding places in $N$, is said to be obtained from $N$ by deleting the nodes in $Y$. By abuse of notation we denote it by $N \setminus K := N'$.

b) A subset $Y \subseteq K$ of hidden nodes of a network $N$ is called unnecessary, if the network $N \setminus Y$ produced by deleting these nodes still computes the same function, otherwise $Y$ is called necessary. The problem to decide whether sets of nodes are necessary is NECE($F$), we write NECE($N, Y$) if $Y$ is necessary.

c) If NECE($N, Y$) for all non-empty subsets $Y \subseteq K$ of nodes, we write ANECE($N$), this also defines a decision problem in the obvious way.

It obviously holds that $\text{MIN}(N) \Rightarrow \text{ANECE}(N)$, the reverse direction however does not hold in general:

*Example 3.* A network can contain only necessary nodes and still not be minimal. Consider, for example, the $\{id, ReLU\}$-network $N$ that consists of an input node $x$, two hidden nodes $y_{1,1} = ReLU(x)$ and $y_{1,2} = ReLU(-x)$ and one output node with weights 1 and -1 and bias 0, so it computes $y_2 = id(y_{1,1} - y_{1,2}) = x$. The network represents the identity map and is not minimal, because the smallest $\{id, ReLU\}$-network $M$ computing the identity consists of an input node, no hidden nodes and one output node with activation $id$, weight 1 and bias 0. However every non-empty subset of hidden nodes in $N$ is necessary; if we delete $y_{1,1}$, the remaining network computes the negative part $x^- = \min\{0, x\}$ of the input, if we delete $y_{1,2}$ it computes the positive part and if we delete both it
computes the zero-function for the last node has no more incoming nodes at all and thus returns the empty sum. We call this network $Q$. <fnref n="3" />

Also consider the net $K$ computing the zero-function in the following way: In the first hidden layer, compute $y_{1,1} = y_{1,2} = ReLU(x)$, the output-node is connected to both with weights 1 and -1, respectively, and bias 0, so it computes $0 = ReLU(x) - ReLU(x)$. In $K$, both hidden nodes on their own are necessary, the subset containing both however is not, because when deleting those two, we remain with the network $Q$ that also computes the zero-function.

**Theorem 10.** Let $id \in F$, then the complement of NECE($F$) and NE($F$) are linear-time equivalent.

*Proof.* The first reduction is trivial,

$$NECE(N, \{y_1, ..., y_k\}) \Leftrightarrow \neg NE(N, N\{y_1, ..., y_k\})$$

For the other direction, let $M, N$ be two $F$-networks. We construct an instance of NECE($F$) that is equivalent to $\neg NE(N, M)$ as follows:

First, we merge $N$ and $M$ into a network $P$ that computes $N(x)$ and $M(x)$, then computes $y = N(x) - M(x)$ in the last hidden layer and then propagates the value $P(x) = id(y)$ to the output layer. Now if $y$ is deleted, $P\{y\} = 0$, because then the output node would have no incoming edges at all, so it would compute the identity over the empty sum, which is 0. It follows that $y$ is unnecessary iff $P \equiv 0$, which in turn is the case iff $N \equiv M$ meaning NE($N, M$), so we have that $\neg NE(N, M) \Leftrightarrow NECE(P, \{y\})$. ■

The next theorem concerns $\Pi_2^P = co - NP^{NP}$, the complexity class containing all languages $L$ who's complement $\bar{L}$ can be decided by a non-deterministic Turing machine with access to an oracle deciding a co-NP-complete problem, see for example [2]. A typical problem that is complete for $\Pi_2^P$ is for example to decide whether $\forall x \in \{0, 1\}^n \exists y \in \{0, 1\}^m : \varphi(x, y)$, where $\varphi$ is a propositional logic formula.

**Theorem 11.** Let $F$ solely contain semi-linear functions. Then

i) $MIN(F)$ is in $\Pi_2^P$.

ii) $ANECE(F)$ is in $\Pi_2^P$.

*Proof. i)* We argue that co- MIN is in $\Sigma_2^P$. The algorithm non-deterministically guesses a smaller representation $M$ of the function/network $N$ and then proves that NE($N, M$), which is co-NP-complete, see [29].

ii) In the same way, observe that co-ANECE($F$) can be solved by non-deterministically guessing an unnecessary subset $Y$ and then showing that the network remaining after deleting $Y$ is equivalent to the original net. ■

**Theorem 12.** If id is among the activations, NE($F$) is reducible to ANECE($F$) in polynomial time.

<footnote n="3">³ This also illustrates that the smallest network $M$ that is equivalent to $N$ is in general not isomorphic to a substructure of $N$.</footnote>
*Proof.* Let $(N, M)$ be an instance of NE. First, merge both $N$ and $M$ into one network by subtracting their corresponding output nodes. Then delete all nodes that are constantly zero. These are detected layer-wise starting with the nodes right after the input layer. For each node $n$, delete all nodes that do not affect it in the sense that they are in subsequent layers, in the same layer, or in a previous layer but with no connection or connection with weights 0 towards $n$. Then allocate one additional id-node in the following layer and connect it to $n$ with weight 1 and no bias. ■

A network using only the identity as activation is not extremely interesting, because a concatenation of affine linear functions is again affine linear. These networks are therefore not only not very powerful, but they neither become more expressive when new layers are added. Any such network can be compressed into a network with no hidden layers. This is the reason why many decision problems for these networks can be decided in polynomial time. However, there is an exception, that also proves that the reverse of Theorem 12 does not hold:

**Theorem 13.** *ANECE(id) is co-NP-complete.*

*Proof.* First, note that a set of unnecessary subset of nodes suffices as a certificate, so we only need to show hardness. We reduce PARTITION on the complement of ANECEas follows:

For $\{a_1, \dots, a_k\}$ an instance of PARTITION, introduce a network $N$ with one input node, one output node and one hidden layer containing nodes $n_1, \dots, n_{k+1}$. All biases are zero, all incoming weights of the $n_i$ are 1, the outgoing weight of $n_i$ is $a_i$ for $i \le k$ and the outgoing weight of $n_{k+1}$ is $-\frac{1}{2} \sum_{i=1}^k a_i$. The network computes the function $N(x) = \frac{x}{2} \sum_{i=1}^k a_i$. We can only obtain an equivalent network by deleting a set containing the only negative weighted node, which is $n_{k+1}$, in which case we also have to delete nodes with outgoing weights that sum up to $\frac{1}{2} \sum_{i=1}^k a_i$. Such a set exists iff $\{a_1, \dots, a_k\}$ contains a subset that sums up to $\frac{1}{2} \sum_{i=1}^k a_i$, which is the case iff $\{a_1, \dots, a_k\}$ is a yes instance of PARTITION.

# 7 Conclusion and Further Questions

We examined the computational complexity of various verification problems for neural networks such as reachability, robustness and minimality in dependence of the activation functions used. We provided conditions for includedness in and hardness for NP, translated two result for CSPs into the language of reachability problems, and showed ETR-hardness of the reachability problems for several typical activation functions. We also showed that NE and VIP are in many cases the same problem, which is essentially “co-NNReach”. For robustness questions,
we analyzed the connection between the distance function in use and the com-
plexity of the resulting problem. Specifically, we highlighted the computational
advantages of metrics with linear ε-balls. We provided a framework for minimiz-
ing networks and formulated these tasks as decision problems.

Further open questions are:

i) Do there exist activation functions that are not semilinear but still lead to a reachability problem in NP?

ii) Several results rely on the identity activation. Can this be omitted? Or is there a problem that becomes substantially easier when the identity map is dropped?

iii) Can the discussed ETR-hard problems be classified with respect to (potentially) larger complexity classes? Here, [14] already provides upper bounds.

iv) Can reductions between VIP, NE and NNReach be found that do not rely on certain functions to be included in the set of activations?

v) How do these problems behave when we also allow weights/biases to be real numbers and study the questions in a corresponding model able to compute over $\mathbb{R}$ such as the Blum-Shub-Smale model [3]?

vi) Is $LR_1(ReLU)$ complete for co-NP? Are $LR_1(F)$ and $LR_\infty(F)$ in general reducible on each other?

vii) Are ANECE and $\text{MIN}(F)$ $\Pi_2^P$-complete if $F$ only contains semi-linear functions?

**Acknowledgment:** I want to thank Klaus Meer for helpful discussion and the anonymous referees for several hints improving the writing.

References

1. Aws Albarghouthi. Introduction to neural network verification. *Found. Trends Program. Lang.*, 7(1–2):1–157, 2021.

2. Sanjeev Arora and Boaz Barak. *Computational complexity: a modern approach*. Cambridge University Press, 2009.

3. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. *Complexity and Real Computation*. Springer, 1998.

4. Manuel Bodirsky. *Complexity of Infinite-Domain Constraint Satisfaction*. Lecture Notes in Logic, 2021.

5. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen. Essential Convexity and Complexity of Semi-Algebraic Constraints. *Logical Methods in Computer Science*, 8, 2012.

6. Andrei A. Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. *SIAM Journal on Computing*, 34:720–742, 2003.

7. Ovidiu Calin. *Deep Learning Architectures - A Mathematical Approach*. Springer, 2020.

8. John Canny. Some algebraic and geometric computations in PSPACE. Technical report, Computer Science Division, University of California, Berkeley, 1988.

9. Clément Carbonnel and Martin C. Cooper. Tractability in constraint satisfaction problems: a survey. *Association for Computing Machinery*, 21:115–144, 2016.
10. Marco Casadio, Ekaterina Komendantskaya, Matthew L. Daggitt, Wen Kokke, Guy Katz, Guy Amir, and Idan Refaeli. Neural Network Robustness as a Verification Property: A Principled Case Study. 2021.

11. Jason Cong and Bingjun Xiao. Minimizing computation in convolutional neural networks. In *International conference on artificial neural networks*, pages 281–290. Springer, 2014.

12. Matthew Dixon, Diego Klabjan, and Jin Hoonc Bang. Classification-based financial markets prediction using deep neural networks. *Algorithmic Finance*, 6:67–77, 2017.

13. Sorin Grigorescu, Bogdan Trasnea, Tiberiu Cocias, and Gigel Macesanu. A survey of deep learning techniques for autonomous driving. *Journal of Field Robotics*, 37:362–386, 2019.

14. Teemu Hankala, Miika Hannula, Juha Kontinen, and Jonni Virtema. Complexity of neural network training and etr: Extensions with effectively continuous functions. *Proceedings of the AAAI Conference on Artificial Intelligence*, 38(11):12278–12285, Mar. 2024.

15. Geoffrey Hinton, Li Deng, Dong Yu, George E. Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N. Sainath, and Brian Kingsbury. Deep neural networks for acoustic modeling in speech recognition: the shared views of four research groups. *IEEE Signal Process*, 29:82–97, 2012.

16. Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In *Proceedings of the sixth annual conference on Computational learning theory*, pages 5–13, 1993.

17. Xiaowei Huang, Daniel Kroening, Wenjie Ruan, James Sharp, Youcheng Sun, Emese Thamo, Min Wu, and Xinping Yi. A survey of safety and trustworthiness of deep neural networks: verification, testing, adversarial attack and defence, and interpretability. *Computer Science Review*, 37, 2020.

18. Omri Isac, Yoni Zohar, Clark Barrett, and Guy Katz. DNN Verification, Reachability, and the Exponential Function Problem. 2023.

19. Peter Jonsson and Christer Bäckström. A unifying approach to temporal constraint reasoning. *Artificial Intelligence*, 102(1):143–155, 1998.

20. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. *Combinatorica*, 4:373–396, 1984.

21. Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Re-luplex: An Efficient SMT Solver for Verifying Deep Neural Networks. *Computer Aided Verification*, 10426:97–117, 2017.

22. Asifullah Khan, Anabia Sohail, Umme Zahoora, and Aqsa Saeed Qureshi. A survey of the recent architectures of deep convolutional neural networks. *Artificial Intelligence Review*, 53:5455–5516, 2020.

23. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet Classification with Deep Convolutional Neural Networks. *Association for Computing Machinery*, 2017.

24. Geert Litjens, Thijs Kooi, Babak Ehteshami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen A.W.M. van der Laak, Bram van Ginneken, and Clara I. Sánchez. A survey on deep learning in medical image analysis. *Medical Image Analysis*, 42:60–88, 2017.

25. Angus Macintyre and A.J. Wilkie. On the Decidability of the Real Exponential Field. *Kreiseliana: About and Around Georg Kreisel*, pages 451–477, 1996.
26. Wenjie Ruan, Xiaowei Huanga, and Marta Kwiatkowska. Reachability Analysis of Deep Neural Networks with Provable Guarantees. *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI*, pages 2651–2659, 2018.

27. Marco Sälzer and Martin Lange. Reachability is np-complete even for the simplest neural networks. In *Reachability Problems: 15th International Conference, RP 2021, Liverpool, UK, October 25–27, 2021, Proceedings 15*, pages 149–164. Springer, 2021.

28. Marcus Schaefer and Daniel Štefankovič. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. *Theory of Computing Systems*, 60:172–193, 2012.

29. Adrian Wurm. Complexity of reachability problems in neural networks. In *International Conference on Reachability Problems*, pages 15–27. Springer, 2023.

30. Adrian Wurm. Robustness verification in neural networks. In *International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, pages 263–278. Springer, 2024.