TIEMPO DE DLOG
En la teoría de la complejidad computacional , DLOGTIME es la clase de complejidad de todos los problemas computacionales solucionables 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 al 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
DLOGTIME incluye problemas relacionados con la verificación de la longitud de la entrada, [1] por ejemplo el problema "¿ La entrada es de longitud par? ", que puede resolverse en tiempo logarítmico mediante búsqueda binaria .
Aplicaciones
DLOGTIME: la uniformidad es importante en la complejidad del circuito . [1] [2]
Referencias
- ^ abc Johnson, David S. (1990), "Un catálogo de clases de complejidad", Manual de informática teórica, vol. A , Elsevier, Ámsterdam, págs. 67-161, MR 1127168. Véase en particular la pág. 140.
- ^ Allender, Eric; Gore, Vivek (1993), "Sobre separaciones fuertes de AC 0 ", Avances en la teoría de la complejidad computacional (New Brunswick, NJ, 1990) , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 13, Amer. Math. Soc., Providence, RI, págs. 21–37, MR 1255326. Véase en particular la pág. 23.
