A Non-deterministic Time Hierarchy over the reals

F. Cucker ^{†}  J.L. Montaña ^{‡}  L.M. Pardo ^{‡}

    This paper is published in
    Extracta Mathematicae, vol.  8, Nr.  2-3, pages 87--91, 1993

Abstract.- We show a non-deterministic time hierarchy over the reals under the model of real Turing machines. As a consequence we obtain the separation EXT IME_{IR} ≠ NP_{IR}.

Keywords: Computational complexity, theory of computation.

0. Introduction

In their 1989 paper [1], 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: the real Turing machine model. A special emphasis was made in the field of the real numbers, IR. This work also made an attempt, under the structural approach to complexity, at a classification of the 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.

In [2] an algebro-geometric characterization of the complexity classes over the reals and a deterministic time hierarchy is stated. The present note is a continuation of the results in [2]. A non-deterministic time hierarchy, as the one in the boolean case, is stated and as a consequence we conclude a feature which is still open in the boolean case: there is a language accepted by a deterministic real Turing machine in simply exponential time which can not be solved in polynomial non-deterministic time.

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

† Dept. L.S.I. Facultat d’Informatica. Universidad Politecnica de Catalunya. Barcelona 08028.

‡ Departamento de Matemáticas, Estadística y Computación. Facultad de Ciencias. Universidad de Cantabria. 39071 - SANTANDER. Spain

‡ Partially supported by DGICyT PB 89/0379 and “POSSO”, ESPRIT-BRA 6846.

1. Ground Tools.

Notations along these pages will follow essentially those introduced in [1]. 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 Turing machine M over IR 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 bounded computation machine.

Definition 1.3. 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}})

Definition 1.4. (c.f. [2]) 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).

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

Proof: See [2].

The following lemma is taken from [2].

Lemma 1.6. 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}.

2. Non–deterministic Time Hierarchy.

Definition 2.1. For a time bound s : IN ⟶ IN, we define the class NT IME_{IR} (s) of all those languages such that there is a real Turing machine M accepting inputs from IR^{∞} × IR^{∞} and a constant K ∈ IN verifying:

For every x ∈ IR^{∞}, x ∈ L if and only if there is y ∈ IR^{∞} such that (x, y) ∈ L(M), and

R_{M}(x, y) ≤ K.s(| x |).

Notice that the class of non–deterministic polynomial time over the reals is

NP_{IR} = ∪_{k∈IN} NT IME_{IR} (n^{k}).

Definition 2.2. 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.3. Let t, t′ : IN ⟶ IN be two time constructible bounds and assume that t′ ∈ ω(t). Then, DT IME_{IR} (t′) contains a language which is not in NT 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)).

On the other hand, if L ∈ NT IME_{IR} (t), there will be a real Turing machine M verifying the conditions of def 2.1. Observe that if (x, y) ∈ L(M) and R_{M}(x, y) ≤ K.t(n) for some y ∈ IR^{∞}, there is a constant K_{1} ≥ K depending only on M such that only the first K_{1}.t(n) coordinates of y are reached along the computation on (x, y). This implies that if π_{n} : IR^{n} × IR^{K_{1}.t(n)} ⟶ IR^{n} is the projection on the first n coordinates, π_{n} projects L(M)_{n+K_{1}.t(n)} onto L_{n}.

Since t is time constructible we can design a new machine M_{1} in the following terms: input(x, y)

m := K_{1}.t(| x |)
if T_{M}(x, y) ≤ m then ACCEPT iff M ACCEPTS (x, y)

else REJECT fi

This machine M_{1} verifies :

R_{M_{1}}(x, y) ≤ K_{1}.t(| x |) for all (x, y) ∈ L(M_{1}). π_{n}(L(M_{1})_{n+K_{1}.t(n)}) = π_{n}(L(M)_{n+K_{1}.t(n)}) = L_{n} Since the projections preserve connected components we have

β_{0} (L(M_{1})_{n+K_{1}.t(n)}) ≥ β_{0}(L_{n}) = 2^{t′(n)}

Finally, from lemma 1.6 we have

K.t(n) ∈ Ω (log_{2}β_{0}(L(M)_{n+K_{1}.t(n)}))

which contradicts the hypothesis t′ ∈ ω(t).

Corollary 2.4. For a pair of time bounds t, t′ : IN ⟶ IN verifying the previous conditions, the following diagram resumes the hierarchies:

DT IME_{IR} (t)  ⊆  NT IME_{IR} (t)
− |⋂  − //−  − |⋂
DT IME_{IR} (t′)  ⊆  NT IME_{IR} (t′)

The following statement is still open in the boolean case:

Corollary 2.5. Denoting by EXT IME_{IR} the class of languages accepted deterministically in simply exponential time we have

EXT IME_{IR} ≠ NP_{IR}

Agnowledgements. The second and third author wish to express their thanks to Professor Marek Karpinski, for suggesting them the problem of finding a non–deterministic hierarchy over the reals in their stay at Dagstuhl Seminar on Algebraic Complexity and Parallelism in July 1992.

References.

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

[2] F Cucker, J.L. Montaña and L.M. Pardo. “Time Bounded Computations over the Reals”. To appear in the International Journal of Algebra and Computation.