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. 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 b
À 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.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement