# Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions

2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Recursive analysis is the most classical approach to model and discuss computations over the reals. It is usually presented using Type 2 or higher order Turing machines. Recently, it has been shown that computability classes of functions computable in recursive analysis can also be defined (or characterized) in an algebraic machine independent way, without resorting to Turing machines. In particular nice connections between the class of computable functions (and some of its sub- and sup-classes) over the reals and algebraically defined (sub- and sup-) classes of $\R$-recursive functions à la Moore 96 have been obtained. However, until now, this has been done only at the computability level, and not at the complexity level. In this paper we provide a framework that allows us to dive into the complexity level of functions over the reals. In particular we provide the first algebraic characterization of polynomial time computable functions over the reals. This framework opens the field of implicit complexity of functions over the reals, and also provide a new reading of some of the existing characterizations at the computability level.
Type de document :
Rapport
[Research Report] 2009
Domaine :

Littérature citée [26 références]

https://hal.inria.fr/inria-00421561
Contributeur : Walid Gomaa <>
Soumis le : lundi 5 octobre 2009 - 16:02:33
Dernière modification le : jeudi 10 mai 2018 - 02:06:01
Document(s) archivé(s) le : mercredi 16 juin 2010 - 00:18:08

### Fichier

submission.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00421561, version 1

### Citation

Olivier Bournez, Walid Gomaa, Emmanuel Hainry. Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions. [Research Report] 2009. 〈inria-00421561〉

### Métriques

Consultations de la notice

## 484

Téléchargements de fichiers