Fonction constructible

En théorie de la complexité, une fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que  f(n) peut être calculée à partir de n par une machine de Turing qui se termine en un temps du même ordre de grandeur que f(n). Le but de cette définition est d'exclure les fonctions qui n'apportent pas de borne supérieure sur le temps d'exécution. Une définition similaire pour la complexité en espace existe et introduit la notion de fonction constructible en espace.

Définitions des fonctions constructibles en temps 
Il y a deux définitions de fonction constructible en temps :
 Une fonction f est constructible en temps s'il existe un entier positif n0 et une machine de Turing M qui prend en entrée un mot 1n constitué de n uns et s'arrête après exactement f(n) étapes pour tout n ≥ n0. 
 Une fonction f est constructible en temps s'il existe une machine de Turing M qui prend en entrée un mot 1n, produit la représentation binaire de f(n) en temps O(f(n)) (une représentation unaire pourrait être utilisée à la place, puisque l'on peut passer d'une représentation à une autre en temps O(f(n))).

Il y a également une notion de fonction totalement constructible en temps. Une fonction f est totalement constructible en temps s'il existe une machine de Turing M qui prend en entrée un mot 1n constitué de n uns et s'arrête après exactement f(n) étapes. Cette définition est moins générale que les deux premières définitions. Cependant, les trois définitions peuvent être utilisées indifféremment pour la plupart des applications.

Définitions des fonctions constructibles en espace 
Similairement, il y a deux définitions de fonction constructible en espace :
 Une fonction f est constructible en espace s'il existe un entier positif n0 et une machine de Turing M qui prend en entrée un mot 1n constitué de n uns, s'arrête en ayant utilisé exactement f(n) cases du ruban pour tout n ≥ n0. 
 Une fonction f est constructible en espace s'il existe une machine de Turing M qui prend en entrée un mot 1n constitué de n uns, produit la représentation binaire (ou unaire) de f(n), en utilisant un espace O(f(n)).

De plus, une fonction f est totalement constructible en espace s'il existe une machine de Turing M qui prend en entrée un mot 1n constitué de  n uns et s'arrête après avoir utilisé exactement f(n) cases du ruban.

Exemples 
Toutes les fonctions usuelles f(n) (par exemple n, nk, 2n) sont constructibles en temps et en espace à condition que f(n) soit supérieure à cn pour une certaine constante c > 0. Aucune fonction non constante et o(n) ne peut être constructible en temps puisqu'il n'y a pas assez de temps pour lire l'entrée. Cependant, log(n) est une fonction constructible en espace.

Propriétés 
 Si f et g sont deux fonctions constructibles en espace, alors les fonctions f+g et f×g sont aussi constructibles en espace.
 Si f est une fonction récursive partout définie de ℕ dans ℕ et constructible en temps, alors elle est constructible en espace.

Applications 
Les fonctions constructibles en temps sont utilisées dans certains théorèmes de la théorie de la complexité, tels que le théorème de hiérarchie en temps déterministe.
Elles sont importantes puisque le théorème de la hiérarchie en temps repose sur des machines de Turing qui doivent déterminer en temps O(f(n)) si un algorithme a utilisé plus de f(n) étapes. Ceci serait impossible si l'on ne pouvait pas calculer f(n) en temps O(f(n)).

Similairement, les fonctions constructibles en espaces sont utilisées dans le . On les trouve aussi dans le  (gap theorem).

Construction de fonction et logique constructive 
En logique constructive une fonction est constructible s'il est existe une démonstration constructive de la valeur cible à partir de la valeur origine.  Dans ce domaine, on s'intéresse plus à la construction de la fonction  dans une logique où on ne fait pas appel à l'infini ou au tiers exclus qu'à sa complexité.  Il s'agit donc d'un domaine assez différent de celui présenté plus haut, puisque le problème de la possibilité de « construire » une fonction  est essentiel et l'emporte sur celui de la complexité.

Notes et références

Bibliographie 
 
 
 Yves Bertot et Pierre Casteran Interactive Theorem Proving and Program Development, Springer Verlag, Berlin, (2004)

Théorie de la complexité des algorithmes
Constructible