Higher order complexity and computable analysis
Identifieur interne : 002796 ( Hal/Corpus ); précédent : 002795; suivant : 002797Higher order complexity and computable analysis
Auteurs : Hugo FéréeSource :
Descripteurs français
English descriptors
Abstract
While first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types.
Url:
Links to Exploration step
Hal:tel-01098839Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Higher order complexity and computable analysis</title><title xml:lang="fr">Complexité d'ordre supérieur et analyse récursive</title><author><name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:tel-01098839</idno><idno type="halId">tel-01098839</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-01098839</idno><idno type="url">https://tel.archives-ouvertes.fr/tel-01098839</idno><date when="2014-12-10">2014-12-10</date><idno type="wicri:Area/Hal/Corpus">002796</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Higher order complexity and computable analysis</title><title xml:lang="fr">Complexité d'ordre supérieur et analyse récursive</title><author><name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>complexity</term><term>computable analysis</term><term>higher order</term></keywords><keywords scheme="mix" xml:lang="fr"><term>analyse récursive</term><term>complexité</term><term>ordre supérieur</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">While first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Higher order complexity and computable analysis</title><title xml:lang="fr">Complexité d'ordre supérieur et analyse récursive</title><author role="aut"><persName><forename type="first">Hugo</forename><surname>Férée</surname></persName><email>hugo.feree@loria.fr</email><ptr type="url" target="http://www.loria.fr/~hferee"></ptr><idno type="idhal">hugo-feree</idno><idno type="halauthor">1111750</idno><affiliation ref="#struct-29797"></affiliation></author><editor role="depositor"><persName><forename>Hugo</forename><surname>Férée</surname></persName><email>hugo.feree@inria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-12-29 19:35:24</date><date type="whenModified">2015-09-22 01:12:54</date><date type="whenReleased">2015-01-06 11:48:10</date><date type="whenProduced">2014-12-10</date><date type="whenEndEmbargoed">2014-12-29</date><ref type="file" target="https://tel.archives-ouvertes.fr/tel-01098839/document"><date notBefore="2014-12-29"></date></ref><ref type="file" n="1" target="https://tel.archives-ouvertes.fr/tel-01098839/file/manuscrit_hferee.pdf"><date notBefore="2014-12-29"></date></ref></edition><respStmt><resp>contributor</resp><name key="177212"><persName><forename>Hugo</forename><surname>Férée</surname></persName><email>hugo.feree@inria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">tel-01098839</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-01098839</idno><idno type="halBibtex">feree:tel-01098839</idno><idno type="halRefHtml">Complexité [cs.CC]. Université de Lorraine, 2014. Français</idno><idno type="halRef">Complexité [cs.CC]. Université de Lorraine, 2014. Français</idno><availability status="restricted"><licence target="http://creativecommons.org/licenses/by-sa/">Attribution - ShareAlike</licence></availability></publicationStmt><seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA-FM" p="LORIA">Méthodes formelles</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno></seriesStmt><notesStmt></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Higher order complexity and computable analysis</title><title xml:lang="fr">Complexité d'ordre supérieur et analyse récursive</title><author role="aut"><persName><forename type="first">Hugo</forename><surname>Férée</surname></persName><email>hugo.feree@loria.fr</email><ptr type="url" target="http://www.loria.fr/~hferee"></ptr><idno type="idHal">hugo-feree</idno><idno type="halAuthorId">1111750</idno><affiliation ref="#struct-29797"></affiliation></author></analytic><monogr><imprint><date type="dateDefended">2014-12-10</date></imprint><authority type="institution">Université de Lorraine</authority><authority type="school">IAEM</authority><authority type="supervisor">Jean-Yves Marion</authority><authority type="supervisor">Mathieu Hoyrup</authority><authority type="jury">James S. Royer (rapporteur et examinateur)</authority><authority type="jury">Paul-André Melliès (Examinateur)</authority><authority type="jury">Olivier Bournez (rapporteur et examinateur)</authority><authority type="jury">Patrick Baillot (rapporteur)</authority><authority type="jury">Philippe de Groote (président du jury)</authority></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="fr">French</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">complexity</term><term xml:lang="en">computable analysis</term><term xml:lang="en">higher order</term><term xml:lang="fr">complexité</term><term xml:lang="fr">analyse récursive</term><term xml:lang="fr">ordre supérieur</term></keywords><classCode scheme="halDomain" n="info.info-cc">Computer Science [cs]/Computational Complexity [cs.CC]</classCode><classCode scheme="halTypology" n="THESE">Theses</classCode></textClass><abstract xml:lang="en">While first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types.</abstract><abstract xml:lang="fr">Alors que la complexité des fonctions d'ordre 1 est bien définie et étudiée, ils n'existe pas de notion satisfaisante à tout ordre. Une telle théorie existe déjà à l'ordre 2 et permet de définir une classe analogue aux fonctions calculables en temps polynomial usuelles. Cela est tout particulièrement intéressant dans le domaine de l'analyse récursive où l'on peut représenter, entre autres, les nombres et les fonctions réelles par des fonctions d'ordre 1. On peut alors remarquer un lien fort entre calculabilité et continuité, et aussi rapprocher la complexité avec certaines propriétés analytiques, ce que nous illustrons dans le cas des opérateurs réels. Nous prouvons cependant que, du point de vue de la complexité, les fonctions d'ordre 1 ne permettent pas de représenter fidèlement certains espaces mathématiques. Ce résultat appuie tout particulièrement la nécessité d'une théorie de la complexité d'ordre supérieur. Nous développons alors un modèle de calcul basé sur la sémantique des jeux, où l'application de deux fonctions est représentée par la confrontation de deux stratégies dans un jeu. En définissant la taille de telles stratégies, nous pouvons déduire une notion robuste et pertinente de complexité pour ces stratégies et donc pour les fonctions d'ordre supérieur. Nous définissons aussi une classe de fonctions calculables en temps polynomial qui paraît être un bon candidat pour définir une classe de complexité raisonnable à tout ordre.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002796 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 002796 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:tel-01098839
|texte= Higher order complexity and computable analysis
}}
| This area was generated with Dilib version V0.6.33. |  |