title: DTIME
text: # DTIME
  
  En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.
  
  Plus précisément, ${\mathsf {DTIME}}(f(n))$ est la classe des problèmes de décision qui, pour une entrée de taille $n$, peuvent être résolus en temps ${\mathcal {O}}(f(n))$ par une machine de Turing déterministe.
  
  ## Définitions
  
  La classe P des problèmes de décision décidables par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée peut être définie comme :
  
      ${\mathsf {P}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})$
  
  De même, la classe EXPTIME des problèmes de décision décidable en temps exponentiel est définie comme :
  
      ${\mathsf {EXPTIME}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right)$
  
  ## 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 $f$ et $g$ telles que $f\log f=o(g)$ et $g$ est constructible en temps, l'inclusion stricte suivante est vérifiée :
  
      ${\mathsf {DTIME}}(f(n))\subsetneq {\mathsf {DTIME}}(g(n))$
  
  ## 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 $f$ constructible en espace :
  
      ${\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)$
  