Time Bounded Computations over the reals

F. Cucker ^{†,‡}  J.L. Montaña ^{‡}  L.M. Pardo ^{‡}
Dept. L.S.I.  Dept. Matem. Estad. y C.C.  Dept. Matem. Estad. y C.C.
Facultat d’Informàtica  Universidad de Cantabria  Universidad de Cantabria
Barcelona 08028  Santander 39071  Santander 39071
SPAIN  SPAIN  SPAIN

    This paper is published in
    International Journal of Algebra and Computation
    Vol.  2, Nr.  4, pages 395--408, 1992.

Topic: computational complexity.

0. Introduction

In their 1989 paper [3], L. Blum, M. Shub and S. Smale introduced a model of computation and a theory of recursiveness that accepted an ordered field or ring as alphabet for the space of admissible inputs. A special emphasis was made in the field of the real numbers, IR. That work also made an attempt, under the structural approach to complexity, at a classification of th e procedures developed in numerical analysis and computational geometry involving real numbers as inputs. In particular, analogues of the P and NP classes were introduced there.

At first glance many similarities can be seen between the new complexity classes, with their relationships, and their Boolean counterparts, a very remarkable one being the existence of complete problems in NP ([3]) and in P ([7]). However, many basic differences can also be found. Among those differences one stands out: to obtain complexity classes bounding the used space is irrelevant. In [10] it is shown in fact that any recursive set can be decided in linear space.

Another outstanding difference is given by the fact that there are recursive problems without running time bounds for any machine that solves them. A typical example is given by ZZ ⊂ IR. In this paper we shall be mainly concerned with the class of problems that can be decided within bounded time. So, we introduce the class T B of subsets of IR^{∞} recognized by real Turing machines whose running time is a well defined function in the input size. A similar class of sets, but in the integer context has been introduced by F. Meyer auf der Heide in [11].

In section 1 we study first properties of such a class. In particular, we characterize them in a geometric manner. Let us recall that a semialgebraic subset of IR^{n} is any subset obtained by finitely many unions and intersections of sets defined by polynomial inequalities. In [3] it is shown that any recursively enumerable set can be written as a countable union of semialgebraic sets. Shortly afterwards, C. Michaux characterized the recursively enumerable sets, as those subsets of IR^{∞} that can be written as a countable union of semialgebraic sets defined over a finite extension of 0 Q. We extend this line of work by characterizing the sets in T B. In fact, we show that a set is in T B if and only if all its subsets of words of size n are semialgebraic subsets of IR^{n}.

This result is used to obtain some consequences regarding the topological structure of recursively enumerable sets as well as of sets in T B. More precisely, we endow IR^{∞} with the sum topology, and we show that all open subsets of IR^{∞} are recursively enumerable, and that for any set L ⊂ IR^{∞}, if L belongs to T B then also their interior and closure belong to T B. We think that this is a step towards S. Smale’s idea “to bring the theory of computation into the domain of geometry, analysis and topology”.

In section 2 we give time hierarchy theorems for T B. A theorem requiring time constructibility is given whose statement is analogous to the well known one for the Boolean case. We give also a theorem not requiring time constructibility, that uses the particular feature of the real model in which any function with domain and images in the integers is computable. However, we pay the price for this generality by requiring the functions not to be sublinear.

† Partially supported by the ESPRIT BRA Program of the EC under contract no. 3075, project ALCOM, and UPC/PR 9014.

‡ Partially supported by DGICyT PB 89/0379.

Complexity of algorithms dealing with polynomials over a ring is usually expressed as a function of the degree and the number of variables of the input polynomial. In the Boolean case (where the ring is supposed to be finitely codable) both parameters are related to the size of the polynomial, the degree being expressed as a natural number in base two. This is not the case for machines over the reals, where any natural number takes unitary space. Thus, in [3] section 6, it is shown that for any d ≥ 4 the dF EAS problem of deciding whether a polynomial of degree d has a real root is NP-complete, but no similar statement can be made without restricting the degree. In fact, the F EAS problem of deciding

whether an arbitrary polinomial has a real root is not even in T B.

In section 3 we introduce several classes of sets that reflect the complexity of problems like the last one we mentioned. In particular we define the class P T B of pseudo time bounded sets to be the class of sets whose function associating the running time to each input is, as a function from IR^{∞} to IR, time bounded. First properties of this class are that it is closed under Boolean operations, it is strictly included between T B and the class of recursive sets, and has complete problems for reductions in T B. Moreover, a whole hierarchy of recursive sets is defined over T B by inductively lifting the relation between T B and P T B, and it is shown that all the levels of this hierarchy have complete problems.

Finally, we extend to the real setting a notion of pseudo-polynomial time introduced in [17] for integer computations.

1. Time Bounded Computations

Notations along these pages will follow essentially those introduced in [3]. However we shall omit the qualification “over the reals” for classes of languages and machines, since no confusion can arise with their Boolean counterpart, which does not appear here.

By IR^{∞} we shall denote the direct sum ⨁_{i∈IN} IR, i.e. the set of all sequences of real numbers with only finitely many non-zero coordinates. The size of an element x ∈ IR^{∞} is the non-negative integer |x| = n ∈ IN such that x_{n} ≠ 0 is the last non-zero coordinate of x. Also, in analogy with the Boolean case, we shall call “language” any set included in IR^{∞} and the language recognized by a machine M will be denoted by L(M). Moreover, languages recognized by some machine will be called recursively enumerable (and denoted r.e. for short) and a r.e. language whose complement is also r.e. will be called recursive. For a language L ⊆ IR^{∞}, we shall denote by L_{n} the set of words in L of size n ∈ IN, i.e. L_{n} = {x ∈ L | |x| = n}.

The running time R_{M}(x) of a machine M for x ∈ L(M) is the number of nodes in M traversed by the computation of M on x until it reaches the output node.

Using these notations, we can define the halting time function associated to a machine M to be

\begin{matrix}T_{M} : & IN ⟶ IN ∪ \{+∞\} \\ n ↦ sup\{R_{M}(x) | x ∈ L(M), |x| = n\} \end{matrix}

Definition 1.1. For a total mapping s : IN ⟶ IN we define the complexity class DT IME_{IR} (s) to be {L | there is a machine M , such that, L = L(M) and T_{M}(n) ∈ O(s)}.

Definition 1.2. A machine M is said to be a time bounded computation machine if T_{M}(n) < ∞, for all n ∈ IN. We shall say that a language is time bounded recursive (L ∈ T B for short) iff L is recognized by a time bounde d computation machine.

Remarks 1.3. From the definition above it can be observed that the class T B is closed under complementation, finite unions and intersections. The newness of the class T B is a particular feature of the real model. In the Boolean one, T B coincides with the class of recursive sets, a fact that is not shared in our context. The most straightforward example is the set of the integers ZZ ⊂ IR which is easily seen to be recursive, but it is not time bounded (cf. theorem 1.10 below).

In [3] section 4, proposition 2, a necessary condition is given for a subset L ⊆ IR^{∞} to be r.e. Shortly afterwards, C. Michaux in [12] modified that condition to obtain a geometrical characterization of r.e. sets.

In this section we extend Michaux’s characterization to another, for languages in T B. In order to do it we recall some notions from real algebraic geometry .

Definition 1.4. A semialgebraic set S is a subset of some finitely dimensional real affine space, S ⊆ IR^{n}, for n < ∞, such that there is a finite number of polynomials f_{ij} ∈ IR[X_{1}, …, X_{n}] and sign conditions ϵ_{ij} ∈ {> 0, = 0, < 0} such that the following equality holds :

S = ⋃_{j=1}^{r}(∩_{i=1}^{t}{(x_{1}, …, x_{n}) ∈ IR^{n} | sign(f_{ij}(x_{1}, …, x_{n})) = ϵ_{ij}})

Thus, the class of semialgebraic subsets of IR^{n} is the closure under the Boolean operations of the class of subsets defined by polynomial inequalities in the variables X_{1}, …, X_{n}. If all the polynomials f_{ij} have coefficients in a subfield H ⊂ IR we shall say that S is defined over H.

In [3] it is shown that any r.e. set can be written as a countable union of semialgebraic sets. Shortly later, C. Michaux characterized in [12] those unions of semialgebraic sets that are r.e. Let us recall this characterization.

Definition 1.5. A language L is said to be finitely generated if there is a finitely generated field extension 0 Q(S) of 0 Q and a countable family of semialgebraic sets defined over 0 Q(S), {A_{n} ⊆ IR^{i_{n}} | i_{n} < ∞} such that

L = ⋃_{n∈IN} A_{n}

This notion captures the geometrical structure of r.e. sets, as the following result stated in [12] shows.

Theorem 1.6. For any language L, L is r.e. iff L is finitely generated.

Our next result gives a characterization of time bounded sets in the same geometrical manner.

Definition 1.7. A language L is said to be finitely presented if there is a finitely generated field extension 0 Q(S) of 0 Q, such that for every n ∈ IN, L_{n} is a semialgebraic subset of IR^{n} defined over 0 Q(S).

Lemma 1.8. For every partial mapping s : IN ⟼ IN there is a machine M computing s within time O(s(n)(n + s(n))^{2}) on input n. Proof: Let us recall from [3] section 1, example 6, that given a set S ⊂ IN we can decide whether a real number x belongs to S within time O(⌊x⌋). Now, we consider the polynomial

f(n, m) = \frac{1 + n + m}{2}(n + m) + (m + 1)

the set S = f(graph(s)) and the algorithm

input(n) m := 0 while f(n, m) ∉ S do

m := m + 1

od

RETURN(m)

This algorithm computes s(n). Moreover, for a given input n we pass s(n) times through the while condition. To check this conditions costs by the preceding remark O(f(n, m)) steps. So, the total cost is bounded by O(s(n)(n + s(n))^{2}).

Remarks 1.9. The preceding result marks another difference with the Boolean model. In this last one, there are many functions not computable from IN to IN, but all time bounds are computable by just getting for each n the maximum of the running times among the 2^{n} words of size n. In the real model, this argument obviously does not apply, but the preceding lemma makes it unnecessary in several situations.

Theorem 1.10. For any language L, L is in T B iff L is finitely presented.

Proof: (⇒) Suppose that L is recognized by a time bounded computation machine M, and let T_{M}(n) = s(n). Let us

consider for each t ∈ IN, the set I_{t} of all inputs accepted in time t. We know that I_{t,n} := {x ∈ I_{t} : |x| = n} is a semialgebraic set. Moreover there is a finitely generated field extension of 0 Q , 0 Q(a_{1}, …, a_{r}) , where {a_{1}, …, a_{r}} is the collection of all constants appearing in the description of M, such that for all n ∈ IN, L_{n} can be described by a finite number of polynomials in 0 Q(a_{1}, …, a_{r})[X_{1}, …, X_{n}] . Thus, we have that

L_{n} = ( ⋃_{t=1}^{s(n)} I_{t,n})

from where we deduce the statement. (⇐) Let us now suppose that L is finitely presented. Then there is a finite extension 0 Q(S) = 0 Q(a_{1}, …, a_{r}) of

0 Q such that for each n the subset L_{n} can be described be a finite system Φ_{n} of equalities and inequalities as in the definition 1.4. whose polynomials have coefficients in 0 Q(S). Thus, for each n, L_{n} is described by a family

{(f_{ij}^{n}, ϵ_{ij}^{n})}

where ϵ_{ij}^{n} is a sign and f_{ij}^{n} ∈ 0 Q(S)[X_{1}, …, X_{n}]. Now, each f_{ij}^{n} can be expressed as a polynomial in 0 Q[a_{1}, …, a_{r}, X_{1}, …, X_{n}] and then can be coded as an element of IN^{∞}. Thus, the same happens with the whole family {(f_{ij}^{n}, ϵ_{ij}^{n})}. We so consider the function

φ :IN → IN^{∞}
n → the encoding of {(f_{ij}^{n}, ϵ_{ij}^{n})}

toghether with the machine given by

input(x) n := |x| compute {(f_{ij}^{n}, ϵ_{ij}^{n})} := φ(n) for every (i, j) evaluate f_{ij}^{n}(a_{1}, …, a_{r}, x_{1}, …, x_{n}) ACCEPT iff the evaluated values satisfy Φ_{n}

The preceding machine accepts exactly L. Moreover, it does so in bounded time. In fact, the first asignment is done in constant time, and the other instructions in time that clearly dependens only on n (and not on the specific input x).

Remarks 1.11. A non-uniform model of computation frequently used in algebraic complexity to show lower bounds is the algebraic tree (see for instance [1] or [15]). One of the most interesting features of the model introduced by Blum, Shub and Smale is that an algebraic tree is just a finite acyclic real Turing machine whose computation nodes perform only elementary operations (+, ∗, − or /). In this sense the computational device introduced in [3] uniformizes the algebraic trees. On the other hand, we could also consider as non-uniform models the finite real Turing machines.

The preceding results show that there is a strong relation between computability and geometry, in the sense that there is a correspondence between abstract computational devices and geometrical properties satisfied by the sets recognized by them. We can sumarize them in the following table.

Machine model  Recognized sets
Real Turing Machine  Finitely generated
Time Bounded Machine  Finitely presented
Finite Machine  Countably unions of semialgebraics

Algebraic Tree or

Algebraic Circuit  Semialgebraic

One of the goals stated in [3] with respect to the introduction of the real Turing machine is “to bring the theory of computation into the domain of geometry, analysis and topology”. This goal passes through the fact that IR is endowed with a very rich topological structure.

There is a canonical form to endow a direct sum with a topological structure. The topology induced over ⨁_{i∈IN} IR is called sum topology and their open sets are the sets U such that for every n the set U_{n} = U ∩ IR^{n} − {X_{n} = 0} is open. In the case of finite sums ⨁_{1≤i≤n} IR, the sum topology coincides with the Euclidean one. For definitions as well as for basic properties of the sum topology, see [5] I, p.15.

Theorem 1.12.

i) For k ∈ IN , every open subset of IR^{k} is r.e. Thus, a closed subset of IR^{k} is r.e. iff it is recursive. ii) Assume IR^{∞} is endowed with the sum topology. Then,

a) Every open set in IR^{∞} is r.e.

b) A closed subset of IR^{∞} is r.e. if and only if it is recursive.

c) For a language L ⊆ IR^{∞} we denote by Int(L) and Clos(L) its interior and closure respectively. Then, if L ∈ T B we also have that Int(L), Clos(L) ∈ T B. Proof: Parts i), ii.a) and ii.b) are consequences of the existence of a good basis of open sets. In fact, any open subset of IR^{n} can be written as a countable union of balls B(x, ϵ) with x has rational coordinates and ϵ belongs to 0 Q. Since these balls are semialgebraic, the statement clearly hold.

For part ii.c) let us consider a set L ∈ T B. For each n, we have a formula Φ_{n}(x_{1}, …, x_{n}) defining L_{n}, because of the theorem 1.10. Again, because of the structure of the open sets in IR^{∞}, it is immediate that

Int(L) := ⋃_{n∈IN} Int(L_{n})

and

Clos(L) := ⋃_{n∈IN} Clos(L_{n})

where the interior and closure of L_{n} is taken in IR^{n} − {x_{n} = 0}. Thus, Int(L_{n}) and Clos(L_{n}) can be expressed by the formulæ

∃ϵ∀y_{1} … ∀y_{n} ϵ > 0 ∧ Φ_{n}(x_{1}, …, x_{n}) ∧ [ ∑_{k=1}^{n}(x_{k} − y_{k})^{2} ≥ ϵ ∨ Φ_{n}(y_{1}, …, y_{n})]

and

∀ϵ∃y_{1} … ∃y_{n}[x_{n} ≠ 0 ∧ ϵ > 0 ∧ Φ_{n}(x_{1}, …, x_{n}) ∧ Φ_{n}(y_{1}, …, y_{n})]

respectively.

These formulæ only use constants in 0 Q(S) . Thus, by the quantifier elimination in the theory of the reals they are equivalent to quantifier-free formulæ with constants in 0 Q(S), which define semialgebraic subsets of IR^{n} − {x_{n} = 0}. The statement is now a trivial consequence of theorem 1.10.

2. Time Hierarchy Theorems within TB

We begin this section with a lemma providing a lower bound for the running time of time bounded machines, that will be useful for proving the hierarchy theorems.

Lemma 2.1. Let M be a time bounded machine and L its accepted language. Then, we have T_{M}(n) ∈ Ω(log_{2} B_{0}(L_{n})), where B_{0}(L_{n}) denotes the number of connected components of L_{n}. Proof: For every y ∈ L_{n} we have a sequence of configurations given by the computation of M on y

(n_{0}, x_{0}) → (n_{1}, x_{1}) → ⋯ → (n_{k}, x_{k})

where n_{0} is the input node, n_{k} is the output node and k ≤ T_{M}(n) . By γ(y) we shall denote the computation path n_{0} → n_{1} → ⋯ → n_{k} in M and let us define

Γ_{n} := {γ(y) | y ∈ L_{n}}

the set of all posible paths followed by inputs in L_{n}.

Now, Γ_{n} is a finite set because the length of every path in Γ_{n} is bounded above by T_{M}(n) and the number of paths in M of a given length ≤ K, is bounded by 2^{K}.

Next, for every path γ ∈ Γ_{n} there is a semialgebraic subset V_{γ} ⊆ IR^{n} − {x_{n} = 0} , given by V_{γ} = {x ∈ L_{n} | γ(x) = γ}, observing that

L_{n} = ⋃_{γ∈Γ_{n}} V_{γ}

At this point let us note that there is a constant K_{M}, depending only on the machine M, such that for every n ∈ IN and for every γ ∈ Γ_{n}, the membership problem to V_{γ} can be solved by a Straight Line Program π_{γ} of length l ≤ K_{M}.T_{M}(n). At every computation node of π_{γ} just an arithmetic operation among {+, −, ×, /} is performed.

Now, we follow the central arguments in [1] plus a little topological trick. Traversing π_{γ} we get a system of equations S according to the operations or tests on the vertices of π_{γ}. In this system, we add a new variable at each computation node. Let u_{1}, ⋯, u_{r} be the set of variables added in S. If U denotes the subset of IR^{n+r} defined by S it is clear that the projection on the first n coordinates of U is exactly V_{γ}.

Thus, the number of connected components of V_{γ}, B_{0}(V_{γ}) ≤ B_{0}(U). Note that the degree of the system S is bounded above by 2, the number of equations is bounded by l, and the number of active variables ≤ 3l, at most three at each computation node, two due to the computation and one added in S to decrease the degree.

Now, by [1] Theorem 2, it follows that the number of connected components of V_{γ} ≤ 2 × 3^{4l−1}. Since the cardinal of Γ_{n} is ≤ 2^{T_{M} (n)}, the statement follows by observing that

B_{0}(L_{n}) ≤ ∑_{γ∈Γ_{n}} B_{0}(V_{γ}) ≤ 2^{T_{M} (n)+1} × 3^{4.K_{M} .T_{M} (n)−1}

Remarks 2.2.

i) Lemma 2.1 is an improvement of Ben-Or’s lower bound in [1], based on the geometry of the semialgebraic sets. In [14] and [13], the lower bounds obtained for the total complexity of a semialgebraic set can also be applied to this model. Moreover, observe that all these lower bounds also hold for the corresponding measure of complexity of machines over any real closed field considered.

ii) The introduction of this lower bound is motivated by the following time hierarchy theorem and its good accuracy for classes of “small” time bound (i.e. lower than linear time ) for which the lower bounds in [1] and [13] are not useful at all.

Definition 2.3. A total mapping s : IN ⟶ IN is said to be time constructible if there is a machine M such that the mapping φ_{M} computed by M restricted to IN coincides with s and, there is a constant K ∈ IR, K > 0 such that R_{M}(m) ≤ K.s(m), for all excepting a finite number of elements m ∈ IN, where R_{M}(m) denotes the running time of M on input m ∈ IN.

The most common functions used as time bounds in complexity theory (as, for instance, log_{2}^{k}(n), n^{k} or 2^{k.n} , with k ∈ IN fixed ) are time constructible over the reals.

Theorem 2.4. Let t, t′ : IN ⟶ IN be two time bounds, t′ time constructible and assume that t′ ∈ ω(t). Then, DT IME_{IR} (t′) contains a language which is not in DT IME_{IR} (t).

Proof: Let us consider the language L defined as the set of points x ∈ IR^{∞}, such that x_{1} + ix_{2} is a 2^{t′(n)} -th root of the unity in the complex plane. The following machine

input(x) n := |x| m := t′(n) z := (x_{1} + ix_{2})^{2^{m}} if z = 1 then ACCEPT else REJECT

fi

accepts L in time O(t′(n)). In fact, the first asignement takes constant time, and the following two can be done within time O(t′(n)). But, the number of connected components of L_{n} is 2^{t′(n)} and so, by lemma 2.1, L cannot be recognized in time t(n).

Remarks 2.5. It is interesting to note that, in contrast with the Boolean case where the input size is computed in linear time, in the real model, we can compute it in constant time. This fact gives to the real model the capacity of deciding more things in sublinear time.

In the following corollary we present some of the strict inclusions for the most usual complexity classes.

Corollary 2.6. For k ∈ IN fixed, in the following chain the inclusion relations are strict: i) DT IME_{IR} (log_{2}^{k}(n)) ⊂ DT IME_{IR} (log_{2}^{k+1}(n)) ⊂ DT IME_{IR} (n) ii) DT IME_{IR} (n^{k}) ⊂ DT IME_{IR} (n^{k+1}) ⊂ DT IME_{IR} (2^{n}) iii) DT IME_{IR} (k^{n}) ⊂ DT IME_{IR} ((k + 1)^{n}) ⊂ DT IME_{IR} (2^{2}^{n}).

As another application of lemma ?.?. we can give another time hierarchy theorem for non-necessarily constructible time bounds .

Theorem 2.7. Let t, t′ : IN ⟶ IN be two time bounds , t′(n) ≥ n and assume that \sqrt[3]{t′} ∈ ω(t). Then, DT IME_{IR} (t′) contains a language not in DT IME_{IR} (t).

Proof: Call s(n) the integer part of the function \sqrt[3]{t′} and consider the language L defined by the set of points (x_{1}, ⋯, x_{n}, ⋯) ∈ IR^{∞} such that x_{1} + ix_{2} is a 2^{s(n)}-th root of the unit in C.

A machine M accepting this language within time O(t′) can be designed in the same manner as in the proof of theorem 2.4 substituting t′ by s. Because of the lemma 1.8 this machine evaluates s on the input size requiring O(t′) steps to complete the evaluation . Next, using s(|x|), the machine controls the simulation on the first two coordinates of the input the complex operation (x_{1} + i.x_{2})^{2}^{s(|x|)}, doing this in O(s) steps. Finally, it compares to (1, 0) in constant time, accepting if and only if the equality holds.

The fact that L is not in DT IME_{IR} (t) follows again in the same manner as in the proof of theorem 2.4 by using lemma 2.1.

3. Pseudo time bounded computations over the reals

Complexity of algorithms dealing with polynomials over a ring is ussually expressed as a function of the degree and the number of variables of the input polynomials. In the Boolean case, both parameters are related with the size of the input polynomial, the degree being expressed as a natural number in base two. This is not the case for machines over the reals, where any natural number takes unitary space; so, we can device polynomials of arbitrarily high degree but with very small size. This explains why, in section 6 of [3] it is shown that for any d ≥ 4 the problem

dF EAS = {F | F is a polynomial of degree d that has a real root}

is NP-complete, but no similar statement can be done for polynomials without restricting the degree. In fact, the problem

F EAS = {F | F is a polynomial that has a real root}

is not even in T B, and thus we have no bound for the runnig time of any algorithm as a function of the input size.

Let us notice, however, that since there are algorithms (see [6], [8], [9] or [15]) that solve F EAS within time d^{O(n)}, given such an input we can compute a bound for the running time of those algorithms on it, and this computation is itself time bounded. This property, shared by a large class of problems motivates the following definition.

Definition 3.1 Let L be a recursive set. We shall say that L is a Pseudo Time Bounded set (briefly L ∈ P T B) if there is a machine M accepting L, and a time bounded recursive function f : IR^{∞} → IN such that R_{M} = O(f). In a similar way, we define pseudo time bounded functions, and we write f ∈ F P T B to denote that f is such a function.

Proposition 3.2

i) The class P T B is closed under complements and finite unions and intersections. ii) F EAS belongs to P T B. iii) We have the strict inclusions T B ⊂ P T B ⊂ R. iv) The halting time problem

H := {(M, x, t) | the machine M accepts x in less than t steps}

is PTB-complete for reductions in T B. Proof:

i) Immediate. ii) Trivial since d^{n} can be computed in T B. iii) Both inclusions being obvious, we shall only show that they are strict.

For the first one, we just note that ZZ is not in T B but it is certainly in P T B since there is a machine deciding this set in time O(x) for input x, and the identity function is computed in constant (and then bounded) time. For the second one, let us consider the set

S = {(x, y, t) | (x + iy)^{2^{2^{⌊t⌋}}} = 1}.

For a fixed value of the parameter t we apply lemma 2.1 getting a lower bound of 2^{t} in the number of steps we must perform to decide whether a triple (x, y, t) belongs to S. So, any machine deciding S has 2^{t} as lower bound for its running time. But any time bounded function with domain IR^{3} must be semialgebraic, and then, must have polynomial growth. We deduce that S ∉ P T B. On the other hand, S is obviously recursive.

iv) The problem is in P T B since the computing time for an input (M, x, t) is linear in t and then can be obtained in bounded time in the size of (M, x, t). On the other hand, for any machine M ∈ P T B we consider the reduction mapping x to (M, x, t), where t is obtained from M and x in bounded time since M ∈ P T B.

Remarks 3.3. The analysis of pseudo time bounded computations can be continued following two directions. On the one hand, a hierarchy of classes over P T B can be inductively defined. On the other hand, subclasses of P T B can be considered by posing restrictions to the function f in definition 3.1.

We shall begin by lifting inductively the relation between T B and P T B.

Definition 3.4. Define P T B_{0} := T B and for i ≥ 1 define P T B_{i} as the class of recursive sets L such that there is a machine M accepting L and a total function f : IR^{∞} → IR belonging to F P T B_{i−1} satisfying R_{M} = O(f). The pseudo time bounded hierachy P T BH is defined by P T BH := ⋃_{i≥0} P T B_{i}.

Now, P T B_{i}-complete problems under T B reductions can be obtained in a natural way. Define the following sets:

H_{1} := H
F H_{1} := {(M, x, t) | M halts on input x in less than t steps}

and for i ≥ 2

F H_{i} := {(M, M_{1}, ⋯, M_{i−1}, x, t) | M halts on input x in less than φ_{M_{1}}(x) steps
and (M_{1}, ⋯, M_{i−1}, x, t) ∈ F H_{i−1} }
H_{i} := {(M, M_{1}, ⋯, M_{i−1}, x, t) | M accepts x in less than φ_{M_{1}}(x) steps
and (M_{1}, ⋯, M_{i−1}, x, t) ∈ F H_{i−1}}

Lemma 3.5. For any s : IN → IN let us consider the functions ψ_{s,j} : IR^{∞} → IR, j ∈ IN, defined by

\begin{matrix}ψ_{s,0}(x) = ∥x∥^{s(|x|)} \\ ψ_{s,k+1}(x) = ∥x∥^{2^{⌊ψ_{s,k}(x)⌋}} \end{matrix}

Then, for any recursive function f : IR^{∞} → IR,

i) If f ∈ F P T B_{i}, there is a function s : IN → IN such that f ∈ O(ψ_{s,i}). Moreover, if f is restricted to a certain IR^{n}, then s can be taken to be constant.

ii) For each s, t : IN → IN, we have that ψ_{s,i} ∈ ω(ψ_{t,i−1}). iii) We have that ψ_{s,i} ∈ F P T B_{i}\F P T B_{i−1}. Proof: Induction on i.

Theorem 3.6

i) For every i ≥ 1 the inclusion P T B_{i−1} ⊂ P T B_{i} is strict. ii) The inclusion P T BH ⊂ R is strict. iii) For every i ≥ 1 the set H_{i} is P T B_{i}-complete for reductions in T B. Proof: For the first and the second statement let us consider the subset of IR^{3}

S = {(x, y, z) | (x + iy)^{2^{2^{2^{·^{·^{·^{2^{⌊∥(x,y)∥⌋}}}}}}} }⌊z⌋} = 1}

For every i ≥ 1 consider the subset S_{i} of S defined by the points in S satisfying also the condition ⌊z⌋ = 2i−2. Clearly, S_{i} ∈ P T B_{i}. Now, suppose that S_{i} belongs to P T B_{i−1}. By the previous lemma one has that

2^{2^{2^{·^{·^{·^{2^{⌊∥(x,y)∥⌋}}}}}}} ^{}⌊2i−3⌋} ≤ ψ_{k,i−2}

for a certain constant k. Taking logarithms 2i − 4 times one gets that

2^{⌊∥(x,y)∥⌋} ≤ ∥(x, y)∥^{k}

which is a contradicion. We then have that S_{i} ∈ P T B_{i} − P T B_{i−1}, and consequently S = ⋃_{i≥1} S_{i} cannot be in P T BH.

For the third statement the case i = 1 is given by Proposition 3.2 iii) and applying induction on i we see that the following is a P T B_{i} algorithm for H_{i}:

input(M, M_{1}, ⋯, M_{i−1}, x, t) z := (M_{1}, ⋯, M_{i−1}, x, t) if z ∉ K_{i−1} then REJECT

else compute T := φ_{M_{1}}(x)

ACCEPT iff M acepts x in less than T steps fi

The hardness is trivially given by the definition of the classes P T B_{i}.

We close this sections introducing a natural subclass of P T B which is obtained by restricting the class of functions used to bound the running time of M in definition 3.1. In the integer setting, a similar class has already been studied under the name of Pseudo-Polynomial Time (see [17] §7.3.2.) We briefly describe now a generalization for the real model.

Definition 3.7 We shall say that a language L ⊂ IR^{∞} is accepted in pseudo-polynomial time (and we shall writte L ∈ pP) if there is a machine M having L as accepted language and a function f computable in polynomial time such that R_{M} = O(f). In a similar way we define the class pNP of languages accepted in non-deterministic pseudo-polynomial time.

Remarks 3.8. Notice that neither pNP nor pP are closed under pP reductions, since the size of f(x) for a function f computable in pseudo-polynomial time, can be doubly exponential in ∥x∥. It is not difficult however to see that both classes are closed under reductions in P and that pNP has complete problems for those reductions .

Theorem 3.9. The problem

KARP_{IR} = {(M, x, t) | the machine M acceppts x in less than t non deterministic steps}

is pNP-complete for reductions in P. Proof: Clearly KARP_{IR} is in pNP. In order to show the hardness, for any pNP machine M with time bound f, we consider the following mapping

x ⟶ (M, x, f(x))

that reduces the language accepted by M to KARP_{IR} in polynomial time.

References.

[1] M. Ben-Or; “Lower bounds for algebraic computation trees”. A.C.M. 15^{th} Symp. on Theory of Computing, pp.80-86, 1983.

[2] R. Benedetti and J.J. Risler; Real algebraic and semialgebraic sets. Hermann, Paris, 1990.

[3] L. Blum, M. Shub and S. Smale; “On a theory of computation and complexity over the real numbers: NPcompleteness, recursive functions and universal machines”. Bulletin of the Amer. Math. Soc., vol.21, n.1, pp.1-46, 1989.

[4] J. Bochnak, M. Coste and M.-F. Roy; Géométrie algébrique réelle. Ergebnisse der Math., 3.Folge, Band 12, Springer Verlag, 1987.

[5] N. Bourbaki; Éléments de Mathématique. Topologie Général. Chapitres I-IV. Hermann, Paris, 1971.

[6] J. Canny; “Some algebraic and geometric computations in PSPACE”. A.C.M. 20^{th} Symp. on Theory of Computing, pp.460-467, 1988.

[7] F. Cucker and A. Torrecillas; “Two P-complete problems in the theory of the reals”. To appear in Proceedings of ICALP’91, Madrid, 1991.

[8] D. Grigor’ev; “Complexity of deciding Tarski algebra”. J. of Symb. Comp., 5 pp.65-108, 1988.

[9] J. Heintz, M.-F. Roy and P. Solerno; “On the complexity of semialgebraic sets”. Proceedings of IFIP’89, pp.293-298, North Holland, 1989.

[10] C. Michaux; “Une remarque à propos des machines sur R introduites par Blum, Shub et Smale”. C. R. Acad. Sci. Paris, t.309, Série I, pp.435-437, 1989.

[11] F. Meyer auf der Heide; “On genuinely time bounded computations”. Symp. Theor. Aspects of Comp., LNCS 349, Springer Verlag, pp.1-16, 1989.

[12] C. Michaux; “Machines sur les réels et problèmes NP-complets”, Séminaire de Structures Algébriques Ordonnées. Prépublications de l’equipe de logique mathématique de Paris 7, 1990.

[13] J.L. Montaña, L.M. Pardo and T. Recio; “The non-scalar model of complexity in computational geometry”. To appear in Proceedings of MEGA’90, Birkhäuser.

[14] L.M. Pardo and T. Recio; “Rabin’s width of a complete proof and the width of a semialgebraic set”. Proceedings of the EUROCAL’87, LNCS 378, Springer Verlag, pp.456-462, 1989.

[15] M. Rabin; “Proving simultaneous positivity of linear forms”. J. of Comp. and Syst. Sc., 6, pp.639-650, 1972.

[16] J. Renegar; “On the computational complexity and geometry of the first order theory of the reals”. Technical report 853, Cornell University, Ithaca, 1989.

[17] K. Wagner and G. Wechsung; Computational Complexity. Mathematische monographien, Band 19, VEB Deutscher Verlag der Wissenschaften, Berlin, 1986.