Voir la source de DTIME

Vous n’avez pas la permission de modifier cette page, pour la raison suivante :

Votre adresse IP fait partie d’une plage qui a été bloquée sur tous les wikis de la Fondation Wikimédia.

Le blocage a été effectué par ‪Hasley‬. Le motif invoqué est Open proxy/Webhost: See the help page if you are affected: .

Début du blocage : 18 décembre 2022 à 17:21
Expiration du blocage : 18 décembre 2025 à 17:21

Votre adresse IP actuelle est 62.210.136.28. La plage bloquée est 62.210.0.0/16.

Veuillez inclure tous les détails ci-dessus dans toutes les demandes que vous effectuerez. Si vous pensez avoir été bloqué(e) par erreur, vous pouvez trouver plus d’informations et d’instructions dans la politique globale Pas de serveurs mandataires ouverts.

Sinon, pour discuter du blocage, veuillez publier une demande de révision sur Méta-Wiki. Vous pouvez également envoyer un courriel à la file des coordinateurs VRT à stewards@wikimedia.org, en incluant tous les détails ci-dessus.

Vous pouvez voir et copier le contenu de cette page.

En [[Théorie de la complexité (informatique théorique)|théorie de la complexité]], '''DTIME''' (ou '''TIME''') désigne une famille de [[Classe de complexité|classes de complexité]] caractérisée par leur [[complexité en temps]] sur une [[machine de Turing]] déterministe.

Plus précisément, <math>\mathsf{DTIME}(f(n))</math> est la classe des [[Problème de décision|problèmes de décision]] qui, pour une entrée de taille <math>n</math>, peuvent être résolus en temps <math>\mathcal{O}(f(n))</math> par une machine de Turing déterministe.

== Définitions ==
La classe [[P (complexité)|P]] des problèmes de décision décidables par une machine de Turing déterministe en temps [[Polynôme|polynomial]] par rapport à la taille de l'entrée peut être définie comme :

: <math>\mathsf{P}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(n^k)</math>

De même, la classe [[EXPTIME]] des problèmes de décision décidable en temps [[Fonction exponentielle|exponentiel]] est définie comme :

: <math>\mathsf{EXPTIME}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}\left(2^{n^k}\right)</math>

== Hiérarchie en temps ==

Informellement, le [[théorème de hiérarchie en temps déterministe]] indique que disposer de plus de temps permet de décider davantage de problèmes. Plus précisément, pour toutes fonctions <math>f</math> et <math>g</math> telles que <math>f\log f=o(g)</math> et <math>g</math> est [[Fonction constructible|constructible en temps]], l'inclusion stricte suivante est vérifiée :

: <math>\mathsf{DTIME}(f(n))\subsetneq\mathsf{DTIME}(g(n))</math>

== Liens avec d'autres classes ==

Les classes DTIME sont reliées aux classes de [[complexité en espace]] [[DSPACE]] et [[NSPACE]] par les inclusions suivantes, pour toute fonction <math>f</math> constructible en espace :
: <math>\mathsf{DTIME}(f(n))\subseteq\mathsf{NTIME}(f(n))\subseteq\mathsf{DSPACE}(f(n))\subseteq\mathsf{NSPACE}(f(n))\subseteq\mathsf{DTIME}\left(2^{\mathcal{O}(f(n))}\right)</math>

== Bibliographie ==

* {{Ouvrage|langue=en|auteur1=|prénom1=Sanjeev|nom1=Arora|lien auteur1=Sanjeev Arora|prénom2=Boaz|nom2=Barak|titre=Computational Complexity: A Modern Approach|passage=|lieu=|éditeur=[[Cambridge University Press]]|date=2009-04-20|pages totales=579|isbn=978-0-521-42426-4|lire en ligne=https://books.google.fr/books?id=8Wjqvsoo48MC&printsec=frontcover&hl=fr&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false|consulté le=2020-06-03|plume=oui}}
* {{Ouvrage|langue=fr|auteur1=Sylvain Perifel|titre=Complexité algorithmique|éditeur=[[Éditions Ellipses]]|date=22-04-2014|pages totales=432|isbn=978-2-729-88692-9|lire en ligne=https://www.irif.fr/~sperifel/complexite.pdf|consulté le=2021-04-10|plume=oui}}

{{Palette|Théorie de la complexité}}
{{Portail|Informatique théorique}}

[[Catégorie:Classe de complexité]]

Modèles utilisés par cette page :

Modèle:Catégorisation badges (voir la source) (protégé)
Modèle:Liste horizontale (voir la source) (semi-protection étendue)
Modèle:Méta lien vers portail (voir la source) (protégé)
Modèle:Méta lien vers portail/Catégorisation (voir la source) (protégé)
Modèle:Méta palette de navigation (voir la source) (protégé)
Modèle:Méta palette de navigation sous-groupe (voir la source) (protégé)
Modèle:Ouvrage (voir la source) (protégé)
Modèle:Palette (voir la source) (protégé)
Modèle:Palette Théorie de la complexité (modifier)
Modèle:Portail (voir la source) (protégé)
Modèle:Portail Informatique théorique (modifier)
Modèle:Portail informatique théorique (modifier)
Modèle:Suivi des biographies (voir la source) (protégé)
Modèle:Tnavbar (voir la source) (protégé)
Module:Biblio (voir la source) (protégé)
Module:Biblio/Commun (voir la source) (protégé)
Module:Biblio/Ouvrage (voir la source) (semi-protection étendue)
Module:Biblio/Références (voir la source) (protégé)
Module:Catégorisation badges (voir la source) (semi-protection étendue)
Module:Date (voir la source) (protégé)
Module:Date/Data (voir la source) (semi-protection étendue)
Module:Langue (voir la source) (protégé)
Module:Langue/Data (voir la source) (semi-protection étendue)
Module:Linguistique (voir la source) (semi-protection étendue)
Module:Nombre2texte (voir la source) (protégé)
Module:Outils (voir la source) (protégé)
Module:Palette (voir la source) (semi-protection étendue)
Module:Suivi des biographies (voir la source) (protégé)
Module:Suivi des biographies/données (voir la source) (semi-protection étendue)
Module:TableBuilder (voir la source) (protégé)
Module:Wikidata (voir la source) (semi-protection étendue)
Module:Wikidata/I18n (voir la source) (semi-protection étendue)

Revenir à la page DTIME.

Ce document provient de « https://fr.wikipedia.org/wiki/DTIME ».