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, ${\displaystyle {\mathsf {DTIME}}(f(n))}$ est la classe des problèmes de décision qui, pour une entrée de taille ${\displaystyle n}$, peuvent être résolus en temps ${\displaystyle {\mathcal {O}}(f(n))}$ par une machine de Turing déterministe.