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)).
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.
vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
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.
A house is the simple topic of this studio. A matter of simple complexity. Starting from a movie depicting ways of living and a framed reference about materials, defining a fragment; redrawing a house
A house is the simple topic of this studio. A matter of simple complexity. Starting from a movie depicting ways of living and a framed reference about materials, defining a fragment; redrawing a house