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 n₀ et une machine de Turing M qui prend en entrée un mot 1ⁿ constitué de n uns et s'arrête après exactement f(n) étapes pour tout n ≥ n₀.
• Une fonction f est constructible en temps s'il existe une machine de Turing M qui prend en entrée un mot 1ⁿ, 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 1ⁿ 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 n₀ et une machine de Turing M qui prend en entrée un mot 1ⁿ constitué de n uns, s'arrête en ayant utilisé exactement f(n) cases du ruban pour tout n ≥ n₀.
• Une fonction f est constructible en espace s'il existe une machine de Turing M qui prend en entrée un mot 1ⁿ 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 1ⁿ 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, n^k, 2ⁿ) 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 théorème de hiérarchie en espace (en). On les trouve aussi dans le théorème de la lacune (en) (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é.

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 1,4
• Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne)
• Yves Bertot et Pierre Casteran Interactive Theorem Proving and Program Development, Springer Verlag, Berlin, (2004)