En la teoría de la complejidad computacional , DLOGTIME es la clase de complejidad de todos los problemas computacionales que se pueden resolver en una cantidad logarítmica de tiempo de cálculo en una máquina de Turing determinista . Debe definirse en una máquina de Turing de acceso aleatorio , ya que de lo contrario la cinta de entrada es más larga que el rango de celdas a las que puede acceder la máquina. Es un modelo muy débil de complejidad temporal: ninguna máquina de Turing de acceso aleatorio con un límite de tiempo determinista más pequeño puede acceder a toda la entrada. [1]
Ejemplos de
DLOGTIME incluye problemas relacionados con la verificación de la longitud de la entrada, [1] por ejemplo, el problema " ¿La entrada tiene una longitud uniforme? ", Que se puede resolver en tiempo logarítmico mediante la búsqueda binaria .
Aplicaciones
DLOGTIME: la uniformidad es importante en la complejidad del circuito . [1] [2]
Referencias
- ^ a b c Johnson, David S. (1990), "Un catálogo de clases de complejidad", Manual de informática teórica, vol. A , Elsevier, Amsterdam, págs. 67-161, MR 1127168. Ver en particular la p. 140 .
- ^ Allender, Eric; Gore, Vivek (1993), "Sobre fuertes separaciones de AC 0 ", Avances en la teoría de la complejidad computacional (New Brunswick, NJ, 1990) , DIMACS Ser. Matemáticas discretas. Theoret. Computación. Sci., 13 años , Amer. Matemáticas. Soc., Providence, RI, págs. 21–37, MR 1255326. Ver en particular la p. 23 .