Polynomial time computation in the context of recursive analysis

Walid Gomaa 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Recursive analysis was introduced by A. Turing [1936], A. Grzegorczyk [1955], and D. Lacombe [1955] as an approach for investigating computation over the real numbers. It is based on enhancing the Turing machine model by introducing oracles that allow the machine to access finitary portions of the real infinite objects. Classes of computable real functions have been extensively studied as well as complexity-theoretic classes of functions restricted to compact domains. However, much less have been done regarding complexity of arbitrary real functions. In this article we give a definition of polynomial time computability of arbitrary real functions. Then we present two main applications based on that definition. The first one, which has already been published, concerns the relationships between polynomial time real computability and the corresponding notion over continuous rational functions. The second application, which is a new contribution to this article, concerns the construction of a function algebra that captures polynomial time real computability.
Type de document :
Communication dans un congrès
Marko van Eekelen and Olha Shkaravska. First International Workshop on Foundational and Practical Aspects of Resource Analysis - FOPARA 2009, Nov 2009, Eindhoven, Netherlands. Springer, 6324, pp.146-162, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15331-0_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00758332
Contributeur : Walid Gomaa <>
Soumis le : mercredi 28 novembre 2012 - 15:32:33
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Identifiants

Collections

Citation

Walid Gomaa. Polynomial time computation in the context of recursive analysis. Marko van Eekelen and Olha Shkaravska. First International Workshop on Foundational and Practical Aspects of Resource Analysis - FOPARA 2009, Nov 2009, Eindhoven, Netherlands. Springer, 6324, pp.146-162, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15331-0_10〉. 〈hal-00758332〉

Partager

Métriques

Consultations de la notice

274