Ver el código de «DTIME»

En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]]  '''DTIME(f(n))''' (también llamada '''TIME(f(n))''') es el conjunto de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos en una [[máquina de Turing]] determinista en tiempo [[Cota superior asintótica|O]](f(n)), y espacio ilimitado.

La clase de complejidad [[tiempo polinómico|P]] se puede definir a partir de DTIME como:

:<math>\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)</math>


{{Control de autoridades}}
[[Categoría:Clases de complejidad]]