Existential Theory of the Reals, Neural Networks, and Tarski's Exponential Function Problem

In this dissertation we study problems related to variations of the Existential Theory of the Reals. In th first chapter we study the approximated ETR and we prove that a certain problem on the approximate trainability of neural networks is poly-time bireducible with ETR. This is a generalisation of a result on exact trainability due to Abrahamsen, Kleist and Miltzow. In the second chapter we study the arithmetical complexity of ETR with a finite set of effectively continuous functions. We improve a previous bound (due to Hankala, Hannula, Kontinen and Virtema) to Sigma^0_2 and show that the bound is sharp. Moreover, we study the relation between the complexity of the exact and the approximate versions and we show that these may be rather independent. In the third chapter we apply the result of the second chapter to the problem of whether the theory of the reals with the exponential function is decidable. We show that ETR_exp is Delta^0_2. By results of Macintyre and Wilkie, further improving this bound to Sigma^0_1 or Pi^0_1 would be equivalent to solving this longstanding problem. We also provide some conditional results depending on whether R_exp is effectively exponentially bounded. If it is, then ETR_exp is omega-recursively enumerable (a bound lower than Delta^0_2 but still greater thatn Sigma^0_1 and Pi^0_1).