Graded Universal Function for BSS-Grzegorczyk Hierarchy and Separation of Complexity Classes

J.-S. Gakwaya & Ch. Michaux

In this communication we will assume some basic knowledge of Blum-Shub and Smale model of computation (see [1]). We will first define an extension of Grzegorczyk hierarchy (see [3] for the definition of this classical hierarchy) to the framework of BSS-model of computation (extending ideas from [2]). We show that this BSS-Grzegorczyk hierarchy is strict. As in the classical case a hierarchy of classes of relations is associated to BSS-Grzegorczyk hierarchy. By building a graded universal function for this hierarchy we prove that it is a strict hierarchy from the third level. The method of proof (which has some reminiscence from [4]) gives us a unified proof of the classical result. But it has no consequence on the main open problem in the subject : separation of the three first levels of this hierarchy of relations.

[1] Blum L., Shub M., Smale S., On a theory of computation and complexity over the real numbers: NP–completeness, recursive functions and universal machines”, Bull. Amer. Math. Soc. 21 (1989) 1–46.

[2] Gakwaya J.–S., Extended Grzegorczyk hierarchy in the BSS model of computability, Cucker and Shub eds, Foundations of Computational Mathematics, Springer (1997) 127–151.

[3] Grzegorczyk A., Some classes of recursive functions, Instytut Matematyczny Polskiej Akademii Nauk, Warszawa (1953) 1–44.

[4] Ritchie R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc. 106 (1963) 139–179.

Addresses J.-S. Gakwaya: Université de Mons-Hainaut, Institut de Mathématique et d’Informatique, Le Pentagone, 6 avenue du Champ de Mars, 7000 Mons, Belgique

Ch. Michaux: Université de Mons-Hainaut, Institut de Mathématique et d’Informatique, Le Pentagone, 6 avenue du Champ de Mars, 7000 Mons, Belgique

E-mail: christian.michaux@umh.ac.be