Characterizing time computational complexity classes with polynomial differential equations

Abstract

In this paper we show that several classes of languages from computational complexity theory, such as $EXPTIME$ , can be characterized in a continuous manner by using only polynomial differential equations. This characterization applies not only to languages, but also to classes of functions, such as the classes defining the Grzegorczyk hierarchy, which implies an analog characterization of the class of elementary computable functions and the class of primitive recursive functions.

Keywords

Analog computation computation with polynomial ordinary differential equations EXPTIME Grzegorczyk hierarchy

1. Introduction

In the papers [3,5] the authors presented a characterization of the computational complexity class P by using polynomial ordinary differential equations (ODEs). This characterization is purely continuous and hence establishes a continuous characterization of the class P typically associated to discrete models of computation such as the standard Turing machine. This result does not use any reference to a (discrete) machine and hence provides an implicit characterization of P.

Interestingly, this result also provides a form of equivalence between analog and digital models of computations, both at a computability level and at a complexity level. This stems from the fact that the class of functions which can be computed with these polynomial ODEs corresponds to an analog model of computation, Shannon’s General Purpose Analog Computer (GPAC) [18,24], which is intended to model differential analyzers, which were the analog computers in use before the advent of the digital computer [11]. It was shown that the GPAC and Turing based models of computation, including computable analysis, are computationally equivalent at a computability level [1,2,17] and at a complexity level, when we consider functions computable in polynomial time [3,5].

A natural question to ask is whether the above continuous characterization of polynomial time computability via ODEs extends to other computational complexity classes. This is not obvious from [3,5], since these papers are technically dense, and rely on other papers such as [4] which are tailored to the polynomial case. Polynomials have many desirable properties which are unfortunately not shared by some other types of functions. For example, the class of polynomials is closed under composition, while the class of exponential functions is not, which may (and will, as we will see later) pose problems when trying to characterize the class $EXPTIME$ with polynomial ODEs.

The purpose of the present paper is to understand how the results of [3,5] can be extended to other complexity classes such as $EXPTIME$ . For this purpose we will first focus on classes of functions, such as the class $FEXPTIME$ of functions computable in exponential time and we will show how this class can be characterized using ODEs. Other classes of functions that we will characterize include all the classes defining the Grzegorczyk hierarchy and, in particular, the elementary computable functions and the primitive recursive functions. We note that some similar results were proved in [7,8,12–14]. However the approach used in these papers differs from the current one in the sense that they use real recursive functions which use partial differential equations, among other differences.

As we will see in the following sections, we will be able to reuse some results from previous papers such as [3–5], while other results will have to be adapted. As we mentioned, the papers [3,5] are technically dense and often not easy to follow. In this paper we also intend to provide a “road map” to the results of [5], which might help simplify their understanding, by clearly separating the “core” results of the papers [3,5], from their “non-core” counterparts.

To obtain our results, first we characterize the class $FEXPTIME$ of discrete functions computable in exponential time using ODEs (Theorem 29). The idea behind this result is to use the encoding provided by [5] of the transition function of a given Turing machine as a solution of a polynomial ODE and iterate it with polynomial ODEs. The challenge will be in making all this work using resources which are exponentially bounded on the input size, and not double exponentially bounded as a more direct approach similar to that of [5] would yield. This will provide the elements necessary to understand how to extend this result to other discrete complexity classes of functions (Theorem 35). As an example of this extension we will show how it is possible to apply Theorem 35 to the whole Grzegorczyk hierarchy, obtaining in this way a completely analog characterization of the Grzegorczyk hierarchy by using ODEs and, in particular, of the class of elementary functions and the class of primitive recursive functions. In the case of the Grzegorczyk hierarchy it will not be enough to apply Theorem 35, since for the complexity time bound we need to extend discrete time bounds (i.e. defined over $N$ ) classes to real functions. While this is trivially done for polynomial or exponential functions, this is not straightforward for classes such as the Grzegorczyk hierarchy. We present a solution to this problem by constructing appropriate bounds using ODEs which perform several operations like iteration, etc.

Finally, combining our approach with that of [5] we show that we can characterize classes of languages instead of classes of functions, and this will be concretely implemented for describing the complexity class $EXPTIME$ using differential equations.

The outline of the paper is as follows. On Section 2 we review some basic notions about computability with ODEs. In Section 3 we briefly review the results of [5] which show how one can characterize the class $FP$ of discrete functions computable in polynomial time in terms of differential equations. In Section 4 we discuss the problems of extending the results from [5] to the exponential case. Then we present a solution to solve these problems and we use it to characterize the class $FEXPTIME$ using differential equations. In Section 5 we discuss the conditions that allow us to repeat what was done with the exponential case for higher complexity classes. In Section 6 we show that, analogously to what was done in [5] for the polynomial case, the analog characterization of the class $FEXPTIME$ and of higher complexity classes via ODEs can be done by considering just one complexity parameter, the length of the solution curve of the ODE. In Section 7 we apply the generalization to the case of the Grzegorczyk hierarchy. To do so, we develop a technique to obtain by means of system of differential equations the correct set of boundaries for each level of the hierarchy. In Section 8 we show how the class $EXPTIME$ can be characterized using differential equations. Finally, in Section 9 we present the conclusions and discuss some open problems.

2. Computing with polynomial differential equations

As we have mentioned, polynomial ODEs correspond to Shannon’s GPAC. More concretely a function is generable if it is the solution of some polynomial initial-value problem (PIVP) defined with a polynomial ODE. We call such functions PIVP functions. Note that in this sense a generable function is a one-variable function. The notion of generable function can be extended to multivariate functions as in [5]. Moreover, by restricting the coefficients of the polynomials used to define the ODE, we can also restrict the class of functions computed by this model. This is usually assumed to avoid potential problems where the ODE gains unreasonable computational power by using the coefficients of the polynomials as oracles. More concretely, let $K$ be some field with the property that $Q \subseteq K$ and recall that $J_{f} (x)$ denotes the Jacobian of f at point x.

Definition 1.
Let $D \subseteq R^{k}$ be a domain (i.e. an open and connected set) and $f : D \to R^{l}$ . We say that $f \in {GVAL}_{K}$ if and only if there is an initial-value problem (IVP) $\begin{matrix} (1) & J_{y} (x) = p (y), y (x_{0}) = y_{0} \end{matrix}$ with solution y such that $f (x) = (y_{1} (x), \dots, y_{l} (x))$ , where p is some $n \times k$ matrix, $n ⩾ l$ , with the property that each entry of p is a polynomial with coefficients in $K$ , and $x_{0} \in K^{k} \cap D$ , $y_{0} \in K^{l}$ .

We remark that, for the class ${GVAL}_{K}$ , a function $f \in {GVAL}_{K}$ corresponds to (components of) a solution y of a differential equation. Note also that it can be shown that each IVP of the form of (1) has one and only one solution [6]. Moreover the one-variable functions of ${GVAL}_{R}$ are exactly the PIVP functions, which are formed by components of some polynomial initial value-problem $y^{'} = p (y)$ , $y (t_{0}) = y_{0}$ , where $y : {R \to R}^{n}$ for some $n ⩾ 1$ . We can also establish complexity measures for functions in ${GVAL}_{K}$ by putting a bound on the growth of functions. Throughout this paper, unless other specified, $‖ \cdot ‖$ denotes the sup norm in $R^{k}$ , i.e. if $x \in R^{k}$ , then $‖ x ‖ = {max}_{1 ⩽ i ⩽ k} | x_{i} |$ , where $x = (x_{1}, \dots, x_{k})$ .
Definition 2.
We say that $f \in {GVAL}_{K} (sp)$ , where $sp : R \to R$ , if $f \in {GVAL}_{K}$ and there is some solution y of (1) for which one has: (i) $f (x) = (y_{1} (x), \dots, y_{l} (x))$ and (ii) $‖ y (x) ‖ ⩽ sp (‖ x ‖)$ .

If $K ⫋ R$ , it is often convenient to ensure that $K$ is closed under the application of functions in ${GVAL}_{K}$ . This is the case for generable fields. A detailed treatment of generable fields and their properties can be found in [6]. As an example, $R_{P}$ , the field of real numbers that are polynomial-time computable in the sense of computable analysis, is a generable field. More specifically, the only property of these fields that is relevant for this paper is the following: a field $K$ is generable if $Q \subseteq K$ and $f (α) \in K^{l}$ for any $(f : R^{k} {\to R}^{l}) \in {GVAL}_{K}$ and any $α \in K^{l}$ . It can be shown (see [6, Section 6]) that there exists a minimal generable field, denoted by $R_{G}$ (the field is minimal in the sense that if $K$ is another generable field, then $R_{G} \subseteq K$ ), and that any element of $R_{G}$ is computable in polynomial time. From now on we will always assume that ${K = R}_{G}$ and denote ${GVAL}_{R_{G}}$ by $GVAL$ for simplicity.

We note that several standard functions from analysis such as the trigonometric functions, polynomials, the exponential and logarithmic functions all belong to $GVAL$ (i.e. they are generable). This class also has important stability properties, since it is closed under addition, subtraction, product, composition, and ODE solving [6]. Specifically, the fact that trigonometric functions belong to $GVAL$ and that this class is closed under composition will be essential for proving some of our results in later sections.

In what follows, it will be convenient to consider generable functions which are bounded by a polynomial. Definition 3.
We say that $f \in GPVAL$ if and only if $f \in GVAL (p)$ for some polynomial p.
However, functions such as the Gamma function or the Riemann Zeta function are not generable. The problem does not arise from the model of computation but from the notion of computation used, where real-time computation is used e.g. in the one-variable case. For example, when computing sin, we immediately get $sin (t)$ as soon as we feed the input t to the GPAC computing sin. This is in contrast to other models of computation (e.g. Turing machines), where some time is allowed for the computation since the moment the input is provided to the model up to the moment in which an answer is provided. For this reason, the GPAC model was extended in [16] to more closely match this notion of computation. The idea is to use a kind of limit computation (see Fig. 1), where at each moment the computation provides an approximation of the correct answer with an error which goes to 0 as computation time goes to infinity, matching what is done in computable analysis [21,25]. Contrarily to what happens for ${GVAL}_{K}$ , in this setting a function f is not longer (formed by components of) a solution y of a differential equation. Instead $f (x)$ is obtained as the limit ${lim}_{t \to + \infty y (t)}$ of a solution y of an ODE, with initial condition $y (0)$ dependent in a “simple manner” of the value x.

Figure 1.
Computing the function f with an ODE.
Definition 4 (ATS).

Let $f \subseteq R^{n} \to R^{m}$ . We say that $f \in ATS (Π, Υ)$ , where $Π, Υ : R^{2} \to R$ if and only if there exist multivariate polynomials p, q with coefficients in $R_{G}$ such that for any $x \in dom (f)$ , there exists (a unique) $y : R \to R^{d}$ satisfying for all $t ⩾ 0$ :

$y (0) = q (x)$ and $y^{'} (t) = p (y (t))$ ;

$\forall μ > 0$ if $t ⩾ Π (‖ x ‖, μ)$ then $‖ (y_{1} (t), \dots, y_{m} (t)) - f (x) ‖ ⩽ e^{- μ}$ ;

$‖ y (t) ‖ ⩽ Υ (‖ x ‖, t)$ .

The function Π is usually referred to as the time bound, and the function Υ as the space bound (the notation $ATS$ is an abbreviation for “analog time space”). Note that, differently to what happens with Turing machines in discrete complexity theory, here space and time boundaries are independent and unrelated one to another. In the paper [4] the focus was on the class $ATSP$ of functions computed with a polynomial time and space bound. This class will also be important in the present paper.

Definition 5.
Let $f \subseteq R^{n} \to R^{m}$ . We say that $f \in ATSP$ if $f \in ATS (Π, Υ)$ for some polynomials Π and Υ.

When using the class $ATSP$ in proofs, it is often useful to use one of the several equivalent definitions of $ATSP$ , which were proved in [4]. In particular, the following definition will be helpful (where the notation $C^{0} (R, R^{n})$ stands for the set of continuous functions from $R$ to $R^{n}$ ), where $R_{+} = [0, + \infty [$ :
Proposition 6.
Let $f \subseteq R^{n} \to R^{m}$ . Then $f \in ATSP$ if and only if there exist $δ ⩾ 0$ , $d \in N$ , multivariate polynomials p with coefficients in $R_{G}$ , $y_{0} \in R_{G}^{d}$ , and polynomials $Π, Υ, Λ : R_{+}^{2} \to R_{+}$ such that for any $x \in C^{0} (R, R^{n})$ , there exists (a unique) $y : R \to R^{d}$ satisfying for all $t ⩾ 0$ :
$y (0) = y_{0}$ and $y^{'} (t) = p (y (t), x (t))$ ;

$‖ y (t) ‖ ⩽ Υ ({sup}_{δ} ‖ x ‖ (t), t)$ , where ${sup}_{δ} f (t) = {sup}_{u \in [t - δ, t] \cap [0, + \infty [} f (u)$ ;

For any $I = [a, b] \subseteq R$ with $a ⩾ 0$ , if there exist $\bar{x} \in dom (f)$ and $μ ⩾ 0$ such that for all $t \in I$ we have $‖ x (t) - \bar{x} ‖ ⩽ e^{- Λ (‖ x ‖, μ)}$ , then $‖ (y_{1} (t), \dots, y_{m} (t)) - f (\bar{x}) ‖ ⩽ e^{- μ}$ whenever $a + Π (‖ \bar{x} ‖, μ) ⩽ u ⩽ b$ .

The first condition of Proposition 6 defines the ODEs generating the function f, the second condition ensures that the norm of the solution of this system satisfies a polynomial bound, while the third condition takes care of the convergence of such solution: specifically, this solution y converges to the correct value of the function $f (\bar{x})$ only if there exists an interval where the value of a continuous function x is near the point $\bar{x}$ . If this happens, then, after a delay given by a polynomial boundary Π, we get a convergence similar to the one of the original definition of $ATSP$ . The proposition above is particularly important because, allowing possible fluctuations for the input x, it provides a strong robustness property to the functions in $ATSP$ that plays a determinant role on ensuring closure by composition for the class.

The class $ATSP$ has several nice properties, which were proved in [5]. Next we provide a summary of the most relevant results.
Proposition 7 (ATSP closure by arithmetic operations).

If $g, f \in ATSP$ , then $g + f, g - f, g \cdot f \in ATSP$ , with the obvious restrictions on the domains of definition.

Proposition 8 (ATSP modulus of continuity).

If $f \in ATSP$ , then f admits a polynomial modulus of continuity: there exists a polynomial $Ω : R^{2} \to R$ such that for all $x, y \in dom (f)$ and $μ ⩾ 0$ , $\begin{matrix} ‖ x - y ‖ ⩽ e^{- Ω (‖ x ‖, μ)} \Rightarrow ‖ f (x) - f (y) ‖ ⩽ e^{- μ} . \end{matrix}$ In particular, f is continuous.

One the most important properties of $ATSP$ is closure under composition.

Theorem 9 (ATSP closure by composition).

If $f, g \in ATSP$ , and $f (dom (f)) \subseteq dom (g)$ , then $g \circ f \in ATSP$ .

Since the class $ATSP$ is, in a sense, an extension of the class $GPVAL$ , one should expect that the latter is included in the former. This is true in a certain type of domain, which is enough for our purposes:

Definition 10.
A set X is called a star domain if there exists $x_{0} \in X$ such that for all $x \in X$ the line segment from $x_{0}$ to x is in X. Such an $x_{0}$ is called a vantage point.

The following theorem is from [5].
Theorem 11.
If $f \in GPVAL$ has a star domain with a vantage point in $R_{G}$ then $f \in ATSP$ .

One key element to extend the polynomial characterization of P and $FP$ given in [4] to higher complexity classes was to understand which ones of the above properties could be maintained for the general case of Definition 4 independently from the functions chosen to play the role of space and time boundaries. Indeed, some proofs of the properties listed above explicitly make use of properties of polynomials, and exploit the equivalence between $ATSP$ and other analog classes such as the one of Definition 6, that does not apply for the class with generic boundaries. More importantly, it is essential to identify which of the above properties are necessary for the whole construction to hold and lead to the desired equivalence. As we will show, the fundamental properties in this sense are closure under arithmetic operations and closure under composition. Therefore, our modification of the polynomial construction is designed with the intent of enabling these two closure properties for classes of the type of Definition 4, while at the same time allowing some freedom on the choice of the time and space boundaries.
3. Computing discrete functions: The polynomial time case

In this section we review several useful results from [5]. In particular we will see how we can code the transition function of a Turing machine (TM for short) into a function in $ATSP$ and how we can iterate it a polynomial number of times, again using a function in $ATSP$ . This will imply that any function $f : Γ^{*} \to Γ^{*}$ computable in polynomial time, where Γ is a finite alphabet, will belong to $ATSP$ in a certain sense. Namely, the notion of emulable function will have to be introduced to be able to go from $Γ^{*}$ to $R^{k}$ , in a way which is similar to what is done when using the representation approach [10,25] in computable analysis. All these notions and ideas will be helpful later when tackling the exponential time case.

3.1. Simulating Turing machines

In this section we will encode the configuration of a Turing machine M as an element of $R^{4}$ and we will build a corresponding transition function $f_{M} : R^{4} \to R^{4}$ . This transition function is built by composing some basic functions, which can be seen as “bricks” to build more complex functions with a desired behavior. Here we present a selection of those function which will be useful on what follows.

Proposition 12.
Let $G \subseteq R_{G}^{d} \subseteq R^{d}$ be a finite subset and $f : G \to R_{G} \subseteq R$ be a function. Then there exists a function $L_{f} \in ATSP$ (Lagrange polynomial), $L_{f} : R^{d} \to R$ , with the property that $L_{f ↾ G} = f$ , where $L_{f ↾ G}$ denotes the restriction of $L_{f}$ to G. In other words, there exists a function $L_{f} \in ATSP$ which extends G to the whole real domain.
Proposition 13.
The real functions $x \to | x |, max, min$ all belong to $ATSP$ .

Other two crucial functions are $lxh$ and $hxl$ that allow to smoothly approximate a step function in a continuous manner. Their graph is depicted in Fig. 2.

Figure 2.
The graphs of functions ${hxl}_{[a, b]}$ (in blue) and ${lxh}_{[a, b]}$ (in red) having last argument x.
Proposition 14 (Low-X-High and High-X-Low).

For every $I = [a, b]$ , $a, b \in R_{G}$ there exist two real functions ${lxh}_{I}, {hxl}_{I} \in ATSP$ such that for any $μ > 0$ and $x, t \in R$ one has:

${lxh}_{I}$ is of the form ${lxh}_{I} (t, μ, x) = ϕ_{1} (t, μ, x) x$ , where $ϕ_{1} (t, μ, x) \in ATSP$ and $0 < ϕ_{1} (t, μ, x) < 1$ ;

${hxl}_{I}$ is of the form ${hxl}_{I} (t, μ, x) = ϕ_{2} (t, μ, x) x$ , where $ϕ_{2} (t, μ, x) \in ATSP$ and $0 < ϕ_{2} (t, μ, x) < 1$ ;

If $t ⩽ a$ , then $| {lxh}_{I} (t, μ, x) | ⩽ e^{- μ}$ and $| x - {hxl}_{I} (t, μ, x) | ⩽ e^{- μ}$ ;

If $t ⩾ b$ , then $| x - {lxh}_{I} (t, μ, x) | ⩽ e^{- μ}$ and $| {hxl}_{I} (t, μ, x) | ⩽ e^{- μ}$ ;

In all cases, $| {lxh}_{I} (t, μ, x) | ⩽ | x |$ and $| {hxl}_{I} (t, μ, x) | ⩽ | x |$ .

Before showing how a configuration can be encoded into an element of $R^{4}$ and how the transition function of a Turing machine M can be encoded as a function $f_{M} : R^{4} \to R^{4}$ , we present the notion of Turing machine that we will use on what follows.

Definition 15 (Turing Machine).

A Turing Machine is a tuple $M = (Q, Σ, Γ, b, δ, q_{0}, q_{\infty})$ , where $Q = {0, \dots, m}$ are the states of the machine, $Σ = {s_{0}, \dots, s_{k - 2}}$ is the tape alphabet and $b = s_{0}$ is the blank symbol, $Γ \subseteq Σ - b$ is the input alphabet, $q_{0} \in Q$ is the initial state, $q_{\infty} \in Q$ is the halting state, and $δ : Q \times Σ \to Q \times Σ \times {L, S, R}$ is the transition function with $L = - 1$ , $S = 0$ , $R = 1$ . We write $δ_{1}$ , $δ_{2}$ , $δ_{3}$ as the components of δ. That is $δ (q, σ) = (δ_{1} (q, σ), δ_{2} (q, σ), δ_{3} (q, σ))$ , where $δ_{1}$ is the new state, $δ_{2}$ the new symbol, and $δ_{3}$ the head move direction. We require that $δ (q_{\infty}, σ) = (q_{\infty}, σ, S)$ .

Note that each symbol $s_{i}$ from Σ can be associated uniquely to the natural number $i \in N$ without any danger of confusion. Hence, in what follows, we will assume that $Σ = {0, \dots, k - 2}$ , without making an explicit reference to the correspondence $s_{i} \mapsto i$ , in order the simplify the notation. We also note that we assume that Σ has $k - 1$ symbols and not k symbols. As indicated in [5, Remark 36] this assumption is important to obtain the continuous (real) map of [5] which simulates the transition function of a Turing using the encoding of configurations of Definition 17. Other continuous transition functions exist (see e.g. [17]) where this requirement is not needed, but they are “less efficient” and not suitable enough for complexity results.

Definition 16 (Configuration).

A configuration for a Turing Machine M is a tuple $c = (x, σ, y, q)$ , where $x \in Σ^{*}$ is the part of the tape at the left of the head, $y \in Σ^{*}$ is the part at the right, $σ \in Σ$ is the symbol under the head, and $q \in Q$ is the current state. More precisely, $x_{1}$ is the symbol immediately at the left of the head and $y_{1}$ is the symbol immediately at the right. $\begin{matrix} \dots 0 0 0 x_{n} x_{n - 1} \dots x_{2} x_{1} σ y_{1} y_{2} \dots y_{l} 0 0 0 \dots \end{matrix}$ The set of configurations of M is denoted as $C_{M}$ . For an input word $w \in Σ^{*}$ the initial configuration is defined by $c_{0} (w) = (λ, b, w, q_{0})$ . Instead, if at the end of the computation the tape contain the word $w \in Σ^{*}$ , then the final configuration is defined by $c_{\infty} (w) = (λ, b, w, q_{\infty})$ , where λ is the empty word.

We now show how a configuration can be encoded as an element of $R^{4}$ .

Definition 17.
Let $c = (x, σ, y, q)$ be a configuration of a Turing machine M with an alphabet $Σ = {0, \dots, k - 2}$ . Then the real encoding of c is defined as $⟨ c ⟩ = (0 . x, σ, 0 . y, q) \in Q \times Σ \times Q \times Q$ where $0 . x = x_{1} k^{- 1} + x_{2} k^{- 2} + \dots + x_{| x |} k^{| x |} \in Q$ and similarly for $0 . y \in Q$ .

Let M also denote the transition function of the Turing machine M, i.e. if c is a configuration, then $M (c)$ denotes the configuration which follows from c after one step of the computation of the TM M.
Theorem 18 ([5]).

Let M be a Turing machine with an alphabet $Σ = {0, \dots, k - 2}$ . Then there is a function $\overline{M} : R^{5} \to R^{4} \in ATSP$ with the property that if c is a configuration of M and $μ > 0$ , then for any $\tilde{c} \in R^{4}$ one has $\begin{matrix} ‖ ⟨ c ⟩ - \tilde{c} ‖ ⩽ \frac{1}{2 k^{2}} - e^{- μ} ⟹ ‖ \overline{M} (\tilde{c}, μ) - ⟨ M (c) ⟩ ‖ ⩽ k ‖ ⟨ c ⟩ - \tilde{c} ‖ . \end{matrix}$

To simulate the computation of a Turing machine M over the real numbers, we need not only to be able to code the transition function of M as a function over the reals, but also to iterate this function over the set of (the coding of) its configurations $C_{M}$ . Since we are not using exact quantities, to be useful, the iteration also has to work on the set of elements of $R^{4}$ “close enough” to $C_{M}$ . This type of iteration can be performed for an arbitrary number of times (see e.g. [17]), but at a too high cost in terms of complexity (resources). Since here we want an “efficient” simulation of the Turing machine (for example we want to simulate polynomially many steps of a TM with a function in $ATSP$ , which uses polynomial time and space, and not with a function which uses e.g. exponential space as in [17]), we need a more refined approach.

The following theorem is from [5] and shows that a function f in $ATSP$ which satisfies certain conditions (the transition function $\overline{M}$ of Theorem 18 satisfies those conditions) can be iterated a polynomial number of times with a function also in ASTP.

Theorem 19 ([5], Polynomial iteration of a function in ATSP).

Let $f : R^{m} \to R^{m} \in ATSP$ , $η \in [0, \frac{1}{2} [$ and assume that there exists a family of subsets $I_{n} \subseteq I$ , $n \in N$ , and polynomials $Ω : R \to R$ , $Π : R^{2} \to R$ such that for all $n \in N$ :

$I_{n + 1} \subseteq I_{n}$ and $f (I_{n + 1}) \subseteq I_{n}$ ;

For all $x \in I_{n}$ , $‖ f^{[n]} (x) ‖ ⩽ Π (‖ x ‖, n)$ ;

For all $x \in I_{n}$ , $y \in R^{m}$ , $μ ⩾ 0$ , if $‖ x - y ‖ ⩽ e^{- Ω (‖ x ‖) - μ}$ then $y \in I$ and $‖ f (x) - f (y) ‖ ⩽ e^{- μ}$ .

Let $f_{η}^{*} (x, u) = f^{[n]} (x)$ for $x \in I_{n}$ and $u \in [n - η, n + η]$ , where $n \in N$ . Then, $f_{η}^{*} \in ATSP$ .

3.2. Equivalence relation between $FP$ and $ATSP$

Using the results of the previous section it can be shown [5] that $FP$ (the class of functions $f : Γ^{*} \to Γ^{*}$ computable in polynomial time, where Γ is a finite alphabet) and $ATSP$ are equivalent using a notion of emulation that we now present. From now on, we fix an alphabet Γ and we assume that Γ comes with an injective mapping $γ : Γ \to N ∖ {0}$ , which means that every non-blank symbol of the alphabet has a unique assigned positive number (the blank is assigned to 0). By extension, γ applies letter wise over words.

Definition 20 (Discrete emulation).

Let G be a set of functions from $R^{2}$ to $R^{2}$ . The function $f : Γ^{*} \to Γ^{*}$ is called emulable under G if there exists $g \in G$ and $k = 2 + max (γ (Γ))$ such that for any word $w \in Γ^{*}$ one has $\begin{matrix} (2) & g (Ψ_{k} (w)) = Ψ_{k} (f (w)) \end{matrix}$ where $Ψ_{k} (w) = (\sum_{i = 1}^{| w |} γ (w_{i}) k^{- i}, | w |)$ . In these circumstances we also say that g emulates f (see diagram below).

Note that the above definition could be generalized to consider other encodings from $Γ^{*}$ to $R^{n}$ instead of $Ψ_{k}$ . However, since the encoding $Ψ_{k}$ as defined above was used in [5], for simplicity and for coherence of the presentation with what was done in [5], we will continue to use the encoding $Ψ_{k}$ here.

As an intuition behind the above definition, a function g defined over a continuous domain emulates a function f defined over a discrete domain if the operation of encoding commutes with the applications of the functions. This means that, given a fixed input word from a discrete alphabet, encoding from the discrete to the continuous can be done either directly to the input before the application of function g, either after the application of function f to the input, yielding the same result.

For simplicity, later on we will use the notation $0 . γ (w)$ to denote the quantity $\sum_{i = 1}^{| w |} γ (w_{i}) k^{- i}$ . In particular, $Ψ_{k} (w) = (0 . γ (w), | w |)$ .

Theorem 21 ([5], FP equivalence).

Let $f : Γ^{*} \to Γ^{*}$ . Then $f \in FP$ if and only if f is emulable under $ATSP$ .

To show that if $f \in FP$ , then f is emulable under $ATSP$ , recall that if $f \in FP$ , then there is some TM M and some polynomial p such that $f (x)$ can be computed by the TM M in time $p (| x |)$ . By Theorem 18, there is a function $\overline{M} \in ATSP$ such that $\overline{M}$ simulates M on $R^{4}$ using the encoding given by Definition 17 (and a suitable μ. See [5] for more details). This function can then be iterated using Theorem 19 to obtain a corresponding function ${\overline{M}}_{η}^{*} \in ATSP$ . Let $w \in Γ^{*}$ be an input for f. Then $0 . γ (f (w))$ is given as $π_{3} ({\overline{M}}_{η}^{*} (c_{0} (w), p (| w |))) = g_{1} (Ψ_{k} (w))$ , with $g_{1} \in ATSP$ , where $π_{i} : R^{n} \to R$ is defined as $π_{i} (x_{1}, \dots, x_{n}) = x_{i}$ . To show (2), i.e. that f is emulable under $ATSP$ , it just remains to show that $| f (w) |$ can be computed from w and $| w |$ by a function $g_{2}$ .

In [5], it was shown that there is a function ${tlength}_{M} : R \times N \to N$ in $ATSP$ such that ${tlength}_{M} (0 . γ (w), n) = | w |$ when $n ⩾ | w |$ . Furthermore, since a TM can only add, at most, one symbol per computation step, we conclude that $| f (w) | ⩽ | w | + p (| x |)$ . Then $| f (w) | = {tlength}_{M} (0 . γ (f (w)), | w | + p (| x |)) = {tlength}_{M} (g_{1} (Ψ_{k} (w)), | w | + p (| x |)) = g_{2} (Ψ_{k} (w))$ , where $g_{2} \in ATSP$ . Taking $g = (g_{1}, g_{2}) \in ATSP$ , we conclude that f is emulable under $ATSP$ . This yields one direction of the proof of the above result. The reverse direction relies on numerically simulating the ODE used in $ATSP$ using the efficient simulation of [23]. More details will be given in the following section.

4. Computing discrete functions: The exponential case

One might think that the class $FEXPTIME$ of functions computable in exponential time by Turing machines can be obtained similarly as Section 3 by considering the class $ATSE$ as the class formed by all functions in $ATS (Π, Υ)$ where Π, Υ are exponentials functions. Unfortunately, a detailed analysis of the arguments used in [5] shows that to obtain the equivalence of $FP$ with $ATSP$ , we need to use two closure properties of the $ATSP$ class, the closure under arithmetic operations and the closure under composition. As discussed in Section 3 the fact that these properties hold for the exponential $ATSE$ class is not obvious. Specifically, it can be easily shown that the closure by composition of the analog class is only possible if the class of functions used as complexity bounds in Definition 4 satisfies closure properties under composition. This is not a problem when the bounds are polynomial, as in $ATSP$ , since the composition of two polynomials is again another polynomial, but this poses problems when composing exponential bounds, since the composition of two exponentials is not necessarily exponential. Therefore $ATSE$ as defined above in not closed under composition.

In the present paper we solve the above problem and define a class $ATSE$ to characterize the exponential case in a manner that allows compositions compatible with the argument used in [5] to show that $FP$ with $ATSP$ are equivalent. In this manner we will be able to show that $ATSE$ is equivalent to $FEXPTIME$ . Although we use $FEXPTIME$ in our arguments and definitions, they can be applied to a broader class of (super-polynomial) functions as we will later show in Section 5 (see Theorem 35). In the following we are going to define the class of boundaries that we are going to consider for the exponential case, that we call exponential boundary functions.

Definition 22.
We say that a function $f : R \to R$ is an exponential boundary if $f (x) = q (x) c^{p (x)}$ for some polynomials p, q and $c \in R_{G}$ .

We first define the class $ATSE$ which will emulate $FEXPTIME$ in the sense of Definition 20. Following Definition 5, we might be tempted to define $ATSE$ similarly as $ATSP$ , in the sense that $f \in ATSE$ if $f \in ATS (Π, Υ)$ for some exponential functions Π and Υ. While that idea worked well for the polynomial case, it no longer works for exponential functions. To see this with an example, assume that we characterized $ATSE$ as just described. Then given some $f \in ATSE$ , to compute $f (x)$ with accuracy $e^{- μ}$ , we would need to wait a time $t^{} = Π (‖ x ‖, μ)$ exponential in $‖ x ‖$ and μ to get an approximation of $f (x)$ with accuracy $e^{- μ}$ , due to the second condition of Definition 4. Moreover, at time $t^{}$ , we would have that the norm of the solution y of the ODE computing $f (x)$ is bounded by $Υ (‖ x ‖, t^{}) = Υ (‖ x ‖, Π (‖ x ‖, μ))$ , which is a double exponential in both $‖ x ‖$ and μ, while what would be natural is that $‖ y (t^{}) ‖$ is bounded by an exponential in $‖ x ‖$ and μ, and not a double exponential in these parameters. Note that this problem does not happen when both Π and Υ are polynomials: since the composition of two polynomials is again a polynomial, when computing $f (x)$ with accuracy $e^{- μ}$ we will be able to use an approximation $y (t^{*})$ which norm is bounded by a polynomial in $‖ x ‖$ and μ.

Our main insight to solve the above problem is that, contrarily to what was done for the case of $ATSP$ , the complexity bounds for $ATSE$ will depend differently on each of the parameters $‖ x ‖$ , μ, and t. Namely, the dependence will be exponential (or belong to whatever class we are considering) on $‖ x ‖$ , but only polynomial on the remaining parameters.

Another problem that we face is that we expect $ATSE$ to not be closed under composition. This is because it is natural that the exponential function $e^{x}$ belongs to $ATSE$ . Thus if $ATSE$ would be closed under composition, then the double exponential function $e^{e^{x}}$ would also belong to it. However, this is not natural since we expect that the double exponential function grows “too quickly” to belong to $ATSE$ . This poses a problem since in [5] one starts from several “simple functions” in $ATSP$ to build more complex functions, via composition and other operations, which still belong to $ATSP$ and perform useful tasks such as simulating the transition function of a given Turing machine, etc. Therefore we encounter an apparent contradiction, reaching a point where closure by composition is required by the structure of the simulation, but at the same time it is not natural and unfeasible at an exponential level. Here we solve this problem by noting that to prove our main equivalence results it will be enough to compose functions in $ATSP$ with functions in $ATSE$ and that composing functions in $ATSP$ with functions in $ATSE$ still yields a function in $ATSE$ . Hence a pure composition at an exponential level (for the $ATSE$ class) is never needed. Nevertheless, extra care is still required in the analysis, since a similar result has not been obtained for the other direction of the composition between $ATSE$ and $ATSP$ functions (i.e. $f \circ g$ might not belong to $ATSE$ if $f \in ATSE$ and $g \in ATSP$ ).
4.1. Definitions of the exponential analog classes

Definition 23 (ATSE).

Let $f \subseteq R^{n} \to R^{m}$ . Then $f \in ATSE$ if and only if $f \in ATS (Π, Υ)$ for some $Π, Υ : R^{2} \to R$ with the following properties:

$Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ for an exponential boundary function $Π_{1}$ and a polynomial function $Π_{2}$ (time bound);

$Υ (‖ x ‖, t) = Υ_{1} (‖ x ‖) Υ_{2} (t)$ for an exponential boundary function $Υ_{1}$ and a polynomial function $Υ_{2}$ (space bound).

In other words, a function belongs to $ATSE$ if and only if the complexity bounds depend exponentially on $‖ x ‖$ (x is the argument of f) and polynomially on the remaining parameters. Quite naturally, this exponential class is closely related (by means of Theorem 25) to a class of Exponentially-Bounded-Generable-Functions, or $GEVAL$ , whose definition is a straightforward extension of the polynomial version $GPVAL$ described previously.

Definition 24 (GEVAL).

Let D be a domain in $R^{k}$ and let $f : D \to R^{m}$ . We say that $f \in GEVAL$ if and only if there exists an exponential boundary function $sp : R \to R$ , $n ⩾ m$ , a $n \times k$ matrix p consisting of polynomials with coefficients in $R_{G}$ , $x_{0} \in R_{G}^{d} \cap D$ , $y_{0} \in K^{n}$ and $y : D \to R^{n}$ satisfying for all $x \in D$ :

$y (x_{0}) = y_{0}$ and $J_{y} (x) = p (y (x))$ ;

$f (x) = (y_{1} (x), \dots, y_{m} (x))$ ;

$‖ y (x) ‖ ⩽ sp (‖ x ‖)$ .

Note that, since exponential functions can be easily expressed as solutions of polynomial ODEs (for example $f (x) = e^{x}$ is the solution of $y^{'} = y$ , $y (0) = 1$ ) and are always bounded by some exponential boundary function, they trivially belong to the class $GEVAL$ defined above.

4.2. Properties of the exponential analog classes

Using straightforward adaptations of the proofs presented for their polynomial counterparts in [5], we get the following properties:

Theorem 25.
If $f \in GEVAL$ has a star domain with a vantage point in $R_{G}$ , then $f \in ATSE$ .

As a consequence of the above theorem together with our previous observation, exponential functions defined over star domains belong to $ATSE$ .
Theorem 26 (Exponential bound of ATSE).

Let $f \in ATSE$ . Then there exists an exponential boundary function E such that $‖ f (x) ‖ ⩽ E (‖ x ‖)$ .

As mentioned earlier, the closure of the $ATSE$ class by composition and arithmetic operations is not straightforward, but can be obtained (in a limited form for composition) under certain circumstances.

Theorem 27 (ATSE closure by arithmetic operations).

If $g, f \in ATSE$ , then $g + f, g - f, g \cdot f \in ATSE$ , with the obvious restrictions on the domains of definition.

Proof.
We present the proof only for the closure by product, since the other cases are similar. We prove the theorem for dimension one, but the proof can be easily repeated for higher dimensions. Let us consider a function $f \in ATSE (Π_{1} Π_{2}, Υ_{1} Υ_{2})$ and a function $g \in ATSE (Π_{1}^{} Π_{2}^{}, Υ_{1}^{} Υ_{2}^{})$ with parameters d, p, q and $d^{}$ , $p^{}$ , $q^{}$ respectively, where d, $d^{}$ represent the dimensions of the two dynamical systems, p, $p^{}$ the polynomials defining the right hand terms of the differential equations and q, $q^{}$ the exponential boundary functions defining the initial conditions (recall that Definition 23 depends on Definition 4 which defines $ATS$ ). Recall that, by definition of the class, we have that $Π_{1}$ , $Υ_{1}$ , $Π_{1}^{}$ , $Υ_{1}^{}$ are exponential boundary functions and that $Π_{2}$ , $Υ_{2}$ , $Π_{2}^{}$ , $Υ_{2}^{}$ are polynomials. We also assume, without loss of generality, that these functions are non-decreasing. Let $x \in dom f \cap dom g$ and consider the following system: $\begin{matrix} (3) & \{\begin{matrix} y (0) = q (x) \\ y^{'} (t) = p (y (t)) \end{matrix} \{\begin{matrix} z (0) = q^{} (x) \\ z^{'} (t) = p^{} (z (t)) \end{matrix} \{\begin{matrix} w (0) = y_{1} (0) z_{1} (0) \\ w^{'} (t) = p_{1} (y (t)) z_{1} (t) + y_{1} (t) p_{1}^{} (z (t)) \end{matrix} \end{matrix}$ where we are using the notation $p_{1}$ , $z_{1}$ and $p_{1}^{}$ to indicate the first component of the vectors. Note that the solution of (3) for the variable w is: $w (t) = y_{1} (t) z_{1} (t)$ and that this system has polynomial right hand terms. We can now proceed with the analysis of the boundaries. Since $f, g \in ATSE$ , from Definition 23, we conclude (taking $μ = 0$ ) that for $t ⩾ Π_{1} (‖ x ‖) Π_{2} (0)$ we have $‖ (y_{1} (t), \dots, y_{m} (t)) - f (x) ‖ ⩽ e^{- 0} = 1$ and $‖ y (t) ‖ ⩽ Υ_{1} (‖ x ‖) Υ_{2} (t)$ . This implies that $‖ f (x) ‖ ⩽ 1 + ‖ y (t) ‖ ⩽ 1 + Υ_{1} (‖ x ‖) Υ_{2} (t)$ . In particular, taking $t = Π_{1} (‖ x ‖) Π_{2} (0)$ gives $‖ f (x) ‖ ⩽ 1 + Υ_{1} (‖ x ‖) Υ_{2} (Π_{1} (‖ x ‖) Π_{2} (0))$ . A similar argument yields $‖ g (x) ‖ ⩽ 1 + Υ_{1}^{} (‖ x ‖) Υ_{2}^{} (Π_{1}^{} (‖ x ‖) Π_{2}^{} (0))$ . Denote by $l (‖ x ‖)$ and $l^{} (‖ x ‖)$ these two bounds for $‖ f (x) ‖$ and $‖ g (x) ‖$ , respectively (i.e $l (‖ x ‖) = 1 + Υ_{1} (‖ x ‖) Υ_{2} (Π_{1} (‖ x ‖) Π_{2} (0))$ and similarly for $l^{} (‖ x ‖)$ ). Note that we get that $l (‖ x ‖)$ and $l^{} (‖ x ‖)$ are exponential boundaries functions, and this would not have been true if $Π_{2}$ , $Υ_{2}$ , $Π_{2}^{}$ , $Υ_{2}^{}$ were not polynomials. Now consider $t ⩾ Π_{1} (‖ x ‖) Π_{2} (μ + ln 2 l^{} (‖ x ‖))$ ; then $‖ f (x) - y_{1} (t) ‖ ⩽ e^{- (μ + ln 2 ‖ g (x) ‖)}$ and in the same way if $t ⩾ Π_{1}^{} (‖ x ‖) Π_{2}^{} (μ + ln (2 + 2 l (‖ x ‖)))$ then $‖ g (x) - z_{1} (t) ‖ ⩽ e^{- (μ + ln (2 + 2 ‖ f (x) ‖))}$ . Therefore if we consider times greater than the maximum of these two bounds we have: $\begin{matrix} ‖ y_{1} (t) z_{1} (t) - f (x) g (x) ‖ ⩽ ‖ (y_{1} (t) - f (x)) g (x) ‖ + ‖ y_{1} (t) (z_{1} (t) - g (x)) ‖ ⩽ e^{- μ} \end{matrix}$ this proves the time bound of Definition 23. The space bound is verified by observing that $‖ y_{1} (t) ‖ ⩽ l (‖ x ‖)$ and $‖ z_{1} (t) ‖ ⩽ l^{*} (‖ x ‖)$ and this concludes the proof. □
Theorem 28 (Composition of ATSE and ATSP).

Let f be a function, $f \in ATSE$ and g be a function, $g \in ATSP$ . Then $g \circ f \in ATSE$ .

Proof.
Let $f : R^{n} \to R^{m}$ and let $g : R^{m} \to R^{l}$ . We will show that $g \circ f \in ATSE$ by using Proposition 6 for g. Indeed, if $g \in ATSP$ , by Proposition 6, then there are polynomials Π, Υ, Λ such that Proposition 6 holds with corresponding r, δ, $z_{0}$ , where r is the polynomial defining the differential equation, $δ \in R$ is the same parameter as in Proposition 6, and $z_{0}$ is the initial condition of the system. In the same way we obtain that there exist two exponential boundary functions $Π_{1}^{'}$ , $Υ_{1}^{'}$ , and two polynomials $Π_{2}^{'}$ , $Υ_{2}^{'}$ such that $f \in ATSE (Π_{1}^{'} Π_{2}^{'}, Υ_{1}^{'} Υ_{2}^{'})$ with corresponding parameters d, p, q for the dimension and polynomials defining the system. Assume, without loss of generality, that all the functions used as boundaries for definitions of f and g are increasing functions. Let $x \in R^{n}$ and consider the following system: $\begin{matrix} \{\begin{matrix} y (0) = q (x) \\ y^{'} (t) = p (y (t)) \end{matrix} \{\begin{matrix} z (0) = z_{0} \\ z^{'} (t) = r (z (t), y_{1.. m} (t)) \end{matrix} \{\begin{matrix} x (0) = x \\ x^{'} (t) = 0 \end{matrix} \end{matrix}$ where $y_{1.. m} (t) = (y_{1} (t), \dots, y_{m} (t))$ . Define $v (t) = (x (t), y (t), z (t))$ . Then it immediately follows that v satisfies a PIVP of the form: $\begin{matrix} (4) & \{\begin{matrix} v (0) = poly (x) \\ v^{'} (t) = poly (v (t)) . \end{matrix} \end{matrix}$ We will show that the polynomial IVP (4) computes $g \circ f$ according to Definition 23. First we check the space bound condition of that definition. By definition of v we have $\begin{matrix} ‖ v (t) ‖ & = max (‖ x (t) ‖, ‖ y (t) ‖, ‖ z (t) ‖) \\ ⩽ max (‖ x ‖, ‖ y (t) ‖, Υ (sup_{u \in [t, t - δ]} ‖ y_{1.. m} (u) ‖, t)) \\ ⩽ exp (‖ x ‖) poly (sup_{u \in [t, t - δ]} ‖ y (u) ‖, t) \\ ⩽ exp (‖ x ‖) poly (sup_{u \in [t, t - δ]} Υ_{1}^{'} (‖ x ‖) Υ_{2}^{'} (u), t) \\ ⩽ exp (‖ x ‖) poly (t) \end{matrix}$ where the notation poly and exp indicate an unspecified polynomial and an unspecified exponential boundary function, respectively. This proves the space bound.

Let us now tackle the time bound of Definition 23. Define $\bar{x} = f (x)$ , $Υ^{} (α) = Υ_{1}^{'} (α) Υ_{2}^{'} (Π_{1}^{'} (α) Π_{2}^{'} (0)) + 1$ and $Π^{″} (α, μ) = Π_{1}^{'} (α) Π_{2}^{'} (Λ (Υ^{} (α), μ)) + Π (Υ^{} (α), μ)$ . Note that $Υ^{}$ is an exponential boundary function. Furthermore, we can easily find two functions, $Π_{1}^{}$ and $Π_{2}^{}$ , such that $0 ⩽ Π^{″} (α, μ) ⩽ Π_{1}^{} (α) Π_{2}^{} (μ)$ where $Π_{1}^{}$ is an exponential boundary function and $Π_{2}^{}$ is a polynomial. From the fact that $f \in ATSE (Π_{1}^{'} Π_{2}^{'}, Υ_{1}^{'} Υ_{2}^{'})$ , by using time $t^{} = Π_{1}^{'} (‖ x ‖) Π_{2}^{'} (0)$ , we conclude that $‖ y_{1.. m} (t^{}) - f (x) ‖ ⩽ e^{- 0}$ , which implies that $\begin{array}{l} ‖ \bar{x} ‖ & = ‖ f (x) ‖ \\ ⩽ ‖ y (t^{}) ‖ + 1 \\ ⩽ Υ_{1}^{'} (‖ x ‖) Υ_{2}^{'} (t^{}) + 1 \\ = Υ_{1}^{'} (‖ x ‖) Υ_{2}^{'} (Π_{1}^{'} (‖ x ‖) Π_{2}^{'} (0)) + 1 \\ = Υ^{} (‖ x ‖) . \end{array}$ Let $μ > 0$ . By definition of $ATSE$ , if $t ⩾ Π_{1}^{'} (‖ x ‖) Π_{2}^{'} (Λ (Υ^{} (‖ x ‖), μ))$ then $‖ y_{1.. m} (t) - \bar{x} ‖ ⩽ e^{- Λ (Υ^{} (‖ x ‖), μ))} ⩽ e^{- Λ (‖ x ‖, μ)}$ . Therefore, due to Proposition 6, we have $\begin{matrix} t ⩾ Π_{1}^{'} (‖ x ‖) Π_{2}^{'} (Λ (Υ^{} (‖ x ‖), μ)) + Π (‖ \bar{x} ‖, μ) \Rightarrow ‖ v_{1.. l} (t) - g (f (x)) ‖ ⩽ e^{- μ} . \end{matrix}$ Note that $Π_{1}^{'} (‖ x ‖) Π_{2}^{'} (Λ (Υ^{*} (‖ x ‖), μ)) + Π (‖ \bar{x} ‖, μ)$ depends exponentially on $‖ x ‖$ , but only polynomially on μ. This shows the time bound for $ATSE$ . □

4.3. Analog characterization of $FEXPTIME$

Finally, we can state one of the main results of this paper. By adapting the construction already developed in [5], we can show the equivalence between the class $ATSE$ and the class of $FEXPTIME$ of functions computable in exponential time. This equivalence is described by the following theorem:

Theorem 29 (FEXPTIME equivalence).

Let $f : Γ^{*} \to Γ^{*}$ . Then $f \in FEXPTIME$ if and only if f is emulable under $ATSE$ .

Next we proceed with the proof of Theorem 29. We will prove the direct and reverse direction of the theorem separately.

For the direct direction of Theorem 29, we have to show that if $f \in FEXPTIME$ , then f is emulable under $ATSE$ . Suppose that f is computable by a Turing machine M. To achieve our purpose, we will need once again to be able to iterate the transition function of M, which belongs to $ATSP$ , due to Theorem 18, with the help of Theorem 19. The main difference to the polynomial case will be the number of iterations of the transition function required to simulate the functioning of the Turing machine M until it halts. Since $f \in FEXPTIME$ , the number of steps which will have to be simulated is exponential on the size of the input and not polynomial as in the original case analyzed in [5]. Nevertheless, an exponential version of Theorem 19 is not necessary, and the original polynomial version is enough for our goal. More concretely, let us show in more detail how the construction of the simulation is made.

Let us assume that $M = (Q, Σ, b, δ, q_{0}, F)$ , where $Σ = {0, 1, \dots, k - 2}$ with $b = 0$ , and $γ (Γ) \subset Σ ∖ {b}$ , and consider an exponential boundary function $e_{M} (| w |) \equiv K^{| w |} \in N$ for some constant $K \in N$ such that for any word $w \in Γ^{*}$ the TM M halts in at most $e_{M} (| w |)$ steps, that is $M^{[e_{M} (| w |)]} (c_{0} (γ (w))) = c_{\infty} (γ (f (w)))$ . We assume that $Ψ_{k} (w) = (0 . γ (w), | w |)$ for any word $w \in Γ^{*}$ as before. Define $μ = ln (4 k^{2})$ and $h (c) = \overline{M} (c, μ)$ for all $c \in R^{4}$ . Define $I_{\infty} = ⟨ C_{M} ⟩$ , where $C_{M}$ is the set of all configurations of M, and $I_{n} = I_{\infty} + {[ϵ_{n}, ϵ_{n}]}^{4}$ where $ϵ_{n} = \frac{1}{4 k^{2 + n}}$ for all $n \in N$ . Note that $ϵ_{n + 1} ⩽ \frac{ϵ_{n}}{k}$ and that $ϵ_{0} ⩽ \frac{1}{2 k^{2}} - e^{- μ}$ . Due to Theorem 18, we have that the transition function of this machine, h, satisfies $h \in ATSP$ and $h (I_{n + 1}) \subseteq I_{n}$ . In particular $‖ h^{[n]} (\bar{c}) - h^{[n]} (c) ‖ ⩽ k^{n} ‖ c - \bar{c} ‖$ for all $c \in I_{\infty}$ , $\bar{c} \in I_{n}$ , and $n \in N$ . Let $δ \in [0, \frac{1}{2} [$ and define $J = ⋃_{n \in N} I_{n} \times [n - δ, n + δ]$ . Then apply Theorem 19 to the function h to get $h_{δ}^{*} : J \to I_{0} \in ATSP$ such that for all $c \in I_{\infty}$ and $n \in N$ we have $h_{δ}^{*} (c, n) = h^{[n]} (c)$ .

Let $π_{i}$ denote the ith projection, that is, $π_{i} (x) = x_{i}$ . Then $π_{i} \in ATSP$ . Take $g (y, l) = π_{3} (h_{δ}^{*} (0, b, y, q_{0}, e_{M} (l)))$ . Note that g is well defined. Indeed, if $(y, l) = Ψ_{k} (w)$ for some $w \in Γ^{*}$ , then $y = 0 . γ (w)$ , $l = | w |$ , and $(0, b, y, q_{0}) = ⟨ (λ, b, γ (w), q_{0}) ⟩ = ⟨ c_{0} (γ (w)) ⟩ \in I_{\infty}$ . Therefore, by construction, for any word $w \in Γ^{*}$ we have $\begin{matrix} g (Ψ_{k} (w)) & = π_{3} (h_{δ}^{*} (⟨ c_{0} (γ (w)) ⟩, e_{M} (| w |))) \\ = π_{3} (h^{[e_{M} (| w |)]} ⟨ c_{0} (γ (w)) ⟩) \\ = π_{3} (⟨ C_{M}^{[e_{M} (| w |)]} (c_{0} (γ (w))) ⟩) \\ = π_{3} (⟨ c_{\infty} (γ (f (w))) ⟩) \\ = 0 . γ (f (w)) = π_{1} (Ψ_{k} (f (w))) . \end{matrix}$ Recall that to show the validity of the emulation we need to compute $Ψ_{k} (f (w))$ and so far we only have the first component, the output of the tape encoding, but we miss the second component: its length. To complete the task, we can proceed similarly as in Section 3 and apply the function ${tlength}_{M}$ from [5] presented there.

In particular, we get that ${tlength}_{M} (g (Ψ_{k} (w)), | w | + e_{M} (| w |)) = | 0 . γ (f (w)) | = | f (w) |$ , since $0 . γ (f (w))$ does not contain any blank character by definition of γ and $| f (w) | ⩽ | w | + e_{M} (| w |)$ . What we have just showed above proves that $\begin{matrix} (5) & \bar{g} (Ψ_{k} (w)) \equiv (g (Ψ_{k} (w)), {tlength}_{M} (g (Ψ_{k} (w)), | w | + e_{M} (| w |))) \end{matrix}$ emulates f according with Definition 20. To conclude the direct direction of the theorem, the last result to prove is that $\bar{g} \in ATSE$ .

Recalling that $g (Ψ_{k} (w)) = π_{3} (h_{δ}^{*} (⟨ c_{0} (γ (w)) ⟩, e_{M} (| w |)))$ , we conclude from Theorem 19 that $h_{δ}^{*} \in ATSP$ . It is trivial to show that $e_{M} \in ATSE$ . Then, due to the composition theorem, Theorem 28, we obtain that $h_{δ}^{*} (⟨ c_{0} (γ (w)) ⟩, e_{M} (| w |)) \in ATSE$ . Due to (5), where $g (Ψ_{k} (w)) = π_{3} (h_{δ}^{*} (⟨ c_{0} (γ (w)) ⟩, e_{M} (| w |)))$ , and since $tlength, π_{3} \in ATSP$ and $h_{δ}^{*} (⟨ c_{0} (γ (w)) ⟩, e_{M} (| w |)), e_{M} \in ATSE$ , we can apply again Theorem 28 to conclude that $\bar{g} \in ATSE$ and thus prove the direct direction of Theorem 29.

We now proceed with the reverse direction of the proof. In other words, we have to show that if f is emulable under $ATSE$ , then $f \in FEXPTIME$ . The argument presented here is similar to the one already provided in [5] for the $ATSP$ equivalence. The main difference is the nature of the boundaries. To be able to prove this result, it is necessary to introduce a theorem about the complexity of solving polynomial differential equations. The proof and more details about the theorem can be found in [23]. Before we state this theorem, we need to introduce some notation. We use the multi-index notation for multivariate polynomials as follows: a monomial $x_{1}^{α_{1}} \dots x_{k}^{α_{k}}$ is represented by $x^{α}$ , where $x = (x_{1}, \dots, x_{k})$ , $α = (α_{1}, \dots, α_{k})$ , $| a | = α_{1} + \dots + α_{k}$ is the degree of the monomial. For any multivariate polynomial $p (x) = \sum_{| α | ⩽ k} a_{α} x^{α}$ we call k the degree of p, $k = \deg (p)$ , if k is the minimal integer for which the condition $p (x) = \sum_{| α | ⩽ k} a_{α} x^{α}$ holds, and we denote the sum of the norm of the coefficients by $Σ p = \sum_{| α | ⩽ k} | a_{α} |$ . For a vector of polynomials, we define the degree and $Σ p$ as the maximum over all components. For any continuous y and polynomial p, define the pseudo-length as: $\begin{matrix} {PsLen}_{y, p} (a, b) = \int_{a}^{b} Σ p max {(1, ‖ y (u) ‖)}^{\deg (p)} d u \end{matrix}$ We are now in condition to state the above mentioned theorem.

Theorem 30 ([23]).

Let $I = [a, b]$ be an interval, $p : R^{n} \to R^{n}$ be such that each of its one-dimensional components is a polynomial of degree at most k, and let $y_{0} \in R^{n}$ . Assume that $y : I \to R^{n}$ is a solution of the IVP $y (a) = y_{0}$ , $y^{'} (t) = p (y (t))$ . Then $y (b)$ can be computed with precision $2^{- μ}$ in time bounded by $poly {(\deg (p), {PsLen}_{y, p} (a, b), log ‖ y_{0} ‖, Σ p, μ)}^{n}$ .

More precisely, the theorem states that there is a Turing machine M such that for any oracle O representing $(a, y_{0}, p, b)$ and any input $μ \in N$ , M outputs a value $M^{O} (μ)$ satisfying $‖ M^{O} (μ) - y (b) ‖ ⩽ 2^{- μ}$ , where y is the solution of the previous differential equation and the number of steps of the machine is bounded by the above expression.

Now we can continue with the proof of the reverse direction of Theorem 29. Assume that f is emulable under $ATSE$ . Let g be the function used in the emulation which satisfies (2). Then $g \in ATSE (Π_{1} Π_{2}, Υ_{1} Υ_{2})$ , where d is the dimension and p, q are the polynomials generating the $ATSE$ dynamical system associated to g. Recall that, by definition of the class $ATSE$ , $Υ_{1}$ , $Π_{1}$ are exponential boundary functions and $Υ_{2}$ , $Π_{2}$ are polynomials. Let $w \in Γ^{*}$ . We will now describe an $FEXPTIME$ algorithm to compute $f (w)$ . Consider the following system $\begin{matrix} y^{'} (t) = p (y (t)), y (0) = q (Ψ_{k} (w)) . \end{matrix}$ Note that the coefficients of p, q and $q (Ψ_{k} (w))$ are polynomially computable in the sense of computable analysis. To show that $f \in FEXPTIME$ , we have to present an algorithm which, on input x computes $f (x)$ in exponential time. The algorithm works in two steps: first, we compute a rough approximation of the output to be able to guess the length of the output. Then we rerun the system with enough precision to get the full output.

Let $t_{w} = Π_{1} (| w |) Π_{2} (2)$ for any $w \in Σ^{*}$ . Note that $t_{w}$ is computable and that it is exponentially bounded in $| w |$ because $Π_{1}$ is an exponential boundary function. Now apply Theorem 30 to compute $\bar{y} = ({\bar{y}}_{1}, {\bar{y}}_{2}) \in R^{2}$ such that $‖ \bar{y} - y (t_{w}) ‖ ⩽ e^{- 2}$ . This operation takes a computational time that is exponential in $| w |$ because $t_{w}$ is exponentially bounded and because $\begin{array}{l} {PsLen}_{y, p} (0, t_{w}) & = \int_{0}^{t_{w}} Σ p max {(1, ‖ y (u) ‖)}^{\deg (p)} d u \\ ⩽ \int_{0}^{t_{w}} Σ p max {(1, sup_{t \in [0, t_{w}]} ‖ y (t) ‖)}^{\deg (p)} d u \\ = Σ p max {(1, sup_{t \in [0, t_{w}]} ‖ y (t) ‖)}^{\deg (p)} t_{w} \\ = poly (t_{w}, sup_{[0, t_{w}]} ‖ y (t) ‖) \end{array}$ and, by construction, $‖ y (t) ‖ ⩽ Υ_{1} (‖ Ψ_{k} (w) ‖) Υ_{2} (t_{w})$ for $t \in [0, t_{w}]$ where $Υ_{1}$ is an exponential boundary function and $Υ_{2}$ is a polynomial (we assume, without loss of generality, that $Υ_{2}$ is an increasing function), which implies that ${PsLen}_{y, p} (0, t_{w}) ⩽ poly (t_{w}, Υ_{1} (‖ Ψ_{k} (w) ‖) Υ_{2} (t_{w})) = exp (| w |)$ . Furthermore, by definition of $t_{w}$ , we have $‖ y (t_{w}) - g (Ψ_{k} (w)) ‖ ⩽ e^{- 2}$ and thus $‖ \bar{y} - Ψ_{k} (f (w)) ‖ ⩽ 2 e^{- 2} ⩽ \frac{1}{3}$ . But, since $Ψ_{k} (f (w)) = (0 . γ (f (w)), | f (w) |)$ , from ${\bar{y}}_{2}$ we can find $| f (w) |$ by rounding to the closest integer. In other words we can compute $| f (w) |$ in exponential time in $| w |$ . Note that this implies that $| f (w) |$ is at most exponential in $| w |$ .

Let $t_{w}^{'} = Π_{1} (| w |) Π_{2} (2 + | f (w) | ln k)$ . Note that there is always an exponential boundary function on $| w |$ such that it is greater than $t_{w}^{'}$ . Indeed, $Π_{1}$ is an exponential boundary function, $Π_{2}$ is a polynomial, and $| f (w) |$ is at most exponential in $| w |$ . We can then apply the same reasoning and use again Theorem 30 to get an $\tilde{y}$ such that $‖ \tilde{y} - y (t_{w}^{'}) ‖ ⩽ e^{- 2 - | f (w) | ln k}$ . Once again this operation takes a time exponential in $| w |$ . Furthermore, $‖ {\tilde{y}}_{1} - 0 . γ (f (w)) ‖ ⩽ 2 e^{- 2 - | f (w) | ln k} ⩽ \frac{1}{3} k^{- | f (w) |}$ . We claim that this allows us to recover $f (w)$ unambiguously in exponential time in $| w |$ . Indeed, it implies that $‖ k^{| f (w) |} {\tilde{y}}_{1} - k^{| f (w) |} 0 . γ (f (w)) ‖ ⩽ \frac{1}{3}$ . Unfolding the definition shows that $k^{| f (w) |} 0 . γ (f (w)) = \sum_{i = 1}^{| f (w) |} γ (f {(w)}_{i}) k^{| f (w) | - i} \in N$ , thus by rounding $k^{| f (w) |} {\tilde{y}}_{1}$ to the closest integer we recover $γ (f (w))$ and then $f (w)$ . This is all done in polynomial time in $| f (w) |$ , and so in exponential time in $| w |$ . This completes the proof of Theorem 29.

5. Going beyond the exponential case

As we have showed previously in this paper, the key intuition of splitting the dependence of the time and space boundaries from one single term, Υ, into the product of two separate components $Υ_{1} Υ_{2}$ with different behaviors has allowed us to capture the full power of exponential time computation with the suitable dynamical systems of polynomial differential equations. Since this procedure has successfully divided the part of the construction that may continue to depend polynomially on the input from the part that has to depend exponentially from the input in order to obtain the equivalence, and since this division process does not seem to explicitly depend on properties possessed only by exponential type of boundaries, it is natural to wonder if an equivalence can be obtained in the same way for other standard complexity classes in a straightforward manner. More precisely, if the second part of the time and space boundaries ( $Π_{2}$ and $Υ_{2}$ in the original $ATSE$ definition) is kept polynomial, it is natural to wonder which classes of functions can be used as first term ( $Π_{1}$ and $Υ_{1}$ ) in order to characterize other classes from standard complexity theory.

Following every step of the proofs, starting from the basic properties and definitions of the $GEVAL$ and $ATSE$ classes, it is possible to see that four conditions are sufficient for the construction to hold.

In this section we extend the result of Theorem 21 to other complexity classes. More precisely, we list which conditions the analog classes involved have to satisfy in order to repeat the simulation process already obtained for the polynomial case. First, let us define a version of the $ATS$ class in which the time and space boundaries are defined using functions from a set A of functions over the reals. More concretely, and in a similar manner to Definition 23, we introduce the following definition.

Definition 31.
Let $f \subseteq R^{n} \to R^{m}$ and let A be a class of functions from $R_{+} = [0, + \infty [$ to $R_{+}$ . Then $f \in AT S_{p} (A)$ if and only if $f \in ATS (Π, Υ)$ for some $Π, Υ : R^{2} \to R$ with the following properties:
$Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ for some function $Π_{1} \in A$ and a polynomial function $Π_{2}$ (time bound);

$Υ (‖ x ‖, t) = Υ_{1} (‖ x ‖) Υ_{2} (t)$ for some function $Υ_{1} \in A$ and a polynomial function $Υ_{2}$ (space bound).

As we already discussed in the previous section, we need to be able to enforce closure by composition and by arithmetic operations for the class $AT S_{p} (A)$ to extend the result of Theorem 21 to other complexity classes. Nevertheless, a more careful analysis of the details of the construction shows that the functions in A should satisfy other additional properties that are trivially shared by polynomials and exponentials, but that are not obvious for a generic class A. Before stating sufficient conditions that ensure closure by composition and by arithmetic operations for the class $AT S_{p} (A)$ , we recall the notion of time-constructible functions [15].
Definition 32 (Time-constructible function).

Let $f : N \to N$ be a function. We call f time-constructible if there exists a Turing machine M which, given as an input a string $1^{n}$ , outputs the binary representation of $f (n)$ in time $O (f (n))$ .

We now present conditions that ensure that the result of Theorem 21 can be extended to other complexity classes.

Definition 33 (Sufficient conditions).

Let A be a class of functions from $R_{+}$ to $R_{+}$ such that:

If $f, g \in A$ then there exists $h \in A$ such that $f ⋆ g (x) ⩽ h (x)$ for every $x \in R_{+}$ , where ⋆ denotes any operator in the list of arithmetical operations: $(+, -, \times)$

If p is polynomial and $f \in A$ then there exists $g \in A$ such that $p \circ f (x) ⩽ g (x)$ and $f \circ p (x) ⩽ g (x)$ for every $x \in R_{+}$ . Moreover, the identity operator belongs to A

If $f \in A$ , then there exists $g \in A$ such that $f (n) ⩽ g (n)$ for every $n \in N$ and $g \in AT S_{p} (A)$

If $f \in A$ then there exists $g : N \to N$ and $h \in A$ and such that $f (n) ⩽ g (n) ⩽ h (n)$ for every $n \in N$ and g is a time-constructible function.

The first condition enforces a form of closure for the main arithmetical operations which are of interest to us. The second condition provides enough elements so that we can have a variant of Theorem 28 for the class $AT S_{p} (A)$ as well as allowing us to replace a polynomial in the proofs by a member of A when needed (polynomials may not belong to A). The third condition is sufficient to show that if a function is computed by a Turing machine in time $f |_{N}$ , where $f \in A$ ,1

¹
Note that $f (N) \subseteq [0, + \infty [$ . Hence, although $f (n)$ might not belong to $N$ when $n \in N$ , we can still say that a Turing machine computes in time $⩽ f (n)$ .

then we may replace f by a function

g \in AT S_{p} (A)

which will play a role similar to the time bound

e_{M}

in the proof of Theorem 29. The fourth and final condition is due to the fact that we do not have any assurances about the computability or complexity needed to compute elements of A. If some bound f of

AT S_{p} (A)

has these problems, we need to be sure that we can replace it by a well-behaved bound g, which can be used to prove the reverse direction of Theorem 29, e.g. when computing the value

t_{w}

. Of course, the function g should not grow quicker than any element of A, hence there is the need to ensure that there is a function

h \in A

which grows at least as quickly as g over the naturals.

We recall that if $f \in A$ is a function such that $f (N) \subseteq [0, + \infty [$ , then we say that a Turing machine M computes a set of functions $F$ in time $O (f (n))$ if there are some $c, n_{0} \in N$ such that if w is a word of length $n ⩾ n_{0}$ , then M computes $g (w) \in F$ in time $⩽ c f (n)$ . Now we can define $FTIME (A) = {g | g : N \to N is a function computable in time O (f (n)) for some f \in A}$ . Another important remark is the following:

Remark 34.

We note that, similarly to what happens to $GPVAL$ and $GEVAL$ , we can more generally define a class $GVAL (A)$ . If A satisfies the conditions of Definition 33, then it follows from lemma 24 and corollary 26 of [6] that $GVAL (A)$ is closed under addition, difference, product, and ODE solving (i. e., if $f \in GVAL (A)$ , then a solution of $y^{'} = f (y)$ also belongs to $GVAL (A)$ ).

At this point we can finally state the following generalized equivalence theorem.

Theorem 35 (Generalized equivalence).

Let A be a class of functions that satisfies the conditions of Definition 33 . Then given a function $f : Γ^{*} \to Γ^{*}$ , we have that $f \in FTIME (A)$ if and only if f is emulable under $AT S_{p} (A)$ .

We will use this theorem to characterize the Grzegorczyk hierarchy with ODEs. In particular, we will also be able to characterize the class of elementary computable functions and the class of primitive recursive functions with ODEs. Nonetheless, before proceeding with the application of Theorem 35 above to the case of the Grzegorczyk hierarchy, in the next section we show that, similarly to the case of the polynomial class $ATSP$ , also the generalized class $AT S_{p} (A)$ can be interpreted just by means of the length of the solutions of the ODEs involved. This possibility is particularly relevant because it reduces the number of parameters necessary to describe the complexity of the system. Indeed, while the $AT S_{p} (A)$ class needed to make use of both a space boundary (on the norm of the solution) and a time boundary (on the convergence rate), this interpretation makes use of just the length of the solution curve. This perspective was illustrated at a polynomial level in [5] introducing another analog class called $ALP$ , Analog-Length-Polynomial, defined using the length of the solution $y (t)$ , and then proving the equivalence of this class with the class $ATSP$ . In the next section we follow a similar path and generalize this result to the case of analog classes constructed over boundaries taken from a generic set of functions A.

6. Generalization of the Analog Length class

We start this section by introducing the definitions required to understand the meaning of the Analog Length class.

Definition 36.
Let $f \subseteq R^{n} \to R^{m}$ . We say that $f \in AL (Π, Υ)$ , where $Π : R^{2} \to R$ if and only if there exist a multivariate polynomial p with coefficients in $R_{G}$ and a function $q \in GPVAL$ such that for any $x \in dom (f)$ , there exists (a unique) $y : R \to R^{d}$ satisfying for all $t ⩾ 0$ :
$y (0) = q (x)$ and $y^{'} (t) = p (y (t))$ ;

$\forall μ > 0$ if ${len}_{y} (0, t) ⩾ Π (‖ x ‖, μ)$ then $‖ (y_{1} (t), \dots, y_{m} (t)) - f (x) ‖ ⩽ e^{- μ}$ ;

$‖ y^{'} (t) ‖ ⩾ 1$ .

In Definition 36 the first item has the same role of the first condition of the definition of $AT S_{p} (A)$ , which is to describe the evolution of the dynamical system. The second item is related to the length of the solution $y (t)$ . Specifically, we are requiring that whenever a certain length of the solution is reached by the system, where the exact amount is dictated by the boundary Π, then it starts the convergence of the system to the correct value of the function f. The way this convergence is obtained is similar to one of $AT S_{p} (A)$ . Finally, the third item is necessary to exclude pathological cases in which the evolution of the dynamical system is too slow and where it might happen that there is some $M > 0$ such that ${len}_{y} (0, t) ⩽ M$ for all $t ⩾ 0$ , thus making the second condition meaningless. A example of such situation is provided by the ODE $y^{'} = - y$ with initial condition $y (0) = 1$ . It is not difficult to see that its solution is $y (t) = e^{- t}$ and that as $t \to + \infty$ , $y (t)$ moves monotonically from the value 1 to 0. Thus the length of the solution curve of this ODE is bounded even when $t \to + \infty$ . We also note that we can avoid this situation, using different requirements. For example, instead of requiring that $‖ y^{'} (t) ‖ ⩾ 1$ for the last condition, we could have required that there is an component $y_{i}$ of y such that $| y_{i} (t) | ⩾ 1$ for all $t ⩾ 0$ .
Definition 37.
Let $f \subseteq R^{n} \to R^{m}$ and let A be a class of functions from $R_{+} = [0, + \infty [$ to $R_{+}$ . Then $f \in AL (A)$ if and only if $f \in AL (Π)$ for some $Π : R^{2} \to R$ with the property that $Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ for some function $Π_{1} \in A$ and a polynomial function $Π_{2}$ .

Notice that Definition 37 is just the generalization of Definition 36 when the boundary Π is taken from a set A, exactly as definition of $AT S_{p} (A)$ was the generalization of the class $ATS$ .

To proceed with the arguments of this section we now need to introduce a lemma showing some useful boundaries over multivariate polynomials.
Lemma 38.
Let $p : R^{k} \to R$ be a multivariate polynomial of degree n, with $p (x) = Σ_{| α | ⩽ n} a_{α} x^{α}$ , where $α = (α_{1}, \dots, α_{k}) \in N^{k}$ , $| α | = α_{1} + \dots + α_{k}$ , and $x^{α} = x_{1}^{α_{1}} \dots x_{k}^{α_{k}}$ . Then there are polynomials $P_{1}, \dots, P_{k}$ of degree at most n, such that $\begin{matrix} ‖ p (x) ‖ ⩽ P_{1} (| x_{1} |) \dots P_{k} (| x_{k} |) . \end{matrix}$
Proof.
We have $\begin{matrix} ‖ p (x) ‖ ⩽ \sum_{| α | ⩽ n} | a_{α} | ‖ x_{1}^{α_{1}} \dots x_{k}^{α_{k}} ‖ ⩽ \sum_{| α | ⩽ n} | a_{α} | | x_{1} |^{α_{1}} \dots | x_{k} |^{α_{k}} \end{matrix}$ Now notice that $| x_{i} |^{| α |} ⩽ max {(1, | x_{i} |)}^{n}$ since: (i) if $| x_{i} | ⩽ 1$ , then $| x_{i} |^{| α |} ⩽ 1 = max {(1, | x_{i} |)}^{n}$ and (ii) if $| x_{i} | ⩾ 1$ , then $| x_{i} |^{| α |} ⩽ | x_{i} |^{n} = max {(1, | x_{i} |)}^{n}$ . This implies that $\begin{array}{l} ‖ p (x) ‖ & ⩽ \sum_{| α | ⩽ n} | a_{α} | max {(1, | x_{1} |)}^{n} \dots max {(1, | x_{k} |)}^{n} \\ ⩽ (\sum p) max {(1, ‖ x ‖)}^{n} \\ ⩽ (\sum p) {(1 + | x_{1} |)}^{n} \dots {(1 + | x_{k} |)}^{n} \end{array}$ where $\sum p = \sum_{| α | ⩽ n} | a_{α} |$ . This concludes the proof of the lemma. □

Let us now assume that the set A considered in this section satisfies the conditions listed above in Definition 33. Then we obtain an equivalence between the two analog classes in the form of the following theorem: Theorem 39.
If A is a class of functions which satisfies the conditions of Definition 33 , then $AT S_{p} (A) = AL (A)$ .
Proof.
The proof of this theorem follows essentially the structure of the proof of Theorem 18 in [4]. Let us first suppose that $f \in AT S_{p} (A)$ , with $f : R^{n} \to R^{m}$ . We want to show that $f \in AL (A)$ . Since $f \in AT S_{p} (A)$ , there exist a polynomial p, functions $Υ_{1}, Π_{1} \in A$ , and polynomials $Π_{2}$ , $Υ_{2}$ satisfying the conditions of Definition 4 when Π and Υ are given by $Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ and $Υ (‖ x ‖, t) = Υ_{1} (‖ x ‖) Υ_{2} (t)$ , respectively. We also assume, without loss of generality, that the polynomials $Π_{2}$ , $Υ_{2}$ are increasing and take non-negative values when they have non-negative arguments. Now consider the system $\begin{matrix} \{\begin{matrix} y (0) = q (x) \\ z (0) = 0 \end{matrix} \{\begin{matrix} y^{'} (t) = p (y (t)) \\ z^{'} (t) = 1 \end{matrix} \end{matrix}$ We now show that this system computes f according to Definition 36. The first and third condition of Definition 36 are trivially satisfied for the above system. We now have to show that the second condition holds for some function $Π^{}$ , where $Π^{} (‖ x ‖, μ) = Π_{1}^{} (‖ x ‖) Π_{2}^{} (μ)$ and $Π_{1}^{} \in A$ and $Π_{2}^{}$ is a polynomial.

We begin by noting that if $t < Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ , then by the third condition of Definition 4 $\begin{matrix} (6) & ‖ y (t) ‖ ⩽ Υ (‖ x ‖, t) = Υ_{1} (‖ x ‖) Υ_{2} (t) ⩽ Υ_{1} (‖ x ‖) Υ_{2} (Π_{1} (‖ x ‖) Π_{2} (μ)) . \end{matrix}$ By Lemma 38 applied to $Υ_{2}$ , we obtain two polynomials ${\bar{P}}_{1}$ , ${\bar{P}}_{2}$ such that $0 < Υ_{2} (Π_{1} (‖ x ‖) Π_{2} (μ)) ⩽ ({\bar{P}}_{1} \circ Π_{1} (‖ x ‖)) ({\bar{P}}_{2} \circ Π_{2} (μ))$ . This and (6) imply that there is some function $Ψ_{1} \in A$ and some polynomial $Ψ_{2}$ such that $‖ y (t) ‖ ⩽ Ψ_{1} (‖ x ‖) Ψ_{2} (μ)$ . Using again Lemma 38, we can obtain polynomials $P_{1}, \dots, P_{k}, Q_{1}, Q_{2}$ such that $\begin{array}{l} ‖ y^{'} (t) ‖ & = ‖ p (y (t)) ‖ \\ ⩽ P_{1} (| y_{1} (t) |) \dots P_{k} (| y_{k} (t) |) \\ ⩽ P_{1} (‖ y (t) ‖) \dots P_{k} (‖ y (t) ‖) \\ ⩽ P_{1} (Ψ_{1} (‖ x ‖) Ψ_{2} (μ)) \dots P_{k} (Ψ_{1} (‖ x ‖) Ψ_{2} (μ)) \\ ⩽ (Q_{1} \circ Ψ_{1} (‖ x ‖)) (Q_{2} \circ Ψ_{2} (μ)) \end{array}$ for some polynomials $P_{1}, \dots, P_{k}, Q_{1}, Q_{2}$ which we assume without loss of generality to be increasing. We now have (recall that $t < Π_{1} (‖ x ‖) Π_{2} (μ)$ by assumption) $\begin{array}{l} {len}_{y} (0, t) & = \int_{0}^{t} ‖ y^{'} (u) ‖ d u \\ ⩽ \int_{0}^{t} (Q_{1} \circ Ψ_{1} (‖ x ‖)) (Q_{2} \circ Ψ_{2} (μ)) d u \\ = (Q_{1} \circ Ψ_{1} (‖ x ‖)) (Q_{2} \circ Ψ_{2} (μ)) t \\ < (Q_{1} \circ Ψ_{1} (‖ x ‖)) (Q_{2} \circ Ψ_{2} (μ)) Π_{1} (‖ x ‖) Π_{2} (μ) \\ ⩽ Λ_{1} (‖ x ‖) Λ_{2} (μ) \end{array}$ where $Λ_{1} \in A$ and $Λ_{2}$ is a polynomial. We have thus concluded that if $t < Π_{1} (‖ x ‖) Π_{2} (μ)$ , then ${len}_{y} (0, t) < Λ_{1} (‖ x ‖) Λ_{2} (μ)$ . This implies that if ${len}_{y} (0, t) ⩾ Λ_{1} (‖ x ‖) Λ_{2} (μ)$ , then it must be $t ⩾ Π_{1} (‖ x ‖) Π_{2} (μ)$ which, by assumption, implies that $‖ (y_{1} (t), \dots, y_{m} (t)) - f (x) ‖ ⩽ e^{- μ}$ , which proves the remaining second condition of Definition 36, thus proving that $f \in AL (A)$ .

For the reverse implication, let us suppose that $f \in AL (A)$ . We now want to show that $f \in AT S_{p} (A)$ . We first note that $f \in AL (A)$ does not necessarily imply that $f \in AT S_{p} (A)$ . For example, consider the following IVP $\begin{matrix} (7) & \{\begin{matrix} y_{1}^{'} = - y_{1} y_{2} \\ y_{2}^{'} = y_{2} \end{matrix} \{\begin{matrix} y_{1} (0) = e^{- 1} \\ y_{2} (0) = 1 . \end{matrix} \end{matrix}$ It is not difficult to see that its solution is $y_{2} (t) = e^{t}$ and $y_{1} (t) = e^{- e^{t}}$ . Hence $y_{1} (t)$ converges to the value 0. Note that $\begin{matrix} {len}_{y} (0, t) = \int_{0}^{t} ‖ y^{'} (u) ‖ d u = \int_{0}^{t} e^{u} d u = e^{t} - 1 . \end{matrix}$ Hence, if $t^{} ⩾ 0$ is such that ${len}_{y} (0, t^{}) ⩾ μ$ , we have $e^{t^{}} - 1 ⩾ μ$ which implies that $t^{} ⩾ ln (1 + μ)$ . When this happens we have that $\begin{matrix} | 0 - y_{1} (t) | ⩽ y_{1} (ln (1 + μ)) = e^{- e^{ln (1 + μ)}} ⩽ e^{- μ} . \end{matrix}$ In other words, the IVP (7) shows that the constant function 0 belongs to $ALP$ . On the other hand, the IVP (7) cannot be used to show that $0 \in ATSP$ , since when $t ⩾ Π (‖ x ‖, μ)$ for some polynomial Π, we will have $‖ y (t) ‖ = e^{t}$ which grows more quickly than any polynomial on t and therefore condition 3 of Definition 4 cannot be satisfied for any polynomial Υ. The solution to this problem is to rescale the time variable of the system (7) so that the condition ${len}_{y} (0, t^{}) ⩾ P (μ)$ , where P is a polynomial, can only achieved for a time $t^{}$ greater than a polynomial on μ, instead of a time which is subpolynomial (logarithmic, in the case of the preceding example).

Let us thus assume that $f \in AL (A)$ . This implies that there is some function $q \in GPVAL$ , a polynomial p, a function $Π_{1} \in A$ , and a polynomial $Π_{2}$ satisfying the conditions of Definition 36 where Π is given by $Π (‖ x ‖, μ) = Π_{1} (‖ x ‖) Π_{2} (μ)$ . Suppose that y is the solution of $y^{'} = p (y)$ , $y (0) = q (x)$ , with $y (t) \in R^{k}$ . We now wish to define a time rescaling τ such that if $\hat{y} (u) = y (τ (u))$ , we get that the condition ${len}_{\hat{y}} (0, u) ⩾ P (μ)$ , where P is a polynomial, only holds when $u ⩾ Q (μ)$ for some polynomial Q. We begin by noting that there is (see lemma 44 of [6]) a $GPVAL$ function $norm : R^{k} \to R$ with the property that $‖ x ‖ ⩽ norm (x) ⩽ ‖ x ‖ + 1 / 2$ . Furthermore, since $p \in GPVAL$ and $GPVAL$ is closed under composition, we conclude that $g = norm \circ p \in GPVAL$ , with $g : R^{k} \to R$ . By definition of $GPVAL$ , we conclude that there is a $d \times k$ matrix r consisting of polynomials with coefficients in $R_{P}$ , with $d ⩾ 1$ and $x_{0} \in R_{G}^{k}$ , $z_{0} \in R_{G}^{d}$ such that $g (x) = z_{1} (x)$ , where $z = (z_{1}, \dots, z_{d})$ is the solution of $\begin{matrix} (8) & J_{z} (x) = r (z), z (x_{0}) = z_{0} . \end{matrix}$ Now take $ψ : R \to R$ as $ψ (t) = g \circ y (t)$ . Note that due to condition 3 of Definition 36. $\begin{matrix} ψ (t) = g \circ y (t) = norm (p (y (t))) = norm (y^{'} (t)) ⩾ ‖ y^{'} (t) ‖ ⩾ 1 . \end{matrix}$ Next we define the function $\hat{ψ} : R \to R$ as $\hat{ψ} (u) = \int_{0}^{u} ψ (t) d t$ . Note that $ψ (t) ⩾ 1$ implies that $\hat{ψ} (u)$ is strictly increasing and thus admits an inverse function ${\hat{ψ}}^{- 1}$ . Furthermore, since $ψ (t) ⩾ 1$ , we have $\begin{matrix} (9) & \hat{ψ} (u) = \int_{0}^{u} ψ (t) d t ⩾ u . \end{matrix}$ Let us now take $\hat{y} (u) = y \circ {\hat{ψ}}^{- 1} (u)$ , $\hat{z} (u) = z \circ \hat{y} (u)$ , and $\hat{w} (u) = {({\hat{ψ}}^{- 1} (u))}^{'}$ where z is the solution of (8). We note that, by using the formula for obtaining the derivative of an inverse function, we obtain $\begin{matrix} (10) & \hat{w} (u) = {({\hat{ψ}}^{- 1} (u))}^{'} = \frac{1}{{\hat{ψ}}^{'} ({\hat{ψ}}^{- 1} (u))} = \frac{1}{ψ ({\hat{ψ}}^{- 1} (u))} \end{matrix}$ Using (8), we conclude that $\begin{array}{l} {\hat{y}}^{'} (u) = y^{'} ({\hat{ψ}}^{- 1} (u)) {({\hat{ψ}}^{- 1} (u))}^{'} = p (y ({\hat{ψ}}^{- 1} (u))) \hat{w} (u) = p (\hat{y} (u)) \hat{w} (u) \\ {\hat{z}}^{'} (u) = J_{z} (\hat{y} (u)) {\hat{y}}^{'} (u) = r (z (\hat{y} (u))) p (\hat{y} (u)) \hat{w} (u) = r (\hat{z} (u)) p (\hat{y} (u)) \hat{w} (u) . \end{array}$ Furthermore, from (10) we get $\begin{array}{l} {\hat{w}}^{'} (u) & = {(\frac{1}{ψ ({\hat{ψ}}^{- 1} (u))})}^{'} \\ = - \frac{ψ^{'} ({\hat{ψ}}^{- 1} (u)) \cdot {({\hat{ψ}}^{- 1} (u))}^{'}}{{(ψ ({\hat{ψ}}^{- 1} (u)))}^{2}} \\ = - ψ^{'} ({\hat{ψ}}^{- 1} (u)) \frac{1}{{(ψ ({\hat{ψ}}^{- 1} (u)))}^{3}} \\ (11) & = - {\hat{w}}^{3} (u) ψ^{'} ({\hat{ψ}}^{- 1} (u)) . \end{array}$ Now remark that ${(z \circ y)}^{'} (ζ) = J_{z} (y (ζ)) y^{'} (ζ) = r (z (y (ζ))) p (y (ζ))$ . Taking $ζ = {\hat{ψ}}^{- 1} (u)$ , we get $\begin{array}{l} {(z \circ y)}^{'} ({\hat{ψ}}^{- 1} (u)) & = r (z (y ({\hat{ψ}}^{- 1} (u)))) p (y ({\hat{ψ}}^{- 1} (u))) \\ = r (\hat{z} (u)) p (\hat{y} (u)) . \end{array}$ In particular, if $r_{(1)}$ denotes the first row of r and since $ψ (t) = g \circ y (t)$ and g is the first component of the solution of z in (8), we get that $ψ^{'} ({\hat{ψ}}^{- 1} (u)) = r_{(1)} (\hat{z} (u)) p (\hat{y} (u))$ . This last equality and (11) yield $\begin{array}{l} {\hat{y}}^{'} (u) = p (\hat{y} (u)) \hat{w} (u) \\ {\hat{z}}^{'} (u) = r (\hat{z} (u)) p (\hat{y} (u)) \hat{w} (u) \\ {\hat{w}}^{'} (u) = - {\hat{w}}^{3} (u) r_{(1)} (\hat{z} (u)) p (\hat{y} (u)) . \end{array}$

This shows that $\hat{y}, \hat{z}, \hat{w} \in GVAL$ . We now prove that this ODE, with the initial conditions $\begin{array}{l} \hat{y} (0) = y \circ {\hat{ψ}}^{- 1} (0) = y (0) = q (x) \\ \hat{z} (0) = z \circ \hat{y} (0) = z (q (x)) \\ \hat{w} (u) = \frac{1}{ψ ({\hat{ψ}}^{- 1} (0))} = \frac{1}{ψ (0)} = \frac{1}{g (y (0))} = \frac{1}{g (q (x))} \end{array}$ computes the function f according to Definition 4. First we remark that, due to the property that $‖ x ‖ ⩽ norm (x) ⩽ ‖ x ‖ + 1 / 2$ , we get $\begin{array}{l} ‖ y^{'} (t) ‖ = ‖ p (y (t)) ‖ ⩽ norm \circ p \circ y (t) = ψ (t) \\ ψ (t) = norm \circ p \circ y (t) ⩽ ‖ p (y (t)) ‖ + 1 / 2 = ‖ y^{'} (t) ‖ + 1 / 2 . \end{array}$ Therefore $\begin{array}{l} (12) & {len}_{y} (0, t) = \int_{0}^{t} ‖ y^{'} (u) ‖ d u ⩽ \int_{0}^{t} ψ (t) = \hat{ψ} (t) \\ (13) & \hat{ψ} (t) ⩽ \int_{0}^{t} ‖ y^{'} (u) ‖ + 1 / 2 d u ⩽ {len}_{y} (0, t) + \frac{t}{2} . \end{array}$ Now note that ${len}_{\hat{y}} (0, u) = \int_{0}^{u} ‖ {\hat{y}}^{'} (ζ) ‖ d ζ = \int_{0}^{u} ‖ p (\hat{y} (ζ)) \hat{w} (ζ) ‖ d ζ$ and by using the variable change $t = {\hat{ψ}}^{- 1} (ζ)$ , we get $ζ = \hat{ψ} (t)$ , $d ζ = {\hat{ψ}}^{'} (t) d t$ , and $\begin{array}{l} {len}_{\hat{y}} (0, u) & = \int_{0}^{{\hat{ψ}}^{- 1} (u)} ‖ p (\hat{y} (\hat{ψ} (t))) \hat{w} (\hat{ψ} (t)) ‖ {\hat{ψ}}^{'} (t) d t \\ = \int_{0}^{{\hat{ψ}}^{- 1} (u)} ‖ p (y (t)) {({\hat{ψ}}^{- 1})}^{'} (\hat{ψ} (t)) ‖ {\hat{ψ}}^{'} (t) d t \\ = \int_{0}^{{\hat{ψ}}^{- 1} (u)} ‖ p (y (t)) ‖ \frac{1}{{\hat{ψ}}^{'} ({\hat{ψ}}^{- 1} (\hat{ψ} (t)))} {\hat{ψ}}^{'} (t) d t \\ = \int_{0}^{{\hat{ψ}}^{- 1} (u)} ‖ p (y (t)) ‖ d t \\ (14) & = {len}_{y} (0, {\hat{ψ}}^{- 1} (u)) \\ ⩽ \hat{ψ} ({\hat{ψ}}^{- 1} (u)) (use (12)) \\ = u . \end{array}$ Using the last inequality and noting that $‖ \hat{y} (u) - \hat{y} (0) ‖ = ‖ \int_{0}^{u} {\hat{y}}^{'} (t) d t ‖ ⩽ \int_{0}^{u} ‖ {\hat{y}}^{'} (t) ‖ d t = {len}_{\hat{y}} (0, u)$ , we get that $\begin{array}{l} ‖ \hat{y} (u) ‖ & ⩽ ‖ \hat{y} (0) ‖ + ‖ \hat{y} (u) - \hat{y} (0) ‖ \\ ⩽ ‖ \hat{y} (0) ‖ + {len}_{\hat{y}} (0, u) \\ ⩽ ‖ \hat{y} (0) ‖ + u \\ ⩽ q (x) + u \end{array}$ and thus $\hat{y} (u)$ is bounded by a polynomial on x and u. Using this result together with the fact that the solution z of (8) belongs to $GPVAL$ , we conclude that $\hat{z} (u) = z \circ \hat{y} (u)$ is also bounded by a polynomial on x and u. Concerning the case of $\hat{w}$ , we note that due to (10) we have (recall that $ψ (t) ⩾ 1$ for any t) $\begin{matrix} ‖ \hat{w} (u) ‖ = ‖ \frac{1}{ψ ({\hat{ψ}}^{- 1} (u))} ‖ ⩽ 1 . \end{matrix}$ Therefore $‖ \hat{w} (u) ‖$ is also polynomially bounded. We have thus shown that condition 3 of Definition 4 holds. We now only have to show that condition 2 holds. Let $t ⩾ 2 Π (‖ x ‖, μ) = 2 Π_{1} (‖ x ‖) Π_{2} (μ)$ . We note that (9) yields us $\begin{matrix} {\hat{ψ}}^{- 1} (u) ⩽ u \end{matrix}$ This last inequality, together with (14) and (13), yields ${len}_{y} (0, u) ⩾ \hat{ψ} (u) - u / 2$ and $\begin{array}{l} {len}_{\hat{y}} (0, t) & = {len}_{y} (0, {\hat{ψ}}^{- 1} (t)) \\ ⩾ (\hat{ψ} ({\hat{ψ}}^{- 1} (t)) - \frac{{\hat{ψ}}^{- 1} (t)}{2}) \\ ⩾ t - \frac{t}{2} \\ = \frac{t}{2} \\ ⩾ Π (‖ x ‖, μ) \end{array}$ which implies condition 2 of Definition 4 due to condition 2 of Definition 36. This shows that $f \in AT S_{p} (A)$ . □

7. Application to the Grzegorczyk hierarchy

We start this section by briefly recalling the definition of the Grzegorczyk hierarchy. The Grzegorczyk hierarchy, originally proposed by Andrzej Gregorczyk in 1953 in [19], is a hierarchy of classes of functions from the naturals to the naturals, defined recursively. For our specific purpose, the first two levels of the hierarchy are not relevant, since they only include trivial functions such as addition and multiplication, which are obviously computable in polynomial time. The third level, which we indicate with the notation $ξ^{3}$ coincides with the set of all elementary functions. The definition of each level of the hierarchy for $n ⩾ 3$ involves the generator functions, $G_{n}$ , whose definition is also recursive. Let $G_{2} : N \to N$ be the exponential function $G_{2} (x) = 2^{x}$ and for $n ⩾ 2$ define: $G_{n + 1} (x) = G_{n}^{[x]} (1)$ , where the notation $G_{n}^{[x]} (1)$ stands for the iteration of the function $G_{n}$ for x times evaluated on the value 1, i.e. $G_{n}^{[0]} (x) = x$ and $G_{n}^{[k + 1]} (x) = G_{n} (G_{n}^{[k]} (x))$ . Then, formally [22, Definition VIII.8.12]:

Definition 40 (Grzegorczyk Hierarchy).

For $n ⩾ 3$ the nth level of the hierarchy, $ξ^{n}$ , is the smallest class of functions containing the zero function, the successor function, the projections, cut-off subtraction and $G_{n - 1}$ which is closed under composition, bounded sum and bounded product.

It can be shown that each level is properly included in the next one, $ξ^{n - 1} ⊊ ξ^{n} ⊊ ξ^{n + 1}$ , and that all together they constitute a hierarchy that satisfies $⋃_{n \in N} ξ^{n} = PR$ , where $PR$ is the set of primitive recursive functions. This is the reason way our analog characterization of the hierarchy naturally implies a characterization of the class of primitive recursive functions as well. Moreover, for any function $f \in ξ^{n}$ , there is some $m \in N$ such that $f (x) ⩽ G_{n - 1}^{[m]} (x)$ (see [22, Theorem VIII.7.8]. Although this theorem is proved for the case of the elementary functions $ξ^{3}$ , its proof generalizes to $ξ^{n}$ for any $n ⩾ 3$ ). We also note [22, Theorem VIII.8.14] that f belongs to $ξ^{n}$ iff it is computable in time belonging to $ξ^{n}$ . Combining the last two facts we conclude that f belongs to $ξ^{n}$ iff it is computable in time bounded by $G_{n - 1}^{[m]} (x)$ for some $m \in N$ . We will use this last characterization to characterize $ξ^{n}$ in the context of Theorem 35 to avoid having to deal with bounded sums and products.

7.1. Analog characterization of each level

In this section our objective is to use ODEs to characterize the classes $ξ^{n}$ , $n ⩾ 3$ , defining the Grzegorczyk hierarchy, with the use of Theorem 35.

However, a problem arises if one wants to use Theorem 35 to characterize $ξ^{n}$ for all $n ⩾ 3$ . When characterizing the classes $FP$ and $FEXPTIME$ , we had to rely on the classes $ATSP$ and $ATSE$ which are defined using the class $ATS$ with polynomial and exponential/polynomial bounds, respectively, which are defined over $R_{+} = [0, + \infty [$ . In the polynomial and exponential cases, this was not problematic since polynomial and exponential functions over $N$ admit a trivial extension to $R$ . This is not the case for the time bounds $G_{n - 1}^{[m]}$ for the Grzegorczyk hierarchy, which are defined using iteration and hence do not admit a trivial extension to $R$ . To solve this problem, in this section we show how we can obtain functions in $GVAL$ which essentially work as an extension of $G_{n - 1}^{[m]}$ . To achieve this purpose, we have to be able to iterate a function with ODEs over integers, since the definition of $G_{n - 1}^{[m]}$ relies on the use of iterations, as mentioned earlier.

With this objective in mind, we now present a construction to iterate functions with ODEs which is based on the ODE $\begin{matrix} (15) & y^{'} = c {(b - y)}^{3} ϕ (t) . \end{matrix}$ that was already studied in [9,13,17]. This ODE is called the targeting equation, for reasons that will become evident in a moment. In (15) we assume that $ϕ : R_{+} \to R_{+}$ is such that $\int_{0}^{\frac{1}{2}} ϕ (t) d t > 0$ (for example one could consider $ϕ (t) = sin (2 π t)$ as $\int_{0}^{\frac{1}{2}} sin (2 π t) d t = 1 > 0$ ), $b \in R$ is the target and $\begin{matrix} (16) & c ⩾ \frac{1}{2 γ^{2} \int_{0}^{1 / 2} ϕ (t) d t} \end{matrix}$ where $γ > 0$ is the targeting error. Let us consider separately two cases:

Let us first assume that $y (0) \neq b$ . Due to (16), we conclude that $\begin{matrix} γ^{2} ⩾ \frac{1}{2 c \int_{0}^{1 / 2} ϕ (t) d t} . \end{matrix}$ Since (15) is a separable equation, we get that $\begin{array}{l} \frac{1}{{(b - y (1 / 2))}^{2}} - \frac{1}{{(b - y (0))}^{2}} = 2 c \int_{0}^{1 / 2} ϕ (t) d t ⟹ \\ \frac{1}{2 c \int_{0}^{1 / 2} ϕ (t) d t} > {(b - y (1 / 2))}^{2} . \end{array}$ This implies that $γ > | b - y (1 / 2) |$ , i.e. $y (1 / 2)$ is γ-close to the value b (the target).

If $y (0) = b$ , then it is trivial to notice that $y (t) = b$ is the solution of (15) and thus the condition $γ > | b - y (1 / 2) |$ is true.

One can also consider the more general targeting ODE

\begin{matrix} (17) & z^{'} = c {(\overline{b} (t) - z)}^{3} ϕ (t), \end{matrix}

where

\bar{b} : R \to R

is a function with the property that

| \overline{b} (t) - b | ⩽ ρ

for all

t \in [0, 1 / 2]

, with

b \in R

(the target),

ρ ⩾ 0

, c satisfies (16) where

γ > 0

is the targeting error. A similar analysis (see [17] for more details) would yield that

| z (1 / 2) - b | < ρ + γ

, independently of the initial condition

y (0) \in R

We also note (to our knowledge, this was not mentioned in the literature before) that c might not be a fixed value, but instead some function $c : R \to R$ . In this case, if $c (t) ⩾ {(2 γ^{2} \int_{0}^{1 / 2} ϕ (t) d t)}^{- 1}$ for all $t \in [0, 1 / 2]$ , then $γ > | b - y (1 / 2) |$ . This follows from known facts of the ODE theory (see e.g. [20, pp. 511–514]) and from the conclusions that we obtained for the previous targeting ODE. A variable value for c has the advantage of allowing a dynamic targeting error, i.e. γ does not need to be fixed a priori and can be dynamically changed by updating the value of c. However, for the purpose of this paper, it is enough to assume that c is a fixed constant.

We will now show how the targeting ODE (17) can be used to obtain a function $f : R^{3} \to R^{2} \in GVAL$ such that the solution of the IVP $y^{'} = f (t, y)$ , $y (0) = (1, 1)$ satisfies $| y_{1} (t) - G_{2} (k) | ⩽ 1 / 4$ (i.e. $| y_{1} (t) - 2^{k} | ⩽ 1 / 4$ ) for all $t \in [k, k + 1 / 2]$ and $k \in N$ , where $y = (y_{1}, y_{2})$ . But before presenting this result, we have to present several auxiliary results. We begin by introducing the error-correcting function $l_{2}$ which was presented in [17, Lemma 9]. Its graph is depicted in Fig. 3.

Figure 3.

The graph of the function $l_{2}$ of Lemma 41 is depicted on the right side (the red graph assumes $x = 1.2$ while the blue graph assumes $x = 0.2$ ). The left graph depicts the function σ from Lemma 42.

Lemma 41.

Let $l_{2} : R^{2} \to [0, 1]$ be given by $l_{2} (x, y) = \frac{1}{π} arctan (4 x (y - 1 / 2)) + \frac{1}{2}$ . Suppose also that $a \in {0, 1}$ . Then, for any $\bar{a}, x \in R$ satisfying $| a - \bar{a} | ⩽ 1 / 4$ and $x > 0$ , we obtain $| a - l_{2} (\bar{a}, x) | < 1 / x$ .

We can see the function $l_{2}$ as a function which reduces the error around a $1 / 4$ -neighborhood of the integers 0 and 1 by an amount specified by $1 / x$ , where $x > 0$ is the first argument of $l_{2}$ .

Proceeding again as in [17], let us take the function s defined by $\begin{matrix} (18) & s (t) = \frac{1}{2} ({sin}^{2} (2 π t) + sin (2 π t)) . \end{matrix}$ The graph of this function is depicted in Fig. 4. A simple analysis shows that this function takes values between 0 and 1 in $[0, 1 / 2]$ and, in particular, between $3 / 4$ and 1 when $x \in [0.16, 0.34]$ , and between $- \frac{1}{8}$ and 0 on the time interval $[1 / 2, 1]$ . Therefore, if we take the $GVAL$ function $ϕ : R^{2} \to [0, 1]$ , defined by $\begin{matrix} (19) & ϕ (t, y) = l_{2} (s (t), y), \end{matrix}$ we conclude that $\int_{0}^{1 / 2} ϕ (t, y) d t > 3 / 4 \times (0.34 - 0.16) = 0.135 > 0$ (assuming that $y ⩾ 4$ ) and $| ϕ (t, y) | < 1 / y$ for all $t \in [1 / 2, 1]$ (i.e. y allows us to provide an upper bound $1 / y$ for $ϕ (t)$ in the time interval $[1 / 2, 1]$ ). Since ϕ has period 1 on t, we conclude that $\int_{k}^{k + 1 / 2} ϕ (t, y) d t > 0.135 > 0$ if $y ⩾ 4$ and $| ϕ (t, y) | < 1 / y$ for all $t \in [k + 1 / 2, k + 1]$ , where $k \in N$ is arbitrary.

Figure 4.

The graph of the function s defined on equation (18).

The following function σ is also from [17, Proposition 5].

Lemma 42.

Let $σ : R \to R$ be a function defined by $σ (x) = x - 0.2 sin (2 π x)$ . Then given $ε \in [0, 1 / 2)$ , there is some contracting factor $λ_{ε} \in (0, 1)$ such that, $\forall δ \in [- ε, ε]$ , $| σ (n + δ) - n | < λ_{ε} δ$ where $n \in Z$ is arbitrary.

The function σ behaves as a uniform contraction in a neighborhood of the integers $Z$ . Contrarily to the function $l_{2}$ which works only for the integer values 0 and 1, σ has the advantage of being a contraction around every integer. However, the rate of contraction is fixed for σ while it can be dynamically prescribed for $l_{2}$ . We remark, as noted in [17], that we can take $λ_{1 / 4} = 0.4 π - 1 \approx 0.2566371$ .

Let us now show how we can obtain a function $f : R^{3} \to R^{2} \in GVAL$ such that the solution of the IVP $y^{'} = f (t, y)$ , $y (0) = (1, 1)$ satisfies $| y_{1} (t) - 2^{k} | ⩽ 1 / 4$ for all $t \in [k, k + 1 / 2]$ and $k \in N$ , where $y = (y_{1}, y_{2})$ . This will be done by iterating the function $f : N \to N$ defined by $f (x) = 2 x$ via the ODE $\begin{matrix} (20) & \{\begin{matrix} y_{1}^{'} = c {(2 σ (y_{2}) - y_{1})}^{3} ϕ_{1} (t, y_{1}, y_{2}) \\ y_{2}^{'} = c {(σ (y_{1}) - y_{2})}^{3} ϕ_{2} (t, y_{1}, y_{2}) \end{matrix} \end{matrix}$ with initial condition $y_{1} (0) = y_{2} (0) = 1$ , where $\begin{matrix} (21) & \begin{matrix} ϕ_{1} (t, y_{1}, y_{2}) = ϕ (t, 16 c ({(2 σ (y_{2}) - y_{1})}^{4} + 1) + 4) \\ ϕ_{2} (t, y_{1}, y_{2}) = ϕ (- t, 16 c ({(σ (y_{1}) - y_{2})}^{4} + 1) + 4) \end{matrix} \end{matrix}$ and $c = 1000$ . Its (ideal) behavior is depicted in Fig. 5. We note that $ϕ_{1}$ is essentially the function ϕ from (19), where the main change is made on the upper bound for ϕ on the time intervals $[k + 1 / 2, k + 1]$ , where $k \in Z$ . In this case, noting that $| x^{3} | ⩽ x^{4} + 1$ for all $x \in R$ , we have that for any $t \in [k + 1 / 2, k + 1]$ we have $\begin{array}{l} | ϕ_{1} (t, y_{1}, y_{2}) | & ⩽ \frac{1}{16 c ({(2 σ (y_{2}) - y_{1})}^{4} + 1) + 4} \\ < \frac{1}{16 c {(2 σ (y_{2}) - y_{1})}^{3}} \end{array}$ which implies that $| y_{1}^{'} (t) | < 1 / 16$ whenever $t \in [k + 1 / 2, k + 1]$ for some $k \in Z$ . Furthermore, since $16 c ({(2 σ (y_{2}) - y_{1})}^{4} + 1) + 4 ⩾ 4$ , we conclude that $\int_{k}^{k + 1 / 2} ϕ_{1} (t, y_{1}, y_{2}) d t > 0.135 > 0$ and therefore that the first equation of (20) defines a targeting equation on the time interval $[0, 1 / 2]$ (or, more generally, on time intervals with the format $[k, k + 1 / 2]$ where $k \in Z$ ) with targeting error $1 / 16$ , since according to (16) $\begin{matrix} c = 1000 > \frac{1}{2 {(\frac{1}{16})}^{2} 0.135} > \frac{1}{2 {(\frac{1}{16})}^{2} \int_{0}^{1 / 2} ϕ_{1} (t, y_{1}, y_{2}) d t} . \end{matrix}$

Figure 5.

Iterating a function with an ODE. Here the dashed (red) and blue (solid) graphs represent the ideal behavior of $y_{1}$ and $y_{2}$ , respectively, in (20).

Using a similar argument we conclude that $| y_{2}^{'} (t) | < 1 / 16$ whenever $t \in [k, k + 1 / 2]$ for some $k \in Z$ and that the second equation of (20) defines a targeting equation on the time interval $[1 / 2, 1]$ (or, more generally, on time intervals with the format $[k + 1 / 2, k + 1]$ where $k \in Z$ ) with targeting error $1 / 16$ .

Let us now analyze in more detail the ODE (20). When $t \in [0, 1 / 2]$ , we have that $| y_{2}^{'} (t) | ⩽ 1 / 16$ , which further implies that $| y_{2} (t) - 1 | ⩽ 1 / 32$ when $t \in [0, 1 / 2]$ , since $\begin{array}{l} | y_{2} (t) - y_{2} (0) | & = | \int_{0}^{t} y_{2}^{'} (t) d t | \\ ⩽ \int_{0}^{t} | y_{2}^{'} (t) | d t \\ ⩽ (\frac{1}{2} - 0) \frac{1}{16} = \frac{1}{32} . \end{array}$ Now notice that, since $| y_{2} (t) - 1 | ⩽ 1 / 32$ , then $\begin{array}{l} | 2 σ (y_{2} (t)) - 2 \cdot 1 | & ⩽ 2 | y_{2} (t) - 1 | \\ ⩽ 1 / 16. \end{array}$ Hence, since the equation for $y_{1}$ in (20) defines a targeting equation with targeting error $γ = 1 / 16$ , we get that $| y_{1} (1 / 2) - 2^{1} | < 1 / 16 + 1 / 16 = 1 / 8$ . Now, on the next half-unit interval, we have that $| y_{1}^{'} (t) | ⩽ 1 / 16$ which implies that $| y_{1} (t) - 2^{1} | < 1 / 8 + 1 / 32 = 5 / 32$ for all $t \in [1 / 2, 1]$ . This implies that $| σ (y_{1} (t)) - 2^{1} | ⩽ λ_{1 / 4} | y_{1} (t) - 2^{1} | < 1 / 24$ for all $t \in [1 / 2, 1]$ . Hence $y_{2}$ will become a targeting equation in the time interval $[1 / 2, 1]$ with targeting error $γ = 1 / 16$ and we will have $| y_{2} (1) - 2^{1} | < 1 / 24 + 1 / 16 < 1 / 8$ . Now the procedure repeats itself in subsequent intervals. For example, when $t \in [1, 3 / 2]$ , we will have that $| y_{2}^{'} (t) | ⩽ 1 / 16$ , which further implies that $| y_{2} (t) - 2^{1} | < 1 / 8 + 1 / 32 < 5 / 32$ when $t \in [1, 3 / 2]$ . By a similar argument as in the previous case, we conclude that $\begin{array}{l} | 2 σ (y_{2} (t)) - 2 \cdot 2^{1} | & ⩽ 2 λ_{1 / 4} | y_{2} (t) - 2^{1} | \\ ⩽ 2 λ_{1 / 4} 5 / 32 \\ ⩽ 1 / 12, \end{array}$ and since the equation for $y_{1}$ in (20) defines a targeting equation with targeting error $γ = 1 / 16$ , we get that $| y_{1} (3 / 2) - 2^{2} | < 1 / 12 + 1 / 16 = 7 / 48$ . On the next half-unit interval, we have that $| y_{1}^{'} (t) | ⩽ 1 / 16$ which implies that $| y_{1} (t) - 2^{2} | < 7 / 48 + 1 / 32 = 17 / 96$ for all $t \in [3 / 2, 2]$ . This implies that $| σ (y_{1} (t)) - 2^{2} | < 1 / 22$ for all $t \in [3 / 2, 2]$ . Hence $y_{2}$ will become a targeting equation in the time interval $[3 / 2, 2]$ with targeting error $γ = 1 / 16$ and we will have $| y_{2} (2) - 2^{2} | < 1 / 22 + 1 / 16 < 1 / 8$ . The procedure repeats itself on subsequent intervals and we conclude that $\begin{matrix} | y_{2} (t) - G_{2} (k) | ⩽ 1 / 4 for all t \in [k, k + 1 / 2] and k \in N . \end{matrix}$

This result can be generalized as shown in the following theorem.

Theorem 43.

Given the function $G_{n} : N \to N$ , $n = 2, 3, \dots$ , there is an IVP $y^{'} = f_{n} (t, y)$ , $y (0) = y_{0}$ , where $f_{n} \in GVAL$ and $y_{0} \in N^{l}$ , such that $| y_{1} (t) - G_{n} (k) | ⩽ 1 / 4$ for all $t \in [k, k + 1 / 2]$ and $k \in N ∖ {0}$ .

Proof.

The proof is done by induction on n. The base case was performed just before the proof of this theorem (note that $y_{2}$ in the above argument corresponds to $y_{1}$ in the context of this theorem).

Now we go to the induction step. Suppose that $y^{'} = f_{n} (t, y)$ , $y (0) = y_{0}$ satisfies the conditions of the theorem. Then we want to show that there is a system $y^{'} = f_{n + 1} (t, y)$ which simulates $G_{n + 1}$ in the sense mentioned in the theorem. Consider the ODE $\begin{matrix} (22) & \{\begin{matrix} z^{'} = f_{n} (τ, y) τ^{'} = c f_{n} (τ, y) {(w + 1 / 4 - τ)}^{3} θ_{1} (t, τ, w) \\ τ^{'} = c {(w + 1 / 4 - τ)}^{3} θ_{1} (t, τ, w) \\ w^{'} = c {(σ (z_{1}) - w)}^{3} θ_{2} (t, z_{1}, w) \end{matrix} \end{matrix}$ with initial condition $z (0) = y_{0}$ , $τ (0) = 0$ , $w (0) = 1$ where $\begin{array}{l} θ_{1} (t, τ, w) = ϕ (t, 16 c ({(w + 1 / 4 - τ)}^{4} + 1) + 4) \\ θ_{2} (t, z_{1}, w) = ϕ (- t, 16 c ({(σ (z_{1}) - w)}^{4} + 1) + 4) \end{array}$ and $c = 5000$ . Its (idealized) behavior is depicted in Fig. 6. We note that $θ_{1}$ and $θ_{2}$ behave like $ϕ_{1}$ and $ϕ_{2}$ of (21), respectively. By using arguments similar to those presented after (21), we conclude that: (i) $| τ^{'} (t) | ⩽ 1 / 16$ whenever $t \in [k + 1 / 2, k + 1]$ for some $k \in Z$ and the equation for τ in (22) defines a targeting equation on time intervals with the format $[k, k + 1 / 2]$ where $k \in Z$ , with targeting error $1 / 32$ and (ii) $| w^{'} (t) | ⩽ 1 / 16$ whenever $t \in [k, k + 1 / 2]$ for some $k \in Z$ and that the equation for w in (22) defines a targeting equation on time intervals with the format $[k + 1 / 2, k + 1]$ where $k \in Z$ , with targeting error $1 / 32$ .

Figure 6.

Iterating the function $G_{n}$ with an ODE. Here the dashed (red), solid (blue), and dotdashed (green) graphs represent the ideal behavior of $z_{1}$ , w, and τ, respectively, in (22).

We note also that, by construction $z (t) = y (τ (t))$ , where y is the solution of $y^{'} = f_{n} (t, y)$ , $y (0) = y_{0}$ . Therefore the value of z only depends on the value of τ. We now have to analyze the behaviour of τ and w. This simulation works again in half-unit time intervals. We break the following analysis in parts, each one related to one half-unit interval.

On the first half-unit interval, where $t \in [0, 1 / 2]$ , we have that w is (almost) constant, since $| w^{'} (t) | ⩽ 1 / 16$ , which implies that $| w (t) - 1 | ⩽ 1 / 32$ for all $t \in [0, 1 / 2]$ . Therefore, since the equation governing the behaviour of τ in this time interval $[0, 1 / 2]$ is a targeting equation, we conclude that $| τ (1 / 2) - (1 + 1 / 4) | ⩽ 1 / 32 + 1 / 32 = 1 / 16$ , since the targeting error is $1 / 32$ . This gives that $τ (1 / 2) \in [1 + 3 / 16, 1 + 5 / 16]$ .

We now proceed with the second time interval. Since $| τ^{'} (t) | ⩽ 1 / 16$ in the time interval $[1 / 2, 1]$ we conclude that $τ (t) \in [1 + 1 / 8, 1 + 3 / 8] \subseteq [1, 3 / 2]$ for $t \in [1 / 2, 1]$ . This implies, by the induction hypothesis, that $z (t) = y (τ (t))$ is such that $| z_{1} (t) - G_{n} (1) | ⩽ 1 / 4$ for all $t \in [1 / 2, 1]$ . Note that $| σ (z_{1} (t)) - G_{n} (1) | ⩽ λ_{1 / 4} | z_{1} (t) - G_{n} (1) | ⩽ λ_{1 / 4} / 4 < 1 / 15$ for all $t \in [1 / 2, 1]$ . Since the targeting error is $1 / 32$ , we conclude that $| w (1) - G_{n} (1) | ⩽ 1 / 32 + 1 / 15$ .

Now the procedure repeats itself on the time interval $[1, 3 / 2]$ . On this interval, we have $| w^{'} (t) | < 1 / 16$ and thus $| w (t) - G_{n} (1) | = | w (t) - G_{n} (1) | ⩽ 1 / 32 + 1 / 15 + 1 / 32 = 31 / 240$ for all $t \in [1, 3 / 2]$ . Therefore, the targeting equation for τ yields that $| τ (3 / 2) - (G_{n} (1) + 1 / 4) | ⩽ 31 / 240 + 1 / 32 = 77 / 480$ . Since $| τ^{'} (t) | ⩽ 1 / 16$ in the time interval $[3 / 2, 2]$ , we have that $| τ (t) - (G_{n} (1) + 1 / 4) | ⩽ 77 / 480 + 1 / 16 = 107 / 480 < 1 / 4$ and therefore $τ (t) \in [G_{n} (1), G_{n} (1) + 1 / 2]$ for $t \in [3 / 2, 2]$ . This implies, by the induction hypothesis, that $z (t) = y (τ (t))$ is such that $| z_{1} (t) - G_{n} (G_{n} (1)) | = | z_{1} (t) - G_{n + 1} (2) | ⩽ 1 / 4$ for all $t \in [3 / 2, 2]$ . Note that $| σ (z_{1}) - G_{n + 1} (2) | ⩽ λ_{1 / 4} | z_{1} (t) - G_{n + 1} (2) | ⩽ λ_{1 / 4} / 4 < 1 / 15$ for all $t \in [3 / 2, 2]$ . Considering the targeting equation for w in $[3 / 2, 2]$ , we conclude that $| w (2) - G_{n + 1} (2) | ⩽ 1 / 32 + 1 / 15$ since the targeting error is $1 / 32$ . Notice again that, for all $t \in [2, 5 / 2]$ , since $| w^{'} (t) | < 1 / 16$ , we have $| w (t) - G_{n + 1} (2) | ⩽ 1 / 32 + 1 / 15 + 1 / 32 = 31 / 240 < 1 / 4$ .

By repeating this procedure on subsequent intervals and by considering w as the variable $y_{1}$ of the statement of the theorem, we conclude the desired result. □

We now know from the previous theorem that each function $G_{n}$ admits an $GVAL$ -extension $t_{n}$ in the sense of Theorem 43. In other words, there is some $GVAL$ function $t_{n}$ such that $| t_{n} (t) - G_{n} (k) | ⩽ 1 / 4$ for all $t \in [k, k + 1 / 2]$ and $k \in N ∖ {0}$ .

Definition 44.

For each $n ⩾ 3$ , we define the class $T^{n}$ as the smallest class of functions $f : R \to R$ containing $t_{n - 1}$ , the identity, $R_{G}$ , and which is closed under sum, difference, product, and composition for $n ⩾ 3$ .

Note that this definition of $T^{n}$ implies that condition 1 and 2 in the list of Definition 33 are immediately satisfied (for condition 2 remark that $T^{n}$ includes $t_{2}$ which grows exponentially fast, and hence which grows more quickly than any polynomial). Furthermore, it is also not difficult to see that condition 4 is satisfied. Indeed, we have that $t_{n - 1} (k) ⩽ G_{n - 1} (k) + 1$ and since $ξ^{n}$ is closed under composition and arithmetic operations, this shows that any function in $T^{n}$ is dominated, over the naturals, by a function in $ξ^{n}$ (note that all function in $ξ^{n}$ are time-constructible). Reciprocally, if $f \in ξ^{n}$ , then there is some $m \in N$ such that $f (k) ⩽ G_{n - 1}^{[m]} (k) ⩽ t_{n - 1} (\dots t_{n - 1} (k) + 1 \dots) + 1$ , where $t_{n - 1} + 1$ is composed m times. Since $(t_{n - 1} + 1) \circ (t_{n - 1} + 1) \circ \dots \circ (t_{n - 1} + 1) \in T^{n}$ , we conclude that condition 4 is satisfied. Moreover, this also shows the following lemma.

Lemma 45.

$FTIME (T^{n}) = FTIME (ξ^{n}) = ξ^{n}$ .

It is then left to prove condition 3, which requires that given any function $f \in ξ^{n}$ there is a function $g \in T^{n}$ such that $f ⩽ g$ and $g \in AT S_{p} (T^{n})$ , for all $n ⩾ 3$ . We will now show that this condition is satisfied, in a multi-step argument.

From the above argument, we have just showed by means of the above proof of Theorem 43 that each $t_{n}$ is generable, meaning that $t_{n} \in GVAL$ for each $n ⩾ 3$ . We now show that (i) we have $T^{n} \subseteq GVAL (T^{n})$ , where $\begin{matrix} GVAL (T^{n}) = ⋃_{g \in T^{n}} GVAL (g), \end{matrix}$ and (ii) $GVAL (T^{n}) \subseteq AT S_{p} (T^{n})$ . This will show condition 3 of Definition 33, since any function $f \in ξ^{n}$ is bounded by a function in $T^{n}$ , as we have already seen.

To show condition (i), we first present the two following lemmas taken from [6, Lemma 24, Corollary 26]:

Lemma 46 ([6], Arithmetic on bounded generable functions).

Let $d, l, n, m \in N$ , $sp, \overline{sp} : R_{+} \to R_{+}$ , $f : \subseteq R^{d} \to R^{n} \in GVAL (sp)$ and $g : \subseteq R^{l} \to R^{m} \in GVAL (\overline{sp})$ . Then:

$f + g, f - g \in GVAL (sp + \overline{sp})$ over $dom f \cap dom g$ if $d = l$ and $n = m$

$f \cdot g \in GVAL (max (sp, \overline{sp}, sp \cdot \overline{sp}))$ if $d = l$ and $n = m$

$f \circ g \in GVAL (max (\overline{sp}, sp \circ \overline{sp}))$ if $m = d$ and $g (dom g) \subseteq dom f$

Lemma 47 ([6], Generable functions are closed under ODE).

Let $d \in N$ , $J \subseteq R$ an interval, $sp, \overline{sp} : R_{+} \to R_{+}$ , $f : \subseteq R^{d} \to R^{d} \in GVAL (sp)$ , $t_{0} \in K \cap J$ and $y_{0} \in R_{G}^{d} \cap dom f$ . Assume there exists $y : J \to dom f$ satisfying for all $t \in J$ :

$y (t_{0}) = y_{0}$

$y^{'} (t) = f (y (t))$

$‖ y (t) ‖ ⩽ \overline{sp} (t)$

Then

y \in GVAL (max (\overline{sp}, sp \circ \overline{sp}))

and is unique.

Since Lemmas 46 and 47 show closure of $GVAL (T^{n})$ under the operations used to define $T^{n}$ , to show (i), i.e. that $T^{n} \subseteq GVAL (T^{n})$ it is enough to show that $t_{n} \in GVAL (T^{n + 1})$ (note that the identity and all elements of $R_{G}$ belong to $GPVAL \subseteq GVAL (T^{n})$ ).

First, define $T^{2} = {p ∣ p \in poly}$ as the class of polynomials over $R_{G}$ . We show that the above proof of Theorem 43 implies that $f_{n} \in GVAL (T^{2})$ and $t_{n} = y_{1} \in GVAL (T^{n + 1})$ for each $n ⩾ 2$ , where $f_{n}$ and $y_{1}$ are defined in the statement of this theorem. This result can be showed by induction on n thanks to the closure by composition of each class $T^{n}$ .

To show that $f_{n} \in GVAL (T^{2})$ and $t_{n} = y_{1} \in GVAL (T^{n + 1})$ for each $n ⩾ 2$ , we proceed by induction. For the base case $n = 2$ , consider $f_{2}$ as defined in (20) and note that $f_{2} \in GVAL (T^{2}) = GPVAL$ since all the right-hand terms in the system (20) belong to $GPVAL$ . Moreover, note that, from the arguments which follow (20), the norm of the solution y of that dynamical system is bounded by a function ${sp}_{2} \in T^{3}$ , where ${sp}_{2} (k) = t_{2} (k + 1)$ . Therefore, since $T^{2} \subset T^{3}$ and each class is closed by composition, applying Lemma 47 above yields $y \in GVAL (T^{3})$ and, in particular, $t_{2} = y_{1} \in T^{3}$ . This proves the base case.

Let us now assume that $f_{n} \in GVAL (T^{2})$ and that $t_{n} \in GVAL (T^{n + 1})$ . We now want to show that $f_{n + 1} \in GVAL (T^{2})$ and $t_{n + 1} \in GVAL (T^{n + 2})$ . First we note that $f_{n + 1}$ is defined as the function used in the right-hand side of the ODE (22) and applied to the variables z, τ, and w. Since $f_{n + 1}$ is built using arithmetic operations, elements of $R_{G}$ , and the functions $f_{n}, θ_{1}, θ_{2}, σ \in GVAL (T^{2})$ , we conclude by Lemma 46 that $f_{n + 1} \in GVAL (T^{2})$ . Also, from the analysis done in the proof of Theorem 43, we conclude that the solution $x (t)$ of (22) is bounded by $t_{n + 1} (t + 1) \in GVAL (T^{n + 2})$ , which shows by Lemma 47 that x and hence $t_{n + 1}$ belongs to $GVAL (T^{n + 2})$ .

At this point we have shown that $t_{n} \in GVAL (T^{n + 1})$ and hence we have proved (i). Now the last element left is condition (ii), which follows from the following theorem, that is a variant of Theorem 11, but now applied to $T^{n}$ :

Theorem 48.
If $f \in GVAL (T^{n})$ has a star domain with a generable vantage point, then we have $f \in ATS (T^{n})$ .

We note that (necessarily univariate) functions of $GVAL (T^{n + 1})$ are always defined at any point of $R_{+} = [0, + \infty [$ . This implies that such functions have a vantage point over this domain (e.g. 0 or 1 may be used as vantage points). Hence, we can conclude from Theorem 48 that if $f \in GVAL (T^{n})$ , then $f \in ATS (T^{n})$ , which immediately implies condition 3 of Definition 33. To prove Theorem 48, we need another result from [6, Proposition 28].
Lemma 49.
Let $sp : R_{+} \to R_{+}$ , $f \in GVAL (sp)$ . There exists a polynomial $q : R \to R$ , with coefficients in $R_{G}$ , such that for any $x_{1}, x_{2} \in dom f$ then $‖ f (x_{1}) - f (x_{2}) ‖ ⩽ ‖ x_{1} - x_{2} ‖ q (sp (max (‖ x_{1} ‖, ‖ x_{2} ‖)))$ .

This lemma tells us that each function in $GVAL (sp)$ has a modulus of continuity expressed by the function $q \circ sp$ where q is a polynomial; therefore, since $GVAL (T^{n})$ is closed by composition with polynomials, this implies that each function in $GVAL (T^{n})$ has modulus of continuity in $T^{n}$ .
Proof of Theorem 48.
Let $f : R_{+} \to R$ be a function in $GVAL (T^{n})$ and let $0 \in R_{G}^{n} \cap dom f$ be a generable vantage point. By definition of $GVAL (T^{n})$ we know that there exist a function $sp \in T^{n}$ , a polynomial p, two initial points $t_{0}$ , $y_{0}$ and a solution y that satisfy Definition 2. In particular, y is the solution of the ODE $y^{'} = p (y)$ and we have $y (t) ⩽ sp (t)$ for all $t ⩾ 0$ . Moreover, since the point 0 belongs to the generable field $R_{G}$ , and by definition of a generable field, we know that $y (0) \in R_{G}^{d}$ (note that since $y \in GVAL (T^{n})$ , we have that y is defined over $[0, + \infty [$ and hence $y (0)$ is defined). Let $x \in dom f$ , which implies that $x ⩾ 0$ , and consider the system: $\begin{matrix} (23) & \{\begin{matrix} x (0) = x \\ γ (0) = 0 \\ z (0) = y (0) \end{matrix} \{\begin{matrix} x^{'} (t) = 0 \\ γ^{'} (t) = x (t) - γ (t) \\ z^{'} (t) = p (z (t)) (x (t) - γ (t)) \end{matrix} \end{matrix}$ We notice that all the differential equations of (23) are expressed as polynomials of the variables $x (t)$ , $γ (t)$ , $z (t)$ . It is immediate to check that the variable $x (t)$ is constant and takes the value $x ⩾ 0$ . This implies that the ODE for γ is separable and can be explicitly solved, yielding $γ (t) = x (1 - e^{- t})$ . Hence $γ (t) \subseteq [0, x] \subseteq dom f$ for all $t ⩾ 0$ . It is also not difficult to directly check that $z (t) = y (γ (t))$ is the solution of the last ODE of (23), which also implies that $‖ z (t) ‖ ⩽ ‖ y (γ (t)) ‖ ⩽ sp (γ (t)) ⩽ sp (x)$ for all $t ⩾ 0$ assuming, without loss of generality, that $sp$ is an increasing function. This shows that $‖ (x (t), γ (t), z (t)) ‖ ⩽ \overline{sp} (x)$ , where $\overline{sp}$ is some function satisfying $\overline{sp} (x) ⩾ max (x, sp (x))$ which belongs to $T^{n}$ . This shows that $\overline{sp} \in T^{n}$ defines a space bound for the solution of (23), where the only argument of $\overline{sp}$ is the initial condition x of (23) (there is no dependence of $\overline{sp}$ on the time variable t). Note also that, due to Definition 2 and because the first m components of the solution $y (t)$ of $y^{'} = p (y)$ yield $f (t)$ , we have $(z_{1} (t), \dots, z_{m} (t)) = (y_{1} (γ (t)), \dots, y_{m} (γ (t))) = f (γ (t))$ and this last value converges to $f (x)$ by continuity of f.

Therefore, according to Definition 31, we have just shown that the second condition of this definition is satisfied when using (23) to approach $f (x)$ , i.e. we can take $Υ (‖ x ‖, t) = Υ_{1} (‖ x ‖) Υ_{2} (t)$ in this definition, where $Υ_{1} = \overline{sp} \in T^{n}$ and $Υ_{2} (t) = 1$ . We now just have to show the first condition of that definition. In other words, we have to show that for any $μ > 0$ , there is some $Π_{1} \in T^{n}$ and a polynomial function $Π_{2}$ such that if $t ⩾ Π_{1} (‖ x ‖) Π_{2} (μ)$ then $‖ (z_{1} (t), \dots, z_{m} (t)) - f (x) ‖ ⩽ e^{- μ}$ .

By Lemma 49, we know that there exists $h \in T^{n}$ such that, $\forall x_{1}, x_{2} ⩾ 0$ , we have: $\begin{matrix} ‖ f (x_{1}) - f (x_{2}) ‖ ⩽ ‖ x_{1} - x_{2} ‖ h (max (‖ x_{1} ‖, ‖ x_{2} ‖)) . \end{matrix}$ In particular, since $‖ γ (t) ‖ ⩽ x$ and $(z_{1} (t), \dots, z_{m} (t)) = f (γ (t))$ , we get $\begin{array}{l} ‖ f (x) - (z_{1} (t), \dots, z_{m} (t)) ‖ & = ‖ f (x) - f (γ (t)) ‖ \\ ⩽ ‖ x - γ (t) ‖ h (x) \\ = x e^{- t} h (x) \end{array}$ Hence, we have that if $\begin{matrix} t ⩾ x + h (x) + μ \end{matrix}$ then $\begin{array}{l} ‖ f (x) - (z_{1} (t), \dots, z_{m} (t)) ‖ & ⩽ x e^{- t} h (x) \\ ⩽ x e^{- (x + h (x) + μ)} h (x) \\ ⩽ \frac{x}{e^{x}} \frac{h (x)}{e^{h (x)}} e^{- μ} \\ ⩽ e^{- μ} . \end{array}$ By taking $Π_{1} (x) = 1 + x + h (x)$ and $Π_{2} (μ) = (1 + μ)$ , we easily see that, by assuming without loss of generality that $x, h (x), μ ⩾ 0$ , that we have $Π_{1} (x) Π_{2} (μ) ⩾ x + h (x) + μ$ and $Π_{1} \in T^{n}$ and $Π_{2}$ is a polynomial. This implies from the above argument that if $t ⩾ Π_{1} (x) Π_{2} (μ)$ , then $‖ f (x) - (z_{1} (t), \dots, z_{m} (t)) ‖ ⩽ e^{- μ}$ , thus showing that $f \in AT S_{p} (T^{n})$ . □

Hence, the classes $T^{n}$ defined above satisfy all the four conditions in the list of Definition 33, and therefore Theorem 50 holds. We then have the following result.
Theorem 50 (Analog characterization of the Grzegorczyk hierarchy).

Let $n \in N$ . Let $f : Γ^{*} \to Γ^{*}$ , then $f \in ξ^{n}$ if and only if is emulable under $ATS (T^{n})$ .

8. Characterizing the class $EXPTIME$

Until now we have described connections between analog classes of functions (e.g. $ATSE$ ) and discrete classes of computable functions such as $FEXPTIME$ . At this point a very natural question arises: is it possible to extend these results to discrete classes of computable sets as well, such as $EXPTIME$ ? The answer to this important question is yes, and the latter can be done by providing a criterion of acceptance/rejection in the definition of the analog classes. Indeed, we will not require any convergence of the dynamical system, but instead that the solution of the PIVP, with initial condition dependent from the input word as usual, reaches an accepting or rejecting region in a certain amount of time to determine whether the input word w belongs or not to the considered set. This modification will allow solutions of ODEs to decide a certain class of sets of words over the considered alphabet Γ, and therefore it will be possible to introduce new classes of sets closely related to $EXPTIME$ . A very similar procedure has been followed by the authors of [5] to extend their results obtained for polynomial computable functions to the complexity class P.

8.1. Definitions of the analog classes

We start with a definition of a new class of sets, that we will call Exponential-Analog-Recognizable, or $EAR$ .

Definition 51 (EAR).

A language $L \subseteq Γ^{*}$ is called exponential analog recognizable if there exist a vector q of bivariate polynomials and a vector p of polynomials with d variables, both with coefficients in $R_{G}$ , and an exponential boundary function $Π : R \to R$ such that for all $w \in Γ^{*}$ there exists (a unique) $y : R \to R^{d}$ satisfying for all $t ⩾ 0$ (see Fig. 7):

$y (0) = q (Ψ_{k} (w))$ and $y^{'} (t) = p (y (t))$ ;

if $| y_{1} (t) | ⩾ 1$ then $| y_{1} (u) | ⩾ 1$ for all $u ⩾ t$ ;

if $w \in L$ (respectively, $w \notin L$ ) and ${len}_{y} (0, t) ⩾ Π (| w |)$ then $y_{1} (t) ⩾ 1$ (respectively, $y_{1} (t) ⩽ - 1$ );

${len}_{y} (0, t) ⩾ t$ , where ${len}_{y} (0, t)$ represents the length of the solution y in the interval $[0, t]$ .

Figure 7.

Graphical depiction of Definition 51. A word w is accepted (rejected) if after following the solution curve for a length exponential in $| w |$ the first component $y_{1}$ of the solution curve takes values $⩾ 1$ ( $⩽ - 1$ , respectively).

Informally, the definition above states that a language L belong to the $EAR$ class if there exists a dynamical system, whose evolution is ruled by a polynomial differential equation, such that, for each word of the alphabet representing a starting point for the system, the trajectory described by the solution enters either the accepting region or the rejecting region as soon as the length of the solution is exponential on the size of the input word. Specifically, condition (1) defines the dynamical system, condition (2) ensures stability once the decision is taken, condition (3) enforces the entrance within the accepting or rejecting region and condition (4) excludes from the classes pathological cases in which the evolution of the system is too slow.

8.2. Equivalence relation between

EXPTIME

and

EAR

We can now state the equivalence result related to the $EAR$ class:

Theorem 52 (EXPTIME equivalence).

For any language $L \subseteq Γ^{*}$ , $L \in EXPTIME$ if and only if L is exponential analog recognizable.

Proof.
Let $L \in EXPTIME$ . Then there exists a function $f \in FEXPTIME$ and two distinct symbols $\bar{0}, \bar{1} \in Γ$ such that for any $w \in Γ^{}$ , $f (w) = \bar{1}$ if $w \in L$ and $f (w) = \bar{0}$ otherwise. By Theorem 29 there is some $g \in ATSE$ that emulates f. Since for any $w \in Γ^{}$ one has $f (w) \in {\bar{0}, \bar{1}}$ , this implies that $Ψ_{k} (f (w)) = (k^{- 1} γ (\bar{0}), 1)$ or $Ψ_{k} (f (w)) = (k^{- 1} γ (\bar{1}), 1)$ . Next define a function $res : {k^{- 1} γ (\bar{0}), k^{- 1} γ (\bar{1})} \to {- 2, 2}$ which is defined by $res (k^{- 1} γ (\bar{0})) = - 2$ and $res (k^{- 1} γ (\bar{1})) = 2$ . Using Lagrange interpolation, by Proposition 12 we can extend $res$ to a function $L_{res} \in ATSP$ which extends $res$ to $R$ . Now take $g^{} (x) = L_{res} (g_{1} (x))$ , where $g (x) = (g_{1} (x), g_{2} (x))$ . Since $g^{}$ is the composition of an $ATSP$ function with an $ATSE$ function, by Theorem 28 we conclude that $g^{} \in ATSE$ . Moreover, $g^{} (Ψ_{k} (w)) = 2$ if $w \in L$ and $g^{} (Ψ_{k} (w)) = - 2$ if $w \notin L$ .

From the definition of the $ATSE$ class we know that $g^{} \in ATSE (Π_{1} Π_{2}, Υ_{1} Υ_{2})$ for some exponential boundary functions $Π_{1}$ , $Υ_{1}$ and some polynomials $Π_{2}$ , $Υ_{2}$ with corresponding d, p, q as parameters and functions defining the dynamical system. Assume, without loss of generality, that these four functions used as boundaries are increasing functions. Let $w \in Γ^{}$ and consider the following system, where v is a constant variable used to store the input and in particular the input length $(v_{2} (t) = | w |)$ , $τ (t) = t$ is used to keep the time, z is the decision variable, and $τ^{} = Π_{1} (v_{2} (t)) Π_{2} (ln 2) = Π_{1} (| w |) Π_{2} (ln 2)$ $\begin{matrix} \{\begin{matrix} y (0) = q (Ψ_{k} (w)) \\ v (0) = Ψ_{k} (w) \\ z (0) = 0 \\ τ (0) = 0 \end{matrix} \{\begin{matrix} y^{'} (t) = p (y (t)) \\ v^{'} (t) = 0 \\ z^{'} (t) = {lxh}_{[0, 1]} (τ (t) - τ^{}, 1 + τ (t), y_{1} (t) - z (t)) \\ τ^{'} (t) = 1 \end{matrix} \end{matrix}$ where y is the solution of the ODE computing $g^{}$ . Let $t \in [0, τ^{}]$ . Then, by the properties of $lxh$ (see Proposition 14), one has $| z^{'} | ⩽ e^{- 1 - t}$ . This implies that $\begin{array}{l} z (t) = \int_{0}^{t} z^{'} (u) d u \Rightarrow \\ (24) & | z (t) | ⩽ \int_{0}^{t} | z^{'} (u) | d u ⩽ \int_{0}^{t} e^{- 1 - u} d u ⩽ e^{- 1} - e^{- 1 - t} ⩽ e^{- 1} . \end{array}$ In particular we conclude that $| z (t) | < 1$ for $t \in [0, τ^{}]$ and therefore that the system has not decided whether w should be accepted or rejected for times $⩽ τ^{}$ .

Let us now consider the case when $t ⩾ τ^{}$ . By definition of $ATSE$ , we have $‖ y_{1} (t) - g^{} (Ψ_{k} (w)) ‖ ⩽ e^{- ln 2}$ . Recall that $g^{} (Ψ_{k} (w)) \in {- 2, 2}$ and let $s \in {- 1, 1}$ be such that $g^{} (Ψ_{k} (w)) = 2 s$ . Then $‖ y_{1} (t) - 2 s ‖ ⩽ \frac{1}{2}$ , which means that $y_{1} (t) = s λ (t)$ , where $λ (t) ⩾ \frac{3}{2}$ . By (24), we conclude that $z (τ^{}) \in [- e^{- 1}, e^{- 1}]$ . From Proposition 14, we also conclude that z satisfies, for $t ⩾ τ^{}$ $\begin{matrix} z^{'} (t) = ϕ (t) (s λ (t) - z (t)), \end{matrix}$ where $1 > ϕ (t) > 0$ . Let us assume, without loss of generality, that $s = 1$ (a similar reasoning can be applied for the case $s = - 1$ ). Then the previous equation gives us, for $t ⩾ τ^{}$ , $\begin{matrix} (25) & z^{'} (t) = ϕ (t) (λ (t) - z (t)) ⩾ ϕ (t) (\frac{3}{2} - z (t)) . \end{matrix}$ Furthermore, since $z (τ^{}) \in [- e^{- 1}, e^{- 1}]$ , we conclude that z is strictly increasing when $t ⩾ τ^{}$ . To see this, consider a variable $r (t)$ defined by $r^{'} (t) = 3 / 2 - r (t)$ and $r (τ^{}) = z (τ^{})$ . We can explicitly solve the ODE for r and conclude that it converges to $3 / 2$ with a rate of convergence of the order of $e^{- t}$ and stays below $3 / 2$ for all $t ⩾ τ^{}$ . Furthermore, using standard results from ODEs we can conclude that $3 / 2 > r (t) ⩾ z (t)$ for all $t ⩾ τ^{}$ . Knowing that $z (τ^{}) \in [- e^{- 1}, e^{- 1}]$ this implies that $z (t)$ is strictly increasing for all $t ⩾ τ^{}$ . By Proposition 14, we have that for $t ⩾ τ^{} + 1$ $\begin{matrix} | y_{1} (t) - z (t) - {lxh}_{[0, 1]} (τ (t) - τ^{}, 1 + τ (t), y_{1} (t) - z (t)) | ⩽ e^{- 1 - τ (t)} ⩽ e^{- 1} . \end{matrix}$ This inequality and the definition of $z (t)$ yield that $\begin{matrix} (26) & | y_{1} (t) - z (t) - z^{'} (t) | ⩽ e^{- 1} . \end{matrix}$ We will now show that if $t ⩾ τ^{* } = τ^{} + 4 / (1 - 2 e^{- 1})$ , then $z (t) ⩾ 1$ . To show that it suffices to show that $z (τ^{* * }) ⩾ 1$ for some $τ^{ * } \in [τ^{}, τ^{* }]$ since z is increasing for $t ⩾ τ^{}$ . Suppose, by absurd, that there is no such $τ^{* * }$ . Then $z (t) < 1$ for all $t \in [τ^{}, τ^{* }]$ which implies that $y_{1} (t) - z (t) > 3 / 2 - 1 = 1 / 2$ . Then using this last inequality and (26), we conclude that $z^{'} (t) ⩾ 1 / 2 - e^{- 1}$ . Since $z (τ^{}) \in [- e^{- 1}, e^{- 1}]$ , this implies that $\begin{array}{l} z (τ^{* }) & = z (τ^{}) + \int_{τ^{}}^{τ^{ }} z^{'} (t) d t \\ ⩾ - e^{- 1} + (τ^{ } - τ^{}) (1 / 2 - e^{- 1}) \\ ⩾ - 1 + \frac{4}{1 - 2 e^{- 1}} (\frac{1}{2} - e^{- 1}) \\ = - 1 + \frac{2}{\frac{1}{2} - e^{- 1}} (\frac{1}{2} - e^{- 1}) \\ = 1 . \end{array}$ which is absurd. Therefore $z (t) ⩾ 1$ for all $t ⩾ τ^{* }$ . This proves conditions 1 and 2 of Definition 51.

Note that $‖ {(y, v, z, τ)}^{'} (t) ‖ ⩾ 1$ for all $t ⩾ 1$ so condition 4 of Definition 51 is also satisfied. To show condition 3, recall that $| g^{} (Ψ_{k} (w)) | = 2$ . Therefore from (24) for $t < τ^{}$ and from the previous analysis for $t ⩾ τ^{}$ , it is possible to conclude that $| z (t) | ⩽ | g^{} (Ψ_{k} (w)) | + 1 / 2 = 5 / 2$ for all $t ⩾ 0$ . This shows that if $Y = (y, v, z, τ)$ , then $‖ Y (t) ‖$ is bounded by an exponential boundary function on $‖ Ψ_{k} (w) ‖$ and by a polynomial on t because $‖ y (t) ‖ ⩽ Υ_{1} (‖ Ψ_{k} (w) ‖) Υ_{2} (t)$ for all $t ⩾ 0$ . Because $y^{'} (t) = p (y (t))$ and, by Proposition 14 $| z^{'} (t) | ⩽ | y_{1} (t) - z (t) | ⩽ | y_{1} (t) | + 5 / 2$ , we conclude that there are an exponential boundary function $Υ_{1}^{}$ and a polynomial $Υ_{2}^{}$ such that $‖ Y^{'} (t) ‖ ⩽ Υ_{1}^{} (‖ Ψ_{k} (w) ‖) Υ_{2}^{} (t)$ and, without loss of generality, we can assume that $Υ_{1}^{}$ and $Υ_{2}^{}$ are increasing functions. Now, since $‖ Y^{'} (t) ‖ ⩾ 1$ , we have that $\begin{matrix} (27) & t ⩽ {len}_{Y} (0, t) ⩽ t sup_{u \in [0, t]} ‖ Y^{'} (u) ‖ ⩽ t Υ_{1}^{} (‖ Ψ_{k} (w) ‖) Υ_{2}^{} (t) . \end{matrix}$ Define the function $Π^{}$ by $Π^{} (| w |) \equiv τ^{ } Υ_{1}^{} (| w |) Υ_{2}^{} (τ^{ })$ which is an exponential boundary function in $‖ Ψ_{k} (w) ‖ = | w |$ , because $τ^{ }$ is an exponential boundary function on $| w |$ , $Υ_{2}^{}$ is a polynomial, and $Υ_{1}^{}$ is an exponential boundary function. Let t be such that ${len}_{Y} (0, t) ⩾ Π^{} (| w |)$ . Then, by (27), $\begin{matrix} t Υ_{1}^{} (| w |) Υ_{2}^{} (t) ⩾ Π^{} (| w |) = τ^{ } Υ_{1}^{} (| w |) Υ_{2}^{} (τ^{ }) \end{matrix}$ which implies that $t Υ_{2}^{} (t) ⩾ τ^{ } Υ_{2}^{} (τ^{ })$ . Since $Υ_{2}^{}$ is increasing, this last condition is only true when $t ⩾ τ^{ }$ which, by the previous analysis, implies that $| z (t) | ⩾ 1$ , that is, the system has decided. This concludes the direct direction of the proof of Theorem 52.

We will now proceed with the reverse direction of the proof of Theorem 52. Assume that $L \in EAR$ . Apply the definition of the class $EAR$ to get the parameters and polynomials d, p, q characterizing the dynamical system and an exponential boundary function Π which satisfies the third condition of the definition of the class. Let $w \in Γ^{}$ and consider the following system $\begin{matrix} y (0) = q (Ψ_{k} (w)), y^{'} (t) = p (y (t)) . \end{matrix}$ We will show that we can decide in time exponential in $| w |$ whether $w \in L$ or not. Note that q is a polynomial with coefficients in $R_{P}$ and $Ψ_{k} (w)$ is a rational number. Therefore $q (Ψ_{k} (w)) \in R_{P}^{d}$ . Finally, note that $\begin{matrix} {PsLen}_{y, p} (0, t) = & \int_{0}^{t} Σ p max {(1, ‖ y (u) ‖)}^{\deg (p)} d u \\ ⩽ t Σ p max (1, sup_{u \in [0, t]} {‖ y (u) ‖}^{\deg (p)}) \\ ⩽ t Σ p max (1, sup_{u \in [0, t]} {(‖ y (0) ‖ + {len}_{y} (0, t))}^{\deg (p)}) \\ ⩽ t poly ({len}_{y} (0, t)) \\ ⩽ poly ({len}_{y} (0, t)) \end{matrix}$ where the last inequality holds because ${len}_{y} (0, t) ⩾ t$ . We can now apply Theorem 30 to conclude that we are able to compute $y (t) \pm 2^{- μ}$ in time polynomial in t, μ and ${len}_{y} (0, t)$ .

At this point some extra care is necessary. Indeed, the temptation is to use Theorem 30 to compute with a desired precision the value of the curve $y (t)$ at time $Π (| w |)$ . Nevertheless, it is possible that, at time $Π (| w |)$ , the length of the solution could be already over exponential in $| w |$ . Therefore, it is essential to use carefully the algorithm developed for the proof of Theorem 30 and stop the computation as soon as the length of the solution is greater than $Π (| w |)$ . This is possible due to the particular nature of the algorithm developed for the proof of Theorem 30 in [23]. Let $t^{}$ be the time at which the algorithm stops. Then, the running time of the algorithm will be polynomial in $t^{}$ , μ and ${len}_{y} (0, t^{}) ⩽ Π (| w |) + O (1)$ . Finally, by definition of the $EAR$ class, we have $t^{} ⩽ {len}_{y} (0, t^{})$ and so, because ${len}_{y} (0, t^{}) ⩽ Π (| w |)$ this algorithm has running time exponential in $| w |$ and polynomial in μ. Take $μ = log 2$ . Then we can obtain $\tilde{y}$ such that $‖ y (t^{}) - \tilde{y} ‖ ⩽ \frac{1}{2}$ . By definition of Π we have that $y_{1} (t^{}) ⩾ 1$ or $y_{1} (t^{}) ⩽ - 1$ , so we can decide from $\tilde{y}$ if $w \in L$ or not. This finishes the proof of the theorem. □

9. Conclusions and open problems

In this paper we have showed that the analog characterization obtained in [5] for polynomial complexity classes can be applied to other classes of computable functions. To reach this conclusion we had to overcome the fact that the equivalence established at a polynomial level was tailored over properties of polynomials, and therefore not trivially applicable to more general classes of functions. We started by analyzing the exponential case and we proved that the key ingredient to obtain the analog characterization was to modify the analog classes involved in such a way that could ensure closure by basic arithmetic operations and closure by composition with functions in $ATSP$ . This led us to Definition 23 of the $ATSE$ class and provided us enough elements to be able to apply the characterization for both the class of functions $FEXPTIME$ and the class of sets $EXPTIME$ by means of Theorems 29 and 52 respectively. Moreover, taking the exponential case as an inspiration and as a starting point, we established which set of conditions on the boundary functions are sufficient for being able to repeat the process applied to the exponential functions and obtain characterizations of greater complexity classes. This analysis has brought us to the formulation of the set of conditions 33 that implied Theorem 35. Then, we applied this generalization to the concrete case of the Grzegorczyk hierarchy, which implies a characterization of the class of elementary function as well as the class of primitive recursive functions.

As a natural consequence of the work presented with this paper, one can wonder whether a similar characterization can be obtained for complexity classes such as $NP$ . The framework used in this paper only deals which classes of languages decided in deterministic time. It would be interesting to know if this framework could be extended to non-deterministic time.

Footnotes

Acknowledgements

The authors wish to thank Olivier Bournez and Amaury Pouly for helpful discussions. R. Gozzi was supported by the Fundação para a Ciência e a Tecnologia (FCT) via grant PD/BD/135190/2017. This work is funded by FCT/MCTES through national funds and when applicable co-funded EU funds under the project UIDB/50008/2020.

References

Bournez,

M.L.

Campagnolo,

D.S.

Graça and

Hainry, The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation, in: Proc. Theory and Applications of Models of Computation (TAMC 06),

J.-Y.

Cai,

S.B.

Cooper and

Li, eds, Lecture Notes in Computer Science, Vol. 3959, Springer, 2006, pp. 631–643. doi:10.1007/11750321_60.

Bournez,

M.L.

Campagnolo,

D.S.

Graça and

Hainry, Polynomial differential equations compute all real computable functions on computable compact intervals, Journal of Complexity 23(3) (2007), 317–335. doi:10.1016/j.jco.2006.12.005.

Bournez,

D.S.

Graça and

Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length – the general purpose analog computer and computable analysis are two efficiently equivalent models of computations, in: Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016),

Chatzigiannakis,

Mitzenmacher,

Rabani and

Sangiorgi, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016, pp. 109:1–109:15.

Bournez,

D.S.

Graça and

Pouly, Computing with polynomial ordinary differential equations, Journal of Complexity 36 (2016), 106–140. doi:10.1016/j.jco.2016.05.002.

Bournez,

D.S.

Graça and

Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length, Journal of the ACM 64(6) (2017), 38:1–38:76. doi:10.1145/3127496.

Bournez,

D.S.

Graça and

Pouly, On the functions generated by the general purpose analog computer, Information and Computation 257 (2017), 34–57. doi:10.1016/j.ic.2017.09.015.

Bournez and

Hainry, An analog characterization of elementarily computable functions over the real numbers, in: Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Lecture Notes in Computer Science, Vol. 3142, Springer, 2004, pp. 269–280. doi:10.1007/978-3-540-27836-8_25.

Bournez and

Hainry, Elementarily computable functions over the real numbers and

R

-sub-recursive functions, Theoretical Computer Science 348(2–3) (2005), 130–147. doi:10.1016/j.tcs.2005.09.010.

M.S.

Branicky, Universal computation and other capabilities of hybrid and continuous dynamical systems, Theoretical Computer Science 138(1) (1995), 67–100. doi:10.1016/0304-3975(94)00147-B.

10.

Brattka,

Hertling and

Weihrauch, A tutorial on computable analysis, in: New Computational Paradigms: Changing Conceptions of What Is Computable,

S.B.

Cooper,

Löwe and

Sorbi, eds, Springer, 2008, pp. 425–491. doi:10.1007/978-0-387-68546-5_18.

11.

Bush, The differential analyzer. A new machine for solving differential equations, Journal of the Franklin Institute 212 (1931), 447–488. doi:10.1016/S0016-0032(31)90616-9.

12.

Campagnolo and

Moore, Upper and lower bounds on continuous-time computation, in: Proc. 2nd International Conference on Unconventional Models of Computation – UMC’2K,

Antoniou,

Calude and

Dinneen, eds, Springer, 2001, pp. 135–153. doi:10.1007/978-1-4471-0313-4_12.

13.

M.L.

Campagnolo,

Moore and

J.F.

Costa, Iteration, inequalities, and differentiability in analog computers, Journal of Complexity 16(4) (2000), 642–660. doi:10.1006/jcom.2000.0559.

14.

M.L.

Campagnolo,

Moore and

J.F.

Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity 18(4) (2002), 977–1000. doi:10.1006/jcom.2002.0655.

15.

Goldreich, Computational Complexity: A Conceptual Perspective, Revised 1st edn, Cambridge University Press, 2008.

16.

D.S.

Graça, Some recent developments on Shannon’s general purpose analog computer, Mathematical Logic Quarterly 50(4–5) (2004), 473–485. doi:10.1002/malq.200310113.

17.

D.S.

Graça,

M.L.

Campagnolo and

Buescu, Computability with polynomial differential equations, Advances in Applied Mathematics 40(3) (2008), 330–349. doi:10.1016/j.aam.2007.02.003.

18.

D.S.

Graça and

J.F.

Costa, Analog computers and recursive functions over the reals, Journal of Complexity 19(5) (2003), 644–664. doi:10.1016/S0885-064X(03)00034-7.

19.

Grzegorczyk, Some classes of recursive functions, Rozprawy matematyczne 4 (1953), 1–45.

20.

J.H.

Hubbard and

B.H.

West, Differential Equations: A Dynamical Systems Approach – Higher-Dimensional Systems, Springer, 1995.

21.

K.-I.

Ko and

Friedman, Computational complexity of real functions, Theoretical Computer Science 20 (1982), 323–352. doi:10.1016/S0304-3975(82)80003-0.

22.

Odifreddi, Classical Recursion Theory, Vol. 2, Elsevier, 1999.

23.

Pouly and

D.S.

Graça, Computational complexity of solving polynomial differential equations over unbounded domains, Theoretical Computer Science 626(2) (2016), 67–82. doi:10.1016/j.tcs.2016.02.002.

24.

C.E.

Shannon, Mathematical theory of the differential analyzer, Journal of Mathematics and Physics 20 (1941), 337–354. doi:10.1002/sapm1941201337.

25.

Weihrauch, Computable Analysis: An Introduction, Springer, 2000.

Characterizing time computational complexity classes with polynomial differential equations

Abstract

Keywords

1. Introduction

2. Computing with polynomial differential equations

Proposition 8 (ATSP modulus of continuity).

Theorem 9 (ATSP closure by composition).

3.1. Simulating Turing machines

Definition 15 (Turing Machine).

Definition 16 (Configuration).

Theorem 19 ([5], Polynomial iteration of a function in ATSP).

3.2. Equivalence relation between FP and ATSP

Definition 20 (Discrete emulation).

Theorem 21 ([5], FP equivalence).

4. Computing discrete functions: The exponential case

Definition 23 (ATSE).

Definition 24 (GEVAL).

4.2. Properties of the exponential analog classes

Theorem 25. If f ∈ GEVAL has a star domain with a vantage point in R G , then f ∈ ATSE . As a consequence of the above theorem together with our previous observation, exponential functions defined over star domains belong to ATSE . Theorem 26 (Exponential bound of ATSE).

Theorem 27 (ATSE closure by arithmetic operations).

Theorem 29 (FEXPTIME equivalence).

Theorem 30 ([23]).

5. Going beyond the exponential case

Definition 33 (Sufficient conditions).

1 Note that f ( N ) ⊆ [ 0 , + ∞ [ . Hence, although f ( n ) might not belong to N when n ∈ N , we can still say that a Turing machine computes in time ⩽ f ( n ) .

6. Generalization of the Analog Length class

Definition 40 (Grzegorczyk Hierarchy).

7.1. Analog characterization of each level

Lemma 47 ([6], Generable functions are closed under ODE).

8. Characterizing the class EXPTIME

8.1. Definitions of the analog classes

Definition 51 (EAR).

Theorem 52 (EXPTIME equivalence).

Footnotes

Acknowledgements

References

3.2. Equivalence relation between $FP$ and $ATSP$

Theorem 25.
If $f \in GEVAL$ has a star domain with a vantage point in $R_{G}$ , then $f \in ATSE$ .

As a consequence of the above theorem together with our previous observation, exponential functions defined over star domains belong to $ATSE$ .
Theorem 26 (Exponential bound of ATSE).

¹
Note that $f (N) \subseteq [0, + \infty [$ . Hence, although $f (n)$ might not belong to $N$ when $n \in N$ , we can still say that a Turing machine computes in time $⩽ f (n)$ .

8. Characterizing the class $EXPTIME$