Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Fonction constructible
Résumé
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.
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.
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)).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.