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 el número de pasos de cálculo) que tomaría una computadora física "normal" para resolver un determinado problema de cálculo utilizando un determinado algoritmo . Es uno de los recursos de complejidad mejor estudiados, porque corresponde muy de cerca a un recurso importante 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, tenemos una clase de complejidad (o ). No hay restricciones 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 usar 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 cambios en el modelo computacional y que estén cerradas bajo la composición de subrutinas.
DTIME satisface el teorema de la jerarquía de tiempo , lo que significa que cantidades de tiempo asintóticamente más grandes siempre crean conjuntos de problemas estrictamente más grandes.
La conocida clase de complejidad P comprende todos los problemas que pueden resolverse en una cantidad polinómica de DTIME . Se puede definir formalmente como:
P es la clase robusta más pequeña que incluye problemas de tiempo lineal(AMS 2004, Conferencia 2.2, pág.20). P es una de las clases de mayor complejidad considerada "computacionalmente factible".
Una clase mucho más grande que usa tiempo determinista es EXPTIME , que contiene todos los problemas que se pueden resolver usando una máquina determinista en tiempo exponencial . Formalmente, tenemos
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; lo sabemosy en adelante.
Modelo de máquina
El modelo de máquina exacto utilizado para definir DTIME puede variar sin afectar la potencia del recurso. Los resultados en la literatura a menudo usan máquinas de Turing de varias cintas , particularmente cuando se habla de clases de muy poco tiempo. En particular, una máquina de Turing determinista de varias cintas nunca puede proporcionar más que una aceleración de tiempo cuadrática sobre una máquina de una sola cinta. [1]
Las constantes multiplicativas en la cantidad de tiempo utilizado no cambian la potencia de las clases DTIME; siempre se puede obtener una aceleración multiplicativa constante aumentando el número de estados en el control de estado finito. En la declaración de Papadimitriou, [2] para una lengua L ,
- Dejar . Entonces, para cualquier , , dónde .
Generalizaciones
Usando un modelo que no sea una máquina de Turing determinista, existen varias generalizaciones y restricciones de DTIME. Por ejemplo, si usamos una máquina de Turing no determinista , tenemos el recurso NTIME . La relación entre los poderes expresivos de DTIME y otros recursos computacionales es muy poco conocida. Uno de los pocos resultados conocidos [3] es
para máquinas de cintas múltiples. Esto se extendió a
por Santhanam. [4]
Si usamos una máquina de Turing alterna , tenemos el recurso ATIME.
Referencias
- ^ Papadimitriou 1994, Thrm. 2.1
- ^ 1994, Thrm. 2.2
- ^ Paul Wolfgang, Nick Pippenger , Endre Szemerédi , 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
- ^ Rahul Santhanam, Sobre separadores, segregadores y tiempo versus espacio , 16a Conferencia Anual de IEEE sobre Complejidad Computacional, 2001.
- Sociedad Americana de Matemáticas (2004). Rudich, Steven y Avi Wigderson (ed.). Teoría de la complejidad computacional . Sociedad Estadounidense 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. CS1 maint: parámetro desalentado ( enlace )