Implicit complexity in recursive analysis

Olivier Bournez (1) , Walid Gomaa (2) , Emmanuel Hainry (2)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 CARTE - Theoretical adverse computations, and safety

Recursive analysis is a model of analog computation which is based on type 2 Turing machines. Various classes of functions computable in recursive analysis have recently been characterized in a machine independent and algebraical context. 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 have been obtained. We provide in this paper a framework that allows to dive into complexity for functions over the reals. It indeed relates classical computability and complexity classes with the corresponding classes in recursive analysis. This framework opens the field of implicit complexity of functions over the reals. While our setting provides a new reading of some of the existing characterizations, it also provides new results: inspired by Bellantoni and Cook's characterization of polynomial time computable functions, we provide the first algebraic characterization of polynomial time computable functions over the reals.

Domaines: Complexité [cs.CC]

Olivier Bournez, Walid Gomaa, Emmanuel Hainry. Implicit complexity in recursive analysis. Tenth International Workshop on Logic and Computational Complexity - LCC'09, Aug 2009, Los Angeles, United States. ⟨inria-00429964⟩