TIEMPO DT

En la teoría de la complejidad computacional , DTIME (o TIME ) es el recurso computacional del tiempo de cálculo para una máquina de Turing determinista . Representa la cantidad de tiempo (o número de pasos de cálculo) que una computadora física "normal" tardaría en resolver un determinado problema computacional utilizando un determinado algoritmo . Es uno de los recursos de complejidad mejor estudiados, porque se corresponde muy de cerca con un importante recurso del mundo real (la cantidad de tiempo que le toma a una computadora resolver un problema).

El recurso DTIME se utiliza para definir clases de complejidad , conjuntos de todos los problemas de decisión que se pueden resolver utilizando una cierta cantidad de tiempo de cálculo. Si un problema de tamaño de entrada n se puede resolver en ⁠ ⁠ ${\displaystyle O(f(n))}$ , tenemos una clase de complejidad ⁠ ⁠ ${\displaystyle {\mathsf {DTIME}}(f(n))}$ (o ⁠ ⁠ ${\displaystyle {\mathsf {TIME}}(f(n))}$ ). No hay ninguna restricción en la cantidad de espacio de memoria utilizado, pero puede haber restricciones en algunos otros recursos de complejidad (como la alternancia ).

Clases de complejidad en DTIME

Muchas clases de complejidad importantes se definen en términos de DTIME , que contienen todos los problemas que se pueden resolver en una cierta cantidad de tiempo determinista. Se puede utilizar cualquier función de complejidad adecuada para definir una clase de complejidad, pero solo ciertas clases son útiles para estudiar. En general, deseamos que nuestras clases de complejidad sean robustas frente a los cambios en el modelo computacional y que estén cerradas bajo la composición de subrutinas.

DTIME satisface el teorema de jerarquía temporal , lo que significa que cantidades de tiempo asintóticamente mayores siempre crean conjuntos de problemas estrictamente mayores.

La conocida clase de complejidad P comprende todos los problemas que se pueden resolver en una cantidad polinómica de DTIME . Se puede definir formalmente como:

${\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$

P es la clase robusta más pequeña que incluye problemas de tiempo lineal (AMS 2004, lección 2.2, pág. 20). P es una de las clases de mayor complejidad consideradas "computacionalmente factibles". ${\displaystyle {\mathsf {DTIME}}\left(n\right)}$

Una clase mucho más grande que utiliza tiempo determinista es EXPTIME , que contiene todos los problemas que se pueden resolver utilizando una máquina determinista en tiempo exponencial . Formalmente, tenemos

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}$

Las clases de mayor complejidad se pueden definir de manera similar. Debido al teorema de la jerarquía temporal, estas clases forman una jerarquía estricta; sabemos que , y así sucesivamente. ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$

Modelo de máquina

Para clases robustas, como P, el modelo de máquina exacto utilizado para definir DTIME puede variar sin afectar la potencia del recurso. La literatura sobre complejidad computacional a menudo define DTIME en función de máquinas de Turing de múltiples cintas , en particular cuando se analizan clases de tiempo muy pequeñas. Una máquina de Turing determinista de múltiples cintas nunca puede proporcionar más que una aceleración de tiempo cuadrática en comparación con una máquina de una sola cinta. ^[1]

Debido al teorema de aceleración lineal para las máquinas de Turing, las constantes multiplicativas en el límite de tiempo no afectan la extensión de las clases DTIME; siempre se puede obtener una aceleración multiplicativa constante aumentando el número de estados en el control de estados finitos y el tamaño del alfabeto de cinta. En la declaración de Papadimitriou, ^[2] para un lenguaje L ,

Sea . Entonces, para cualquier , , donde . ${\displaystyle L\in {\mathsf {DTIME}}(f(n))}$ ${\displaystyle \epsilon >0}$ ${\displaystyle L\in {\mathsf {DTIME}}(f'(n))}$ ${\displaystyle f'(n)=\epsilon f(n)+n+2}$

Generalizaciones

Si utilizamos un modelo distinto de una máquina de Turing determinista, existen varias generalizaciones y restricciones de DTIME. Por ejemplo, si utilizamos una máquina de Turing no determinista , tenemos el recurso NTIME . La relación entre los poderes expresivos de DTIME y otros recursos computacionales se entiende muy poco. Uno de los pocos resultados conocidos ^[3] es

${\displaystyle {\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))}$

para máquinas multicinta. Esto se amplió a

${\displaystyle {\mathsf {DTIME}}(O(n{\sqrt {\log ^{*}n}}))\neq {\mathsf {NTIME}}(O(n{\sqrt {\log ^{*}n}}))}$

por Santhanam. ^[4]

Si utilizamos una máquina de Turing alterna , tenemos el recurso ATIME.

Referencias

1. Papadimitriou 1994, Thrm. 2.1
2. 1994, Tesis 2.2
3. Paul Wolfgang, Nick Pippenger , Endre Szemerédi y William Trotter. Sobre determinismo versus no determinismo y problemas relacionados. 24.° Simposio anual sobre fundamentos de la informática, 1983. doi :10.1109/SFCS.1983.39
4. Rahul Santhanam, Sobre separadores, segregadores y tiempo versus espacio, 16ª Conferencia Anual IEEE sobre Complejidad Computacional, 2001.

• Sociedad Americana de Matemáticas (2004). Rudich, Steven y Avi Wigderson (ed.). Teoría de la complejidad computacional . Sociedad Americana de Matemáticas e Instituto de Estudios Avanzados . ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.