Higher-order complexity in analysis

Hugo Férée 1 Mathieu Hoyrup 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We present ongoing work on the development of complexity theory in analysis. Kawamura and Cook recently showed how to carry out complexity theory on the space C[0,1] of continuous real functions on the unit interval. It is done, as in computable analysis, by representing objects by first-order functions (from finite words to finite words, say) and by measuring the complexity of a second-order functional in terms of second-order polynomials. We prove that this framework cannot be directly applied to spaces that are not $\sigma$-compact. However, representing objects by higher-order functions (over finite words, say) makes it possible to carry out complexity theory on such spaces: for this purpose we develop the complexity of higher-order functionals. At orders above 3, our class of polynomial-time computable functionals strictly contains the class BFF of Buss, Cook and Urquhart.
Type de document :
Communication dans un congrès
CCA - 10th International Conference on Computability and Complexity in Analysis - 2013, Jul 2013, Nancy, France. 2013
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00915973
Contributeur : Mathieu Hoyrup <>
Soumis le : lundi 9 décembre 2013 - 15:27:37
Dernière modification le : jeudi 22 septembre 2016 - 14:31:38
Document(s) archivé(s) le : dimanche 9 mars 2014 - 23:50:23

Fichier

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

Identifiants

  • HAL Id : hal-00915973, version 1

Collections

Citation

Hugo Férée, Mathieu Hoyrup. Higher-order complexity in analysis. CCA - 10th International Conference on Computability and Complexity in Analysis - 2013, Jul 2013, Nancy, France. 2013. 〈hal-00915973〉

Partager

Métriques

Consultations de
la notice

306

Téléchargements du document

303