Complexity of Neural Network Training and ETR: Extensions with
  Effectively Continuous Functions
We study the complexity of the problem of training neural networks defined
via various activation functions. The training problem is known to be
existsR-complete with respect to linear activation functions and the ReLU
activation function. We consider the complexity of the problem with respect to
the sigmoid activation function and other effectively continuous functions. We
show that these training problems are polynomial-time many-one bireducible to
the existential theory of the reals extended with the corresponding activation
functions. In particular, we establish that the sigmoid activation function
leads to the existential theory of the reals with the exponential function. It
is thus open, and equivalent with the decidability of the existential theory of
the reals with the exponential function, whether training neural networks using
the sigmoid activation function is algorithmically solvable. In contrast, we
obtain that the training problem is undecidable if sinusoidal activation
functions are considered. Finally, we obtain general upper bounds for the
complexity of the training problem in the form of low levels of the
arithmetical hierarchy.
Teemu Hankala, Miika Hannula, Juha Kontinen, Jonni Virtema
# Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions

###### Abstract

We study the complexity of the problem of training neural networks defined via various activation functions. The training problem is known to be \(\exists\mathbb{R}\)-complete with respect to linear activation functions and the ReLU activation function. We consider the complexity of the problem with respect to the sigmoid activation function and other effectively continuous functions. We show that these training problems are polynomial-time many-one bireducible to the existential theory of the reals extended with the corresponding activation functions. In particular, we establish that the sigmoid activation function leads to the existential theory of the reals with the exponential function. It is thus open, and equivalent with the decidability of the existential theory of the reals with the exponential function, whether training neural networks using the sigmoid activation function is algorithmically solvable. In contrast, we obtain that the training problem is undecidable if sinusoidal activation functions are considered. Finally, we obtain general upper bounds for the complexity of the training problem in the form of low levels of the arithmetical hierarchy.

## I Introduction

We study the computational complexity of neural network (NN) training problems parameterized by various activation functions. Such a training problem asks, given a neural network architecture, finite training data, a cost function and a threshold, whether there exist real-valued edge weights and neuron biases for the network such that the total training error with respect to the training data is below the given threshold value. Neural network training problems have been studied extensively (see [1] for a comprehensive survey of the history) and recently a version of this problem was shown to be complete for the complexity class \(\exists\mathbb{R}\)[2, 3]. The aforementioned complexity class \(\exists\mathbb{R}\) is defined as the class of decision problems \(P\) that are polynomial-time reducible to the existential theory of the reals, that is, to the corresponding decision problem \(\mathrm{ETR}\)[4]. In other words, there is a polynomial-time computable function \(f\) such that \(x\in P\) if and only if \(f(x)\) is an existential first-order (\(\mathrm{FO}\)) formula that is true over the structure \((\mathbb{R},+,\times,<,=,0,1)\) of the ordered field of the real numbers. The latter question is easily seen to be equivalent to deciding whether a finite system of polynomial equations and inequations with integer coefficients and real unknowns has a solution.

The class \(\exists\mathbb{R}\) has turned out to have many interesting complete problems, for instance the so-called art gallery problem [5], two-dimensional packing problems [6], and certain decision problems on symmetric Nash Equilibria [7]. The activation functions in the \(\exists\mathbb{R}\)-complete training problem mentioned above are restricted to linear functions and the rectified linear unit (ReLU) activation function. In practice, there are also other useful activation functions such as the standard logistic sigmoid function, which is defined in terms of the exponential function, and sinusoidal activation functions. However, whereas \(\mathrm{ETR}\) is \(\mathsf{NP}\)-hard and included in \(\mathsf{PSPACE}\)[8], it is a long-standing and influential open problem posed by Alfred Tarski whether exponential arithmetic is decidable. This problem is known to be related to another major open question - _Schanuel's conjecture_ - in transcendental number theory (see, e.g., [9, 10]). On the other hand, the theory of the reals extended by the sine function is known to be undecidable, even under some further restrictions on the allowed syntax of the formulae [11].
In this article, we generalize the connection between \(\mathrm{ETR}\) and the neural network training problem from linear functions and the ReLU activation function to arbitrary real-valued functions. On the \(\mathrm{ETR}\) side, the corresponding activation function is added as a new function symbol to the signature of the underlying structure \((\mathbb{R},+,\times,<,=,0,1)\). We show that the NN training problem using \(f\) as an activation function together with the identity activation function is complete for the extension \(\exists\mathbb{R}_{f}\) of the class \(\exists\mathbb{R}\). In other words, this training problem is polynomial-time many-one bireducible to the existential theory of the reals extended with \(f\). Besides a single activation function \(f\), we allow the use of a set \(\tau\) of activation functions both in the training problem and in the definition of complexity classes of the form \(\exists\mathbb{R}_{\tau}\). Our result implies that the decidability of the training problem of neural networks using the sigmoid activation function is equivalent to the decidability of (the existential fragment of) exponential arithmetic. In fact, due to a certain model theoretic property (i.e., _model completeness_) of the theory of exponential arithmetic, this theory is decidable if and only if its existential fragment is decidable, and for showing decidability, it suffices to show it to be recursively enumerable (\(\Sigma^{0}_{1}\)) (see, e.g., [10] for further discussion). Another immediate consequence is that the neural network training problem is undecidable if the sine function is allowed to be used for neural activation. Interestingly, sinusoidal activation functions have already been observed to be hard to train in simulations, and have been analyzed, for instance, in [12].

Moreover, we establish upper bounds for the complexity of the NN training problem in the case of _effectively continuous_ activation functions. The class of effectively continuous functions (see [10]) contains, for example, the sigmoid function and sinusoidal activation functions. We show, using rational approximations and basic topological properties, that it is possible to place these problems and the theories \(\exists\mathbb{R}_{\tau}\) into \(\Sigma^{0}_{3}\), the third level of the arithmetical hierarchy. We also show that for effectively continuous functions, the complexity of \(\exists\mathbb{R}_{\tau}\) drops to \(\Sigma^{0}_{1}\) if the use of the equality sign is disallowed in the formulae. However, it is not known whether this seeming distinction is real or not, for instance, in the case of the exponential function and \(\exists\mathbb{R}_{\mathrm{exp}}\). As a matter of fact, this question can be shown to be equivalent to Tarski's exponential function problem. Note that disallowing equalities in favour of the strict order relation has no implications in the complexity of \(\mathrm{ETR}\), as has been shown in [4]. In addition, the neural network training problem can be restricted in a manner which is contained in the corresponding strictly ordered variant of the class \(\exists\mathbb{R}_{\tau}\). Under this formulation, the set of weights and biases satisfying an instance of the training problem can be observed to be _stable_ in the sense that it is an open set in the standard Euclidean topology.

In the next two sections, we will present model-theoretic definitions and properties of the complexity classes that are obtained by extending \(\mathrm{ETR}\) with new real-valued functions. We give an emphasis on effectively continuous functions and give a short summary of their basic properties, restated from [10]. Next, we formulate such variants of the NN training problem parameterized by different activation functions that are complete for the corresponding extensions of the complexity class \(\exists\mathbb{R}\). In the last section, we formulate some shortcomings of our neural network construction as open questions.

## II Preliminaries

For real numbers \(a\) and \(b\), we let \((a,b)\) and \([a,b]\) denote the open and closed intervals with endpoints \(a\) and \(b\), respectively. We write \(|a|\) for the absolute value of \(a\). For sets \(A\) and \(B\), we write \(A^{B}\) to denote the set of all functions with domain \(B\) and co-domain \(A\).

We assume familiarity with basic complexity classes such as \(\mathsf{P}\), \(\mathsf{NP}\) and \(\mathsf{PSPACE}\), and briefly review some concepts from computability theory (see, e.g., [13]). In this context, it is customary to assume that finite objects are encoded as natural numbers. A relation of natural numbers \(S\subseteq\mathbb{N}^{n}\), for a fixed \(n\geq 1\), is _computable_ (or _decidable_) if there exists a Turing machine that given any tuple \(x\in\mathbb{N}^{n}\) decides whether or not \(x\in S\). The _arithmetical hierarchy_ is formed by the classes of sets \(\Sigma^{0}_{k}\) and \(\Pi^{0}_{k}\), \(k\in\mathbb{N}\), defined recursively as follows:

* The class \(\Sigma^{0}_{0}=\Pi^{0}_{0}\) consists of all computable relations \(S\) over \(\mathbb{N}\).
* The class \(\Sigma^{0}_{k+1}\) consists of all relations \(S(x_{1},\ldots,x_{n})\) that are definable by a sentence of the form \(\exists y_{1}\ldots y_{m}R(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\), where \(R\) is a relation in \(\Pi^{0}_{k}\).
* The class \(\Pi^{0}_{k+1}\) consists of all relations \(S(x_{1},\ldots,x_{n})\) that are definable by a sentence of the form \(\forall y_{1}\ldots y_{m}R(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\), where \(R\) is a relation in \(\Sigma^{0}_{k}\).

The classes \(\Sigma^{0}_{1}\) and \(\Pi^{0}_{1}\) thus form the sets of _recursively enumerable_ relations and _co-recursively enumerable_ relations, respectively. In addition, a well-known consequence of Post's theorem is that for each natural number \(k\) the strict inclusions \(\Sigma^{0}_{k}\unlhd\Sigma^{0}_{k+1}\) and \(\Pi^{0}_{k}\subsetneq\Pi^{0}_{k+1}\) hold.

The first-order language of _real arithmetic_, written \(\operatorname{FO}(+,\times,<,=,0,1)\), is given by the grammar

\[\phi::=i<i\mid i=i\mid\phi\wedge\phi\mid\phi\vee\phi\mid\exists x\phi\mid\forall x\phi, \tag{1}\]

where \(i\) stands for numerical terms given by the grammar

\[i::=0\mid 1\mid x\mid i\times i\mid i+i,\ \ \ \text{where $x$ is a first-order variable.}\]

Note that adding negation to (1) does not increase the expressiveness of the language. A negated formula can be expressed positively via a negation normal form transformation and subsequent positive rewriting of negated atomic formulae.

Furthermore, we consider various extensions of the first-order language of real arithmetic. For a collection of relation and function symbols \(\mathcal{C}\), we write \(\operatorname{FO}(\mathcal{C})\) to denote the variant of \(\operatorname{FO}(+,\times,<,=,0,1)\) that uses only function symbols and relation symbols in \(\mathcal{C}\). _Existential real arithmetic_\(\exists\operatorname{FO}(+,\times,<,=,0,1)\) is obtained from (1) by dropping universal quantification. The logic \(\exists\operatorname{FO}(\mathcal{C})\) is defined analogously.

A formula \(\phi\) is _open_ if some variable appears free in \(\phi\), and otherwise _closed_. Closed formulae are referred to as _sentences_. Given a first-order structure \(\mathfrak{A}\) and a variable assignment \(s\), we write \(\mathfrak{A}\models_{s}\phi\) in the case that \(\phi\) is true in \(\mathfrak{A}\) with respect to \(s\). If \(\phi\) is a sentence, we write \(\mathfrak{A}\models\phi\) if \(\phi\) is true in \(\mathfrak{A}\).

The semantics for the language of real arithmetic is defined over the fixed structure \((\mathbb{R},+,\times,<,=,0,1)\) of real arithmetic in the usual way, and similarly for \(\operatorname{FO}(\mathcal{C})\) where the symbols in \(\mathcal{C}\) have their usual interpretations. As a slight abuse of notation, we use \(f\) to denote both a real-valued function and the corresponding function symbol. Moreover, we allow function symbols to be interpreted as partial functions. Any atomic formula with some undefined term with respect to an assignment \(s\) is defined to be false.

We use shorthands \(\mathbb{R}\) and \(\mathbb{R}^{<}\) for the models \((\mathbb{R},+,\times,<,=,0,1)\) and \((\mathbb{R},+,\times,<,0,1)\), respectively. For a collection \(\tau\) of additional functions, we write \(\mathbb{R}_{\tau}\) and \(\mathbb{R}_{\tau}^{<}\) for the corresponding extension of the models \(\mathbb{R}\) and \(\mathbb{R}^{<}\), respectively. We define the complexity class \(\exists\mathbb{R}_{\tau}\) as the collection of decision problems that have a polynomial-time many-one reduction to closed formulae of the existential real arithmetic with additional functions from \(\tau\). We also consider a subclass of \(\exists\mathbb{R}_{\tau}\) defined in terms of strict inequalities: the class \(\exists\mathbb{R}_{\tau}^{<}\) is defined otherwise as \(\exists\mathbb{R}_{\tau}\), except that we drop equality atoms \(i=i\) from (1).

## III The Existential Theory of the Reals in the Arithmetical Hierarchy

The full first-order theory of the ordered field of the real numbers admits an efficient version of quantifier elimination and thus is decidable, a result first shown by Alfred Tarski. Furthermore, the satisfiability problem of the existential fragment of this theory is known to be in \(\mathsf{PSPACE}\)[8]. In general, though, it is not known if the corresponding existential theory is decidable when new function symbols are added to the underlying model. The addition of the sine function is known to lead to undecidability, whereas Tarski's exponential function problem has been famously open since the 1950s.

In this section we show that if the added functions are assumed to satisfy certain fairly general computable topological properties, the satisfiability problem of the resulting existential theories can be bounded from above using low levels of the arithmetical hierarchy. Specifically, to this end, we use the following definition of effectively continuous functions from [10].

**Definition 1** ([10, Definition 4.2.1]).: _A function \(f\colon\mathbb{R}^{n}\to\mathbb{R}\) is called effectively continuous if there exists a computable function \(g\) with the following properties:_

* _To each_ \(n\)_-tuple of open intervals_ \((a_{1},b_{1})\)_,_ \(\ldots\)_,_ \((a_{n},b_{n})\) _with rational endpoints, the function_ \(g\) _associates an open interval_ \((c,d)\) _with rational endpoints such that_ \[\forall x\left(x\in(a_{1},b_{1})\times\cdots\times(a_{n},b_{n})\implies f(x) \in(c,d)\right).\]
* \(\forall M>0\ \forall\varepsilon>0\ \exists\delta>0\ \forall a_{i},b_{i}\) _it holds that, if_ \(c,d\) _is the output of_ \(g\) _on input_ \(a_{i},b_{i}\)_, then_ \[\bigwedge_{i\in[n]}(a_{i},b_{i})\subseteq[-M,M]\wedge|a_{i}-b_{i}|<\delta\implies |c-d|<\varepsilon.\]

_In this case, it is said that \(g\) computes the function \(f\). In addition, the set of all effectively continuous functions is denoted by \(\mathrm{ECF}\)._

As noted in [10], there is at most one effectively continuous function for each computable function. Thus the set \(\mathrm{ECF}\) is countable, and not every constant function is effectively continuous. On the other hand, rational constant functions, the identity function \(x\mapsto x\), the absolute value function \(x\mapsto|x|\), together with addition, multiplication, division, and the exponential function and basic trigonometric functions are effectively continuous. Using these functions and the following lemma, all rational functions and many neural activation functions, such as the ReLU function and the sigmoid function \(\sigma\colon x\mapsto 1/(1+\exp(-x))\), can be seen to be in \(\mathrm{ECF}\).

**Lemma 2** ([10, Lemma 4.2.6]).: _The set \(\mathrm{ECF}\) of all effectively continuous functions is effectively closed under composition, i.e., given computable functions \(g\) and \(g^{\prime}\) which compute two effectively continuous functions \(f\) and \(f^{\prime}\), respectively, we can effectively find a computable function \(g^{\prime\prime}\) which computes the composition \(f\circ f^{\prime}\) (when the latter is defined)._

The following two lemmas state some basic topological properties of effectively continuous functions that are central in our approach.

**Lemma 3** ([10, Remark 4.2.2 (rephrased)]).: _Effectively continuous functions are uniformly continuous on every compact cube of the form \([-M,M]^{n}\), where \(M>0\). In particular, effectively continuous functions are continuous in the Euclidean topology._

**Lemma 4** ([10, Proposition 4.2.10 (rephrased)]).: _Let \(T\) be a set of effectively continuous functions. Then the set_

\[\{(g,\bar{x}):\ \bar{x}\in\mathbb{Q}^{n},\ g\in T\text{ and }g(\bar{x})<0\}\]

_is recursively enumerable relatively to \(T\), i.e., there is an algorithm which, on input \(\bar{x}\in\mathbb{Q}^{n}\), and a code for \(g\in T\), stops if and only if \(g(\bar{x})<0\)._

This lemma implies that the set of rational solutions \(\bar{x}\in\mathbb{Q}^{n}\) for \(f(\bar{x})<0\) is recursively enumerable when \(f\) is effectively continuous.

We utilise some rudimentary notions and knowledge from point-set topology summarised in the following lemma (for basics of point-set topology see, e.g., the monograph [14]). In order to simplify the notation, for a topological space \(X\), we use \(X\) to denote also the underlying set of the space. A set \(D\subseteq A\) is said to be a _dense subset of \(A\)_ (in some topology) if the set \(D\) intersects every non-empty open subset of \(A\). A topological space \(X\) is _compact_ (more specifically, \(\omega\)-compact) if every countable collection \(E\) of open subsets of \(X\) such that \(X\subseteq\bigcup E\) has a finite subset \(F\subseteq D\) so that the condition \(X\subseteq\bigcup F\) holds.

**Lemma 5** (Topology toolbox).: _Let \(X\) and \(Y\) be topological spaces, \(f\colon X\to Y\) a continuous function, \(S\) a set in \(X\), \(A\) and \(B\) open sets in \(X\), and \(C\) an open set in \(Y\). Then the following claims hold._

* _The subsets_ \(A\cap B\)_,_ \(A\cup B\)_, and_ \(f^{-1}[C]\) _are open in_ \(X\)_._
* _The product_ \(A^{k}\) _is open in the product space_ \(X^{k}\)_._
* _If_ \(D\) _is a dense subset of_ \(S\) _then_ \(D^{k}\) _is a dense subset of_ \(S^{k}\) _in the corresponding product topology._
* _If_ \(S^{k}\) _is open in_ \(X^{k}\)_, then any projection of_ \(S^{k}\) _is open in the corresponding product space_ \(X^{n}\)_._
* _The product topology of compact spaces is compact._
* _If_ \(X\) _is a compact metric space, then_ \(X\) _is sequentially compact, that is, if_ \((x_{i})_{i\in\mathbb{N}}\)_, is a sequence of elements of_ \(X\)_, then there is a converging subsequence of_ \((x_{i})_{i\in\mathbb{N}}\)_._

The following lemma is an easy consequence of the previous topological facts.
**Lemma 6**.: _Let \(\mathfrak{A}\) be a model with a vocabulary \(\tau\), and \(\mathcal{T}\) a topology of the universe \(A\) of \(\mathfrak{A}\) such that_

* _for every_ \(n\)_-ary relation symbol_ \(R\) _in_ \(\tau\)_, the interpretation_ \(R^{\mathfrak{A}}\) _is an open set in the corresponding product topology of_ \(A^{n}\) _obtained from_ \(\mathcal{T}\)_, and_
* _for every_ \(n\)_-ary function symbol_ \(f\) _in_ \(\tau\)_, the interpretation_ \(f^{\mathfrak{A}}\) _is continuous with respect to the product topology of_ \(A^{n}\) _obtained from_ \(\mathcal{T}\)_._

_Let \(\phi(\bar{x})\in\exists\mathrm{FO}(\tau)\) be a formula with free variables in the \(n\)-tuple \(\bar{x}\). Then the set of \(n\)-tuples \(\bar{a}\) satisfying \(\phi(\bar{a})\) in \(\mathfrak{A}\) is an open set in the product topology of \(A^{n}\) based on \(\mathcal{T}\)._

Proof.: The proof proceeds by induction; we utilise topological facts from Lemma 5. First note that the interpretations of terms are continuous functions, since by induction they can be computed by composing continuous functions.

The interpretations of atomic formulae are open, for pre-images of open sets of continuous functions are open. Finally, if the interpretation of \(\phi\) and \(\psi\) are open, the interpretations of \(\phi\wedge\psi\) and \(\phi\vee\psi\) are open, for the intersections and unions of open sets are open, and the interpretation of \(\exists x\phi\) is open, for projections of open sets are open. 

**Lemma 7**.: _Let \(\mathfrak{A}\), \(\tau\) and \(\mathcal{T}\) be as in the previous lemma. Let \(D\) be a dense subset of the universe \(A\) in the topology \(\mathcal{T}\), and let \(\phi(\bar{x})\in\exists\mathrm{FO}(\tau)\) be a formula with free variables in \(\bar{x}\). Then \(\phi\) is satisfiable in \(\mathfrak{A}\) if and only if \(\phi(\bar{a})\) is true in \(\mathfrak{A}\) for some tuple \(\bar{a}\) from the dense set \(D\)._

Proof.: The \(\Leftarrow\) direction is immediate. For the converse, let \(\phi\) be an \(\exists\mathrm{FO}(\tau)\) formula with \(k\) free variables that is satisfied in \(\mathfrak{A}\). By Lemma 6, \(\phi\) defines an open set in \(A^{k}\). Note that, since \(D\) is a dense subset of \(A\) in the topology \(\mathcal{T}\), \(D^{k}\) is a dense subset of \(A^{k}\) in the corresponding product topology. Now by the definition of denseness, the intersection of \(D^{k}\) and the set defined by \(\phi\) is non-empty, and thus \(\phi(\bar{a})\) is true in \(\mathfrak{A}\) for some tuple \(\bar{a}\in D^{k}\). 

By the density of rational numbers, we can now obtain an upper bound for the satisfiability problem of formulae when function symbols are interpreted using effectively continuous functions. First, if the equality sign is not allowed in the formulae, the remaining strict order relation corresponds to open sets in the Euclidean topology.

**Theorem 8**.: _Let \(\phi(\bar{x})\) be an existential formula without identity over the structure \(\mathbb{R}_{\mathrm{ECF}}\). Then the set of rational solutions \(\bar{a}\in\mathbb{Q}^{n}\) for \(\mathbb{R}_{\mathrm{ECF}}\models\phi(\bar{a})\) is recursively enumerable. Moreover, the complexity class \(\exists\mathbb{R}^{<}_{\mathrm{ECF}}\) is contained in \(\Sigma^{0}_{1}\)._

Proof.: The proof proceeds by induction of the structure of \(\exists\mathrm{FO}(\{<\}\cup\mathrm{ECF})\)-formulae. First note that each atomic formula can be equivalently expressed by an inequality of the form \(f(\bar{y})<0\) for some effectively continuous function \(f\) and tuple of variables \(\bar{y}\). Thus, by Lemma 4, rational solution sets for atomic formulae are recursively enumerable. The cases for conjunction and disjunction are immediate, for finite intersections and unions of recursively enumerable sets are recursively enumerable.

Finally, consider the case for \(\exists y\psi(\bar{x},y)\). By the induction hypothesis, the rational truth set of \(\psi(\bar{x},y)\) is recursively enumerable; we claim that its projection \(P\) to the variables in \(\bar{x}\) is the recursively enumerable rational truth set of \(\exists y\psi(\bar{x},y)\). Note first that projections of recursively enumerable sets are recursively enumerable, and thus it suffices to show that \(P\) is the rational truth set of \(\exists y\psi(\bar{x},y)\). Assume that \(\phi(\bar{a},b)\), where \(\bar{a}\) is a tuple of rational numbers and \(b\) is a real number, is true in \(\mathbb{R}^{<}_{\mathrm{ECF}}\). Now since, by Lemma 6, the truth set of \(\phi(\bar{x},y)\) is open, there exists a rational number \(c\) such that \(\phi(\bar{a},c)\) is true in \(\mathbb{R}^{<}_{\mathrm{ECF}}\), from which the claim follows.

Now \(\exists\mathbb{R}^{<}_{\mathrm{ECF}}\) is in \(\Sigma^{0}_{1}\), since by Lemma 7, non-emptiness of truth sets of \(\exists\mathrm{FO}(\{<\}\cup\mathrm{ECF})\)-formulae are equivalent to checking non-emptiness of their rational truth sets, and \(\Sigma^{0}_{1}\) is clearly closed under polynomial-time reductions. 

In the following, a \(\tau\)_-polynomial_ is a \(\tau\)-term where, except for the arithmetic operations \(+\) and \(\times\), functions \(g\) can only appear with variable or constant arguments, that is, in the form \(g(x)\) or \(g(c)\). Furthermore, the
(total) degree of a polynomial \(P\) is defined as the maximum over the sum of the variable exponents in each monomial term occurring in \(P\). Note that the minus sign can be avoided by shuffling monomial terms from one side of the equations and inequations to the other.

**Lemma 9**.: _Let \(\tau\) be a set of function symbols and \(\phi(\bar{x})\in\exists\mathrm{FO}(\{+,\times,<,=,0,1\}\cup\tau)\). Then we can construct in polynomial time with respect to the length of the formula \(\phi(\bar{x})\) a \(\tau\)-polynomial \(P(\bar{x},\bar{y})\) of degree at most \(4\) such that \(\phi(\bar{x})\) is equivalent to_

\[\exists\bar{y}P(\bar{x},\bar{y})=0\]

_over the expanded reals \(\mathbb{R}_{\tau}\)._

Proof.: The proof of this lemma is analogous to the proof of [4, Lemma 3.2]. In fact, it suffices to first simplify all subterms of \(\phi\) of the form \(g(t)\) to the required form using new variables: replace \(g(t)\) by \(g(y)\) and add a new conjunct \(y=t\). Then the translation in [4] can be used directly by treating terms \(g(y)\) exactly the same way as in the original proof. 

Analogously to the \(\exists\mathbb{R}\)-complete decision problem \(4\)-\(\mathrm{FEAS}\) in [4], we define \(4\)-\(\mathrm{FEAS}_{\tau}\) to be the decision problem that asks, given a \(\tau\)-polynomial of degree at most \(4\), if the polynomial is feasible, i.e., has a root in the extended model \(\mathbb{R}_{\tau}\). Using the previous lemma, we obtain a complete problem for the corresponding extension of \(\exists\mathbb{R}\) with the functions in \(\tau\), thus justifying the use of the notation \(\exists\mathbb{R}_{\tau}\).

**Corollary 10**.: \(4\)_-\(\mathrm{FEAS}_{\tau}\) is \(\exists\mathbb{R}_{\tau}\)-complete._

Note that for product spaces of the form \(\mathbb{R}^{n}\), the standard Euclidean topology coincides with the product topology and is sequentially compact. With the help of Lemma 9, we can now give an upper bound for complexity class of the existential theory of the reals extended with effectively continuous functions.

**Theorem 11**.: \(\exists\mathbb{R}_{\mathrm{ECF}}\) _is contained in \(\Sigma^{0}_{3}\)._

Proof.: Let \(\phi\) be an existential sentence over \(\mathbb{R}_{\mathrm{ECF}}\). By Lemma 9, we may assume that \(\phi\) is of the form \(\exists\bar{x}P_{\tau}(\bar{x})=0\), where \(P_{\tau}\) is a \(\tau\)-polynomial over a vocabulary \(\tau\) that contains function symbols for the effectively continuous functions. By Lemmas 2 and 3, the function defined by \(P_{\tau}\) is effectively continuous. We observe that \(\exists\bar{x}P_{\tau}(\bar{x})=0\) is equivalent over \(\mathbb{R}_{\mathrm{ECF}}\) to the expression

\[\exists d>0\ \forall\varepsilon>0\ \exists\bar{x}\in B(\bar{0},d):|P_{\tau}( \bar{x})|<\varepsilon. \tag{2}\]

For this claim, \(\exists\bar{x}P_{\tau}(\bar{x})=0\) clearly implies (2). For the converse direction, (2) entails that there is an infinite sequence of tuples \((\bar{x}_{i})_{i\in\mathbb{N}}\) inside some open ball \(B(\bar{0},d)\) such that \(\lim_{i\to\infty}P_{\tau}(\bar{x}_{i})=0\). Since the closure \(\bar{B}(\bar{0},d)\) is compact, the sequence \((\bar{x}_{i})_{i\in\mathbb{N}}\) has a subsequence \((\bar{y}_{j})_{j\in\mathbb{N}}\) that converges to a limit point \(y\in\bar{B}(\bar{0},d)\). Since \(P_{\tau}\) is continuous, and \(\lim_{j\to\infty}P_{\tau}(\bar{y}_{j})=0\), we obtain that \(P_{\tau}(\bar{y})=0\) and, in particular, that the claim \(\exists\bar{x}P_{\tau}(\bar{x})=0\) holds.

The parameters \(\varepsilon\) and \(d\) can without loss of generality be assumed to be rational in (2). The innermost existentially quantified part of (2) then describes a predicate that is definable by an existential formula with \(\varepsilon\) and \(d\) as rational constant parameters over \(\mathbb{R}^{<}_{\mathrm{ECF}}\) and thus is in \(\Sigma^{0}_{1}\) by Theorem 8. The full expression (2) hence defines a \(\Sigma^{0}_{3}\) predicate. Since \(\exists\mathbb{R}_{\mathrm{ECF}}\) is defined as the class of problems that can be reduced in polynomial time to sentences of the form of \(\phi\), we conclude that \(\exists\mathbb{R}_{\mathrm{ECF}}\) is contained in \(\Sigma^{0}_{3}\). 

Now the following results are corollaries of the preceding theorems.

**Theorem 12**.: \(\exists\mathbb{R}^{<}_{\mathrm{exp}}\subseteq\Sigma^{0}_{1}\) _and \(\exists\mathbb{R}_{\mathrm{exp}}\subseteq\Sigma^{0}_{3}\)._

In fact, by the model completeness of the first-order theory of \(\mathbb{R}_{\mathrm{exp}}\) (see [9, 10]), the decidability of its existential fragment is equivalent to it being recursively enumerable, and also equivalent to the full first-order theory of \(\mathbb{R}_{\mathrm{exp}}\) being decidable. Thus, the precise relationship of \(\exists\mathbb{R}_{\mathrm{exp}}\) to \(\Sigma^{0}_{1}\) and \(\Sigma^{0}_{3}\) is an open problem. These observations can be generalized to any \(\mathbb{R}_{\tau}\) with a model-complete first-order theory and to any set \(\tau\) of effectively continuous functions.
Below, for convenience of stating the theorem, we assume below that \(\exists\mathbb{R}_{\sin}\) and \(\exists\mathbb{R}_{\sin}^{<}\) are closed under computable reductions.

**Theorem 13**.: \(\Sigma_{1}^{0}\subseteq\exists\mathbb{R}_{\sin}\subseteq\Sigma_{3}^{0}\) _and \(\exists\mathbb{R}_{\sin}^{<}=\Sigma_{1}^{0}\)._

Proof.: Note that the formula \(\sin(y)=0\wedge 4<y\wedge y<7\) defines \(2\pi\) in \(y\), and that the formula

\[\sin(2\pi\times x)=0\wedge(x=0\lor x>0)\]

defines natural numbers over the reals, with the help of the previously defined \(2\pi\). Hence \(\Sigma_{1}^{0}\)-hardness follows from the Davis-Putnam-Robinson-Matiyasevich theorem. For the second item, hardness follows from the results of [15]. 

## IV The Neural Network Training Problem

Under a suitable formulation, the complexity of the neural network training problem is complete for the complexity class \(\exists\mathbb{R}_{\tau}\), where the set \(\tau\) includes all those unary real-valued functions that are being used for neural activation. In the case of effectively continuous activation functions, the complexity of the training problem can be bounded using low levels of the arithmetical hierarchy. We concentrate on _feedforward neural networks_ under the following definitions.

**Definition 14**.: _A neural network architecture is a pair \(N=(G,\varphi)\) over a finite directed acyclic graph \(G=(V,E)\) and a function \(\varphi\) with the following definitions and properties:_

* _The vertices of the graph are called_ neurons_. A neuron of the network architecture_ \(N\) _is called an_ input neuron _if there are no incoming edges to it. A neuron is an_ output neuron _if there are no outgoing edges from it. Every other vertex of the graph is called a_ hidden neuron_._
* _The function_ \(\varphi\) _maps each non-input neuron_ \(v\) _to a function_ \(\varphi(v)\colon\mathbb{R}\to\mathbb{R}\)_. The function_ \(\varphi(v)\) _is the_ activation function _of the neuron_ \(v\)_. The value_ \(\varphi(v)\) _is alternatively denoted by_ \(\varphi_{v}\)_._

**Definition 15**.: _A neural network is a triple \(\mathcal{N}=(N,w,b)\) over a neural network architecture \(N\) together with real-valued functions \(w\) and \(b\) with the following properties:_

* _The function_ \(w\) _maps each edge_ \(e\) _of the underlying graph to a real number. The value_ \(w(e)\) _is the_ edge weight _of_ \(e\) _in the neural network and is denoted by_ \(w_{e}\)_._
* _The function_ \(b\) _maps each non-input neuron_ \(v\) _to a real number, called the_ bias _of_ \(v\)_, and denoted in short by_ \(b_{v}\)_._

**Definition 16**.: _A data point for a neural network architecture \(N\) is a function \(d\) that maps a real number to each input neuron and to each output neuron._

**Definition 17**.: _Let \(\mathcal{N}=(N,w,b)\) be a neural network. The neural function of \(\mathcal{N}\) is the unique function \(g\) with the following definitions and properties:_

* _The domain of_ \(g\) _is the set of all possible data points for the network architecture_ \(N\)_. For each data point_ \(d\)_, the value_ \(g(d)\) _is a function mapping each neuron to a real number, called the_ neural value _computed by the network for the given neuron. This function is also referred to as_ \(g_{d}\)_._
* _For each data point_ \(d\in\mathrm{dom}(g)\) _and for each input neuron_ \(v\) _it holds that_ \(g_{d}(v)=d(v)\)_._
* _For each_ \(x\in\mathrm{dom}(g)\) _and for each neuron_ \(v\in V\) _that is not an input neuron it holds that_ \[g_{d}(v)=\varphi_{v}\left(b_{v}+\sum_{u\in P}\left(w_{(u,v)}\times g_{d}(u) \right)\right),\] (3) _where_ \(P\) _is the set of predecessors of_ \(v\) _in the underlying directed acyclic graph._

In other words, the neural function for a fixed data point \(d\) is defined recursively as follows: For each input neuron \(v\), the value given by the neural function for \(v\) is the value \(d(v)\) as given by the data point. For every other neuron \(v\), the neural value \(g_{d}(v)\) is computed by adding the bias value \(b_{v}\) to the sum of the
incoming neural values, each multiplied by the corresponding edge weight, and finally this sum is mapped through the activation function \(\varphi_{v}\). The neural function is well-defined, since the network architecture is specifically assumed to be acyclic.

In the following definition, to simplify notation, we denote by \(d_{O}\) the tuple consisting of the values of a data point \(d\) for the output neurons of the network architecture, where some fixed order on the output neurons independent of the data points is assumed.

**Definition 18**.: _Let \(\tau\) be a set of unary functions. An \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) instance is a tuple of the form \((N,A_{E},A_{V},D,c,\prec,\delta)\) for a neural network architecture \(N=(G,\varphi)\) with the following properties:_

* _For each neuron_ \(v\) _of the network architecture_ \(N\)_, the activation function_ \(\varphi_{v}\) _is either the identity function_ \(x\mapsto x\) _or some function_ \(f\in\tau\)_._
* _A subset_ \(A_{E}\) _of the edges of_ \(N\) _are marked as_ active edges _in the training process. Similarly,_ \(A_{V}\) _is a subset of_ active neurons_._
* _A finite set_ \(D\) _of data points that maps neurons to rational numbers._
* \(A\) cost function__\(c\colon\mathbb{R}^{2m}\to\mathbb{R}\)_, where_ \(m\) _is the number of output neurons of_ \(N\)_, is assumed to be definable with an arithmetic expression._
* _The symbol_ \(\prec\) _is one the of relation symbols in the set_ \(\{=,\leq,<\}\)_._
* \(A\) threshold _value_ \(\delta\) _for allowed total training error is given as a rational number._

_A pair \((w,b)\) is a satisfying solution for the training instance \((N,A_{E},A_{V},D,c,\prec,\delta)\), if \((N,w,b)\) is a neural network as in Definition 15 so that for each edge \(e\) of \(G\) not in \(A_{E}\) it holds that \(w(e)=1\) and for each neuron \(v\) not in \(A_{V}\), \(b(v)=0\), and that the neural function \(g\) satisfies the condition_

\[\sum_{d\in D}c\left((g_{d})_{O},d_{O}\right)\prec\delta. \tag{4}\]

_Then \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) is the decision problem that asks, given an \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) instance, if there exists some satisfying solution for it. Furthermore, \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}^{<}\) is defined otherwise as the decision problem \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\), except that the strict order relation \(<\) is the only allowed choice for the relation symbol \(\prec\). Furthermore, for a single function \(f\), we use the notation \(\mathrm{NN}_{\mathrm{f}}\mathrm{-TRAINING}\) for \(\mathrm{NN}_{\{\mathrm{f}}}\mathrm{-TRAINING}\), and similarly for \(\mathrm{NN}_{\mathrm{f}}\mathrm{-TRAINING}^{<}\)._

If \(c\) is such a cost function that for all \(m\)-tuples \(\bar{a}\) and \(\bar{b}\) it holds that \(c(\bar{a},\bar{b})=0\) if and only if \(\bar{a}=\bar{b}\), then it is called _faithful_. If \(c\) is both faithful and non-negative, threshold value \(\delta=0\) is used, and \(\prec\) is replaced with the equality sign, then 4 is equivalent to all data points \(d\in D\) satisfying the condition \((g_{d})_{O}=d_{O}\), that is, \(g_{d}(v)=d(v)\) for every output neuron of the network.

**Lemma 19**.: _For any set \(\tau\) of unary real-valued functions, the problem \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}^{<}\) is in the complexity class \(\exists\mathbb{R}_{\tau\cup\{-,\dot{\tau}\}}^{<}\)._

Proof.: Let \((N,A_{E},A_{V},D,c,\prec,\delta)\) be an \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) instance. We show how to construct a formula \(\phi(\bar{w},\bar{b})\) of \(\exists\mathrm{FO}(\{+,-,\times,\dot{\div},<,0,1\}\cup\tau)\) in polynomial time such that there exists some satisfying solution for the given instance of the training problem if and only if \(\mathbb{R}_{\tau}\models\exists\bar{w}\,\exists\bar{b}\,\phi(\bar{w},\bar{b})\), where \(\bar{w}\) and \(\bar{b}\) are finite sequences of variables that in some fixed order encode the weights and biases for the active edges and active neurons, respectively. We use \(g\) to denote the intended neural function for the variables in \(\bar{w}\) and \(\bar{b}\). Let \(m\) be the number of output neurons of \(N\).

First we show, that for each data point \(d\in D\) and for each neuron \(v\) of the network, there is a term \(t_{(d,v)}\) which evaluates to \(g_{d}(v)\) over \(\mathbb{R}_{\tau}\). Namely, if \(v\) is an input neuron, we can express \(t_{(d,v)}\) succinctly as the corresponding input value given by \(d\), for instance, in the form of a fraction of two binary expansions of integral values. If \(v\) is a non-input neuron, a suitable \(t_{(d,v)}\) can be obtained as in expression 3 of Definition 17 using the terms \(t_{(d,u)}\) of the predecessors \(u\) of \(v\) and the sets \(A_{E}\) and \(A_{V}\). Note that the underlying graph structure is given as a part of the input, and that the graph is assumed to be acyclic.

According to Definition 18, the cost function \(c\) is expressible as an arithmetic expression. Then, for each \(d\in D\), there is some term \(t^{\prime}_{d}\) that evaluates to \(c((g_{d})_{O},d_{O})\) over \(\mathbb{R}_{\tau}\). Furthermore, the given rational
threshold value \(\delta\) can be expressed by some constant term \(t_{\delta}^{\prime\prime}\) Now, the relational formula 4 of Definition 18 is expressible as \(\sum_{d\in D}t_{d}^{\prime}<t_{\delta}^{\prime\prime}\), thus yielding the claimed formula \(\phi(\bar{w},\bar{b})\). 

Note that in the previous proof, \(\phi(\bar{w},\bar{b})\) is a single quantifier-free relational atom. It also defines the set of all satisfying solutions for the given training instance as a subset of \(\mathbb{R}^{|A_{E}|+|A_{V}|}\). If all the functions in \(\tau\) are effectively continuous, this solution set is open in the Euclidean topology by Lemma 6, and its intersection with \(\mathbb{Q}^{|A_{E}|+|A_{V}|}\) is recursively enumerable by Theorem 8. What is more, if the complete first-order theory of the model \(\mathbb{R}_{\tau}\) is _o-minimal_ (see, e.g., [10] for definition and discussion), then the set of satisfying solutions has only a finite number of connected components. In particular, the model \(\mathbb{R}_{\mathrm{exp}}\) is known to be o-minimal, whereas \(\mathbb{R}_{\mathrm{sin}}\) is not o-minimal. However, for example in the case of the sigmoid activation function, it is an open problem whether any positive lower bounds for the radii of open neighbourhoods for solutions in the open solution set can be computed, in general. By the model completeness of \(\mathbb{R}_{\mathrm{exp}}\), this question is connected to Tarski's exponential function problem via the so-called _first root conjecture_ (see, e.g., [9, 10]).

**Lemma 20**.: _For any set \(\tau\) of unary real-valued functions, the problem \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) is in \(\exists\mathbb{R}_{\tau}\)._

Proof.: Let \((N,A_{E},A_{V},D,c,\prec,\delta)\) be an \(\mathrm{NN}_{\tau}\mathrm{-TRAINING}\) instance and let \(\phi(\bar{w},\bar{b})\) be as in the proof of Lemma 19. It is enough to show that there is some formula \(\phi^{\prime}(\bar{w},\bar{b})\) of \(\exists\mathrm{FO}(\{+,\times,<,=,0,1\}\cup\tau)\) that is equivalent to \(\phi(\bar{w},\bar{b})\) over the structure \(\mathbb{R}_{\tau\cup\{-,\div\}}\). For this, note that if \(\theta(x)\) is a formula with some open variable \(x\), then formulae of the form \(\theta(-y)\) and \(\theta(y/z)\) can be defined existentially as \(\exists x(\theta(x)\wedge x+y=0)\) and \(\exists x(\theta(x)\wedge x\times z=y)\). Repeating these steps, the function symbols \(-\) and \(\div\) can be eliminated from \(\phi(\bar{w},\bar{b})\). 

Notice that the proof of Lemma 20 and the membership of the training problem in the class \(\exists\mathbb{R}_{\tau}\) can be generalized to the case where all of the data points, activation functions, threshold value and cost function are definable using existential formulae of the alphabet \(\{+,\times,<,=,0,1\}\cup\tau\). The set \(\tau\) may also include other than unary functions.

Next we define a decision problem for existential formulae in a certain normal form. The definition is an extension of the problem called ETR-INV in [5], now allowing the use of unary function symbols.

**Definition 21**.: _Let \(\tau\) be a set of unary real-valued functions. Then \(\mathrm{ETR}_{\tau}\mathrm{-INV}\mathrm{-FLAT}\) is the following decision problem: Given a finite set \(\mathcal{C}\) of constraints, each of one of the forms_

\[x=1,\quad x+y+z=0,\quad x\times y+1=0,\quad x+f(y)=0, \tag{5}\]

_where \(x\), \(y\) and \(z\) are first-order variable symbols and \(f\) is some function symbol in \(\tau\), determine whether the system of constraints of \(\mathcal{C}\) is satisfiable over \(\mathbb{R}_{\tau}\) using a single variable assignment._

The constraint types of 5 are called _unit_ constraints, _addition_ constraints, _inversion_ constraints and _function_ constraints, respectively.

**Lemma 22**.: _The problem \(\mathrm{ETR}_{\tau}\mathrm{-INV}\mathrm{-FLAT}\) is \(\exists\mathbb{R}_{\tau}\)-complete._

Proof.: We show that the satisfiability problem of the existential theory of the structure \(\mathbb{R}_{\tau}\) is reducible in polynomial time to \(\mathrm{ETR}_{\tau}\mathrm{-INV}\mathrm{-FLAT}\); the opposite direction is clear. Let \(\phi\) be a sentence of the logic \(\exists\mathrm{FO}(\{+,\times,<,=,0,1\}\cup\tau)\). Simplifying all functional subterms as in the proof of Lemma 9 and proceeding as in the proof of Theorem 16 of [5], the satisfiability of \(\phi\) can be reduced in polynomial time to a finite set \(\mathcal{C}^{\prime}\) of constraints of the following forms:

\[x=1,\quad x+y=z,\quad x\times y=1,\quad x=f(y).\]

For every choice of first-order variables \(x\), \(y\) and \(z\), the following observation is true for every variable assignment \(s\):

\[\mathbb{R}_{\tau}\models_{s}x+y=z\iff\mathbb{R}_{\tau}\models_{s}\exists u \exists v(v+v+v=0\wedge z+u+v=0\wedge x+y+u=0).\]
Similarly, for monomial terms \(t\) and \(t^{\prime}\), it holds that

\[\mathbb{R}_{\tau}\models_{s}t=t^{\prime}\iff\mathbb{R}_{\tau}\models_{s}\exists u \exists v(v+v+v=0\wedge t+u+v=0\wedge t^{\prime}+u+v=0).\]

In particular, each of the constraints in \(\mathcal{C}^{\prime}\) can be expressed equivalently using at most a constant number of \(\mathrm{ETR}_{\tau}\)-\(\mathrm{INV}\)-\(\mathrm{FLAT}\) constraints, producing an equivalent system of constraints. 

Depending on the functions in the set \(\tau\), some of the constraints in Definition 21 can be left out without losing \(\exists\mathbb{R}_{\tau}\)-completeness. For instance, the exponential function can be used in order to switch between addition and multiplication in existential formulae.

The proof of the following theorem is based on the neural network construction of [2], in which it was used to obtain the first known version of an \(\exists\mathbb{R}\)-complete NN training problem.

**Theorem 23**.: _Let \(\tau\) be a set of unary real-valued functions. Then the neural network training problem \(\mathrm{NN}_{\tau}\)-\(\mathrm{TRAINING}\) is \(\exists\mathbb{R}_{\tau}\)-complete._

Proof.: By Lemmas 20 and 22 it is enough to show that the problem \(\mathrm{ETR}_{\tau}\)-\(\mathrm{INV}\)-\(\mathrm{FLAT}\) has a polynomial-time reduction to \(\mathrm{NN}_{\tau}\)-\(\mathrm{TRAINING}\). To this end, let \(\mathcal{C}\) be a finite set of \(\mathrm{ETR}_{\tau}\)-\(\mathrm{INV}\)-\(\mathrm{FLAT}\) constraints. We may assume that \(\mathcal{C}\) does not include unsatisfiable constraints of the form \(x\times x+1=0\). Let \(W\) be the set of all variable symbols that appear in any of the constraints of \(\mathcal{C}\). Next, we describe how to construct an \(\mathrm{NN}_{\tau}\)-\(\mathrm{TRAINING}\) instance \((N,A_{E},A_{V},D,c,\prec,\delta)\) in polynomial time so that this instance has a satisfying solution if and only if the system \(\mathcal{C}\) of constraints is satisfiable.

First, let \((A_{V},\prec,\delta):=(\varnothing,=,0)\). In particular, biases are assumed to be \(0\) for all neurons. Let \(c\) be any faithful and non-negative cost function. In the sequel, we will refer to the variables of individual constraints also using indices in the set \(\{1,2,3\}\) according to the list

\[x_{1}=1,\quad x_{1}+x_{2}+x_{3}=0,\quad x_{1}\times x_{2}+1=0,\quad x_{1}+f(x_ {2})=0. \tag{6}\]

Notice that these indices are based on the positions of the variables in the constraints in such a manner that, for example, in a constraint of the form \(x+x+y=0\), indices \(1\) and \(2\) would refer to \(x\) and \(3\) to \(y\). For each \(C\in\mathcal{C}\), let \(l_{C}\) be the appropriate number of these indices for \(C\).

We define the underlying graph \(G\) of the network architecture \(N=(G,\varphi)\), case by case, based on the sets \(W\) and \(\mathcal{C}\) of variables and constraints. The resulting substructure of the network for each constraint type is depicted in Figure 1.

* For each variable symbol \(x\in W\), there is a unique input neuron \(i_{x}\) and an edge to an immediate successor \(j_{x}\). The intended meaning of these two neurons is to encode the value of the variable \(x\) into the edge weight of \((i_{x},j_{x})\). The number of neurons introduced in this step is \(2|W|\).
* For each constraint \(C\in\mathcal{C}\), an output neuron \(o_{C}\) is inserted. In addition, there are unique hidden neurons \(h_{(C,k)}\) and \(q_{(C,k)}\), and a unique input neuron \(p_{(C,k)}\) for each \(k\in\{1,\ldots,l_{C}\}\), and they are incident to the edges of the network as follows: \[(j_{x_{k}},h_{(C,k)}),\quad(h_{(C,k)},o_{C}),\quad(p_{(C,k)},q_{(C,k)})\quad \text{and}\quad(q_{(C,k)},h_{(C,k)}).\] In total, there are at most \(10|\mathcal{C}|\) new neurons introduced in this case. Here, the neurons \(p_{(C,k)}\) and \(q_{(C,k)}\) are intended to cancel out the output value of the neuron \(h_{(C,k)}\) for those data points that in the construction are not intended to directly concern the constraint \(C\) but that still give a non-zero value for the input neuron \(i_{x_{k}}\).
* For each constraint of the form \(x\times y+1=0\), an additional input neuron \(e_{C}\) is added and connected with an edge \((e_{C},j_{y})\) to the neuron \(j_{y}\). For this, at most \(|\mathcal{C}|\) new neurons are introduced.

As the remaining part of the network architecture \(N\), the function \(\varphi\) is selected so that for each neuron \(v\), the activation function \(\varphi_{v}\) is the identity function except for the case that \(v\) is of type \(h_{(C,2)}\) for some function constraint \(C\) of the form \(x_{1}+f(x_{2})=0\); in this case, the selection \(\varphi_{v}:=f\) is used. The set \(A_{E}\) of active edges is defined to be the set of all edges of \(N\) that are either of the form

\[(i_{x},j_{x}),\quad(j_{y},h_{(C,2)})\quad\text{or}\quad(p_{(C^{\prime},k)},q_{ (C^{\prime},k)}),\]
where \(x\) and \(y\) are variables that appear in \(W\), \(C\) is an inversion constraint \(z\times y+1=0\) for some variable \(z\in W\), and \(C^{\prime}\in\mathcal{C}\) is a constraint and \(k\in\{1,\ldots,l_{C^{\prime}}\}\) a corresponding index in the sense of 6. In Figure 1, active edges are drawn using thicker arrows than the other edges of the network.

Recall that all input neurons are either of the form \(i_{x}\), \(p_{(C,k)}\) or \(e_{C}\), and that \(\{o_{C}\mid C\in\mathcal{C}\}\) is the set of all output neurons. Now, let \(D\) consist of the following data points:

* There is a data point \(d_{a}\) in \(D\) that is defined as follows:
* For each variable symbol \(x\in W\) it holds that \(d_{a}(i_{x})=1\).
* For each constraint \(C\) of the form \(x\times y+1=0\) it holds that \(d_{a}(p_{(C,1)})=1\) and \(d_{a}(p_{(C,2)})=1\).
* For every other input neuron \(v\), \(d_{a}(v)=0\).
* For every output neuron \(o_{C}\) corresponding to some unit constraint \(C\in\mathcal{C}\), i.e., \(C\) is \(x=1\) for some \(x\in W\), it holds that \(d_{a}(o_{C})=1\).
* For every other output neuron \(v\), we have \(d_{a}(v)=0\).
* For each constraint \(C\in\mathcal{C}\) of the form \(x\times y+1=0\), two additional data points, \(d_{(C,1)}\) and \(d_{(C,2)}\), are defined in the following steps:
* The data point \(d_{(C,1)}\) maps the tuple \((i_{x},i_{y},e_{C},o_{C})\) of neurons to the tuple \((1,0,1,0)\).
* In addition, \(d_{(C,1)}\) maps to \(1\) all those input neurons of the form \(p_{(C^{\prime},k)}\) for which the number \(k\in\{1,\ldots,l_{C^{\prime}}\}\) is an index for \(x\) in some constraint \(C^{\prime}\neq C\).
* In \(d_{(C,2)}\), the neurons of the tuple \((i_{x},i_{y},e_{C},o_{C})\) are mapped to the values of (\(0,1,0,1\)).
* The data point \(d_{(C,2)}\) has value \(1\) for all input neurons of the form \(p_{(C^{\prime},k)}\) for which \(k\in\{1,2,3\}\) is an index for the variable \(y\) in some \(C^{\prime}\in\mathcal{C}\) such that \(C^{\prime}\neq C\).
* If \(v\) is any other input neuron or output neuron of \(N\), it holds that \(d_{(C,1)}(v)=d_{(C,2)}(v)=0\).

Fig. 1: (a) For a unit constraint \(x=1\), and for every other part of the network, the value assigned to some variable \(x\) is encoded in the weight of the edge from \(i_{x}\) to \(j_{x}\). (b) In the part of the network corresponding to a function constraint \(x+f(y)=0\), the neuron \(h_{(C,2)}\) is activated using the given function \(f\). For every other type of neurons in the network, the identity activation function \(x\mapsto x\) is used. (c) Input neurons \(i_{x}\), \(i_{y}\) and \(i_{z}\), hidden neurons \(j_{x}\), \(j_{y}\), \(j_{z}\) and \(h_{(C,k)}\) for \(k\in\{1,2,3\}\), together with the output neuron \(o_{C}\) enforce an addition constraint \(C\) of type \(x+y+z=0\). For each \(k\in\{1,2,3\}\), the neurons \(p_{(C,k)}\) and \(q_{(C,k)}\) are used to connect the corresponding variable in the constraint with inversion constraints. (d) For an inversion constraint \(C\) of the form \(x\times y+1=0\), an additional input neuron, \(e_{C}\), is introduced. An edge between the hidden levels of the network, from \(j_{y}\) to \(h_{(C,2)}\), is active in the training process. It is intended to carry the negated value of the variable \(x\).
These steps introduce at most \(2|\mathcal{C}|\) data points. Note that in the preceding definition of the data points \(d_{(C,1)}\) and \(d_{(C,2)}\), we use the assumption that \(\mathcal{C}\) does not have constraints of the form \(x\times x+1=0\).

It remains to show that the \(\mathrm{NN}_{\tau}\)-TRAINING instance \((N,A_{E},A_{V},D,c,\prec,\delta)\) has a satisfying solution if and only if the system \(\mathcal{C}\) is satisfiable. For this, first assume that some edge weight function \(w\) is a solution for the training problem. Let variable assignment \(s\) be such that for each variable \(x\in W\) it holds that \(s(x)=w(i_{x},j_{x})\). We show that \(s\) satisfies \(\mathcal{C}\). For this, let \(C\in\mathcal{C}\) be arbitrary.

* If \(C\) is a unit constraint \(x=1\), then by the definition of \(d_{a}\) and the non-negativeness of \(c\), it holds that \(d_{a}(o_{C})=1\). Since \(d_{a}(i_{x})=1\) and \(d_{a}(p_{(C,1)})=0\), we have \(w(i_{x},j_{x})=1\) and so \(s(x)=1\).
* In the case that \(C\) is \(x+y+z=0\), we have \(d_{a}(o_{C})=0\) and \(d_{a}(p_{(C,k)})=0\) for each \(k\in\{1,2,,3\}\). Thus, \(w(i_{x},j_{x})+w(i_{y},j_{y})+w(i_{z},j_{z})=0\) or, equivalently, \(s(x)+s(y)+s(z)=0\).
* If \(C\) is some inversion constraint \(x\times y+1=0\), the definition of the data point \(d_{(C,1)}\) leads to the following observation: \[0 =d_{(C,1)}(o_{C})\] \[=w(i_{x},j_{x})\times d_{(C,1)}(i_{x})+w(j_{y},h_{(C,2)})\times(w (i_{y},j_{y})\times d_{(C,1)}(i_{y})+d_{(C,1)}(e_{C}))\] \[=w(i_{x},j_{x})\times 1+w(j_{y},h_{(C,2)})\times(w(i_{y},j_{y}) \times 0+1)\] \[=w(i_{x},j_{x})+w(j_{y},h_{(C,2)}).\] Similarly, from the definition of \(d_{(C,2)}\) and the non-negativeness of the cost function \(c\), we get \[1 =d_{(C,2)}(o_{C})\] \[=w(i_{x},j_{x})\times d_{(C,2)}(i_{x})+w(j_{y},h_{(C,2)})\times(w (i_{y},j_{y})\times d_{(C,2)}(i_{y})+d_{(C,2)}(e_{C}))\] \[=w(i_{x},j_{x})\times 0+w(j_{y},h_{(C,2)})\times(w(i_{y},j_{y}) \times 1+0)\] \[=w(j_{y},h_{(C,2)})\times w(i_{y},j_{y}).\] Thus it holds that \(w(j_{y},h_{(C,2)})=-w(i_{x},j_{x})\), and both of the claims \(w(i_{x},j_{x})\times w(i_{y},j_{y})+1=0\) and \(s(x)\times s(y)+1=0\) are true.
* If \(C\) is \(x+f(y)=0\), we get \(d_{a}(o_{C})=1\), \(d_{a}(i_{x})=d_{a}(i_{y})=1\) and \(d_{a}(p_{(C,k)})=0\) for \(k\in\{1,2\}\). From these it follows that \(w(i_{x},j_{x})+f(w(i_{y},j_{y}))=0\) and \(s(x)+f(s(y))=0\).

Therefore, the preceding assignment \(s\) satisfies all the constraints that belong to \(\mathcal{C}\).

For the other direction, let \(s\) be some assignment over the variables in \(W\) such that all constraints of \(\mathcal{C}\) are satisfied. Let \(w\) be an edge weight function defined on the set \(A_{E}\) as follows:

* For each variable symbol \(x\in W\), it holds that \(w(i_{x},j_{x})=s(x)\).
* For each constraint \(C\) of the form \(x\times y+1=0\), weight value \(-s(x)\) is assigned to the edge \((j_{y},h_{(C,2)})\). The edge \((p_{(C,2)},q_{(C,2)})\) is mapped to the value \(s(x)\times s(y)\).
* Every remaining \((p_{(C,k)},q_{(C,k)})\in A_{E}\) is given the weight value \(-s(x_{k})\), where \(x_{k}\) is such that it matches with the index \(k\in\{1,2,3\}\) of constraint \(C\) in the sense of 6.

Let \(g\) be the neural function of the neural network \((N,w,\varnothing)\). It remains to show that for every output neuron \(v\) and for every data point \(d\in D\) it holds that \(g_{d}(v)=d(v)\). Recall that for each output neuron \(v\) there is a unique \(C\in\mathcal{C}\) such that \(v=o_{C}\).

We will first check the case of the data point \(d_{a}\). If \(C\in\mathcal{C}\) is not an inversion constraint, then for all indices \(k\in\{1,\ldots,l_{C}\}\) as in 6 it holds that

\[g_{d_{a}}(h_{(C,k)})=w(i_{x_{k}},j_{x_{k}})\times d_{a}(i_{x_{k}})+w(p_{(C,k)},q_{(C,k)})\times d_{a}(p_{(C,k)})=s(x_{k})\times 1+0=s(x_{k}).\]

From this it follows that if \(C\) is a unit constraint, then \(g_{d_{a}}(o_{C})=s(x_{1})=1\), and if \(C\) is an addition constraint, then \(g_{d_{a}}(o_{C})=s(x_{1})+s(x_{2})+s(x_{3})=0\), and furthermore, if \(C\) is a function constraint of the form \(x_{1}+f(x_{2})=0\), then \(g_{d_{a}}(o_{C})=s(x_{1})+f(x_{2})=0\). That is, for each of the preceding cases, it holds that \(g_{d_{a}}(o_{C})=d_{a}(o_{C})\). On the other hand, if \(C\) is an inversion constraint \(x\times y+1=0\), then

\[g_{d_{a}}(h_{(C,1)}) =w(i_{x},j_{x})\times d_{a}(i_{x})+w(p_{(C,1)},q_{(C,1)})\times d_ {a}(p_{(C,1)})\] \[=s(x)\times 1+(-s(x))\times 1=0,\]
\[g_{d_{a}}(h_{(C,2)}) =\left(w(j_{y},h_{(C,2)})\times(w(i_{y},j_{y})\times d_{a}(i_{y})+d_ {a}(e_{C}))\right)+w(p_{(C,2)},q_{(C,2)})\times d_{a}(p_{(C,2)})\] \[=(-s(x)\times(s(y)\times 1+0)+(s(x)\times s(y))\times 1)=0.\]

Thus, it holds that \(g_{d_{a}}(o_{C})=0=d_{a}(o_{C})\).

For the remaining cases, let \(C\) be a fixed inversion constraint \(x\times y+1=0\). We will go through the data points \(d_{(C,1)}\) and \(d_{(C,2)}\) simultaneously. First, let \(d\in\{d_{(C,1)},d_{(C,2)}\}\) and \(C^{\prime}\in\mathcal{C}\setminus\{C\}\) be arbitrary. Then, for each \(k\in\{1,\ldots,l_{C^{\prime}}\}\) it holds that \(h_{(C^{\prime},k)}=0\), namely, either it holds that both \(d(x_{k})=0\) and \(d(p_{(C^{\prime},k)})=0\) are true, or that both \(d(x_{k})=1\) and \(d(p_{(C^{\prime},k)})=1\) are true. Therefore, we obtain the result \(g(o_{C^{\prime}})=0=d(o_{C^{\prime}})\).

For the inversion constraint \(C\) and neuron \(h_{(C,1)}\), for each \(d\in\{d_{(C,1)},d_{(C,2)}\}\) it holds that

\[g_{d}(h_{(C,1)})=w(i_{x},j_{x})\times d(i_{x})+w(p_{(C,1)},q_{(C,1)})\times d( p_{(C,1)})=s(x)\times d(i_{x})+0.\]

From this we get \(g_{d_{(C,1)}}(h_{(C,1)})=s(x)\) and \(g_{d_{(C,2)}}(h_{(C,1)})=0\). On the other hand, for the hidden neuron \(h_{(C,2)}\) and \(d\in\{d_{(C,1)},d_{(C,2)}\}\) we have

\[g_{d}(h_{(C,2)}) =\left(w(j_{y},h_{(C,2)})\times(w(i_{y},j_{y})\times d(i_{y})+d(e _{C}))\right)+w(p_{(C,2)},q_{(C,2)})\times d(p_{(C,2)})\] \[=-s(x)\times(s(y)\times d(i_{y})+d(e_{C}))+0\] \[=-s(x)\times s(y)\times d(i_{y})-s(x)\times d(e_{C}).\]

Then, \(g_{d_{(C,1)}}(o_{C})=s(x)-s(x)=0\) and \(g_{d_{(C,2)}}(o_{C})=0-s(x)\times s(y)=1\), from which it follows that \(g_{d}(o_{C})=d(o_{C})\) for each \(d\in\{d_{(C,1)},d_{(C,2)}\}\). This concludes the proof the theorem. 

In the previous proof, it is enough to have a single unit constraint in the set \(\mathcal{C}\). Addition constraints can be combined under a unified output neuron, if multiple data points are allowed in order to take separate addition constraints into account. Here, we can use the fact that the indices of the input neurons \(p_{(C,k)}\) are based on the numbers \(k\) instead of the corresponding variable \(x_{k}\); multiple occurrences of a variable in an unified addition constraint can be treated separately. Furthermore, as noted in [2], it can be assumed that each variable is incident to at most one inversion constraint. In this manner, only a constant number of data points is needed for all the inversion constraints that are in \(\mathcal{C}\).

As a reminder, the sigmoid activation function \(\sigma\colon\mathbb{R}\to\mathbb{R}\) is defined as \(\sigma(x)=1/(1+\exp(-x))\) for each \(x\in\mathbb{R}\). Using the previous theorem, we can now connect sigmoidal NN training with exponential real arithmetic.

**Corollary 24**.: \(\mathrm{NN}_{\sigma}\)_-\(\mathrm{TRAINING}\) is \(\exists\mathbb{R}_{\mathrm{exp}}\)-complete._

Proof.: By Theorem 23, \(\mathrm{NN}_{\sigma}\)-\(\mathrm{TRAINING}\) is \(\exists\mathbb{R}_{\sigma}\)-complete. Furthermore, the sigmoid activation function is existentially definable in \(\exists\mathbb{R}_{\mathrm{exp}}\) and similarly the exponential function is existentially definable in \(\exists\mathbb{R}_{\sigma}\). Thus it follows that \(\mathrm{NN}_{\sigma}\)-\(\mathrm{TRAINING}\) is \(\exists\mathbb{R}_{\mathrm{exp}}\)-complete. 

**Corollary 25**.: \(\mathrm{NN}_{\mathrm{sin}}\)_-\(\mathrm{TRAINING}\) is undecidable but in \(\Sigma^{0}_{3}\)._

Proof.: The claim follows from Theorems 13 and 23. 

Similar to the proof of Theorem 13, undecidability can be generalized to other functions having some form of periodic nature that can be used to define natural numbers with existential formulae.

## V Conclusion

We have studied the complexity of the neural network training problem. We showed that the training problem corresponding to sets \(\tau\) of activation functions are complete for the complexity classes \(\exists\mathbb{R}_{\tau}\) that extend the reals with the corresponding functions. We also showed that for sets \(\tau\) of effectively continuous functions, these problems reside in \(\Sigma^{0}_{3}\), and even in \(\Sigma^{0}_{1}\) when defined without the equality sign and negation. The following topics deserve further study:
* Could our \(\Sigma^{0}_{1}\) upper bound for the identity-free existential theory of the reals with effectively continuous functions be improved or extended. Note that for decidability of the exponential arithmetic it would suffice to establish an \(\Sigma^{0}_{1}\)-upper bound for its existential fragment [9, 10].
* The proof of our main completeness result (Theorem 23) is based on the use of adversarial network architectures (see [3]). It is an open question whether our result holds if the NN architecture is assumed to be a fully connected graph with all edge weights and neuron biases being active, or when restricted to the case that all neurons use the same activation function.
* For many non-negative cost functions it is known that the computational complexity of an exact total training error \(0\) is at most the complexity of an error bounded by some positive value (allowing equality), whereas an upper bound given by the strict order relation \(<\) seems to be independent of the two. Recall that these cases correspond to our upper bounds \(\Sigma^{0}_{3}\) and \(\Sigma^{0}_{1}\), and that in the case of the exponential function, they are also connected to Tarski's exponential function problem.
* Another topic to study are training problems with limited precision. For example, does the complexity of the training problem decrease for some activation functions if edge weights and biases are assumed to be rational?
