Teorema de la jerarquía del tiempo

Con más tiempo, una máquina de Turing puede resolver más problemas

En la teoría de la complejidad computacional , los teoremas de la jerarquía temporal son declaraciones importantes sobre la computación limitada en el tiempo en las máquinas de Turing . De manera informal, estos teoremas dicen que, dado más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que se pueden resolver con n ² tiempo pero no con n tiempo, donde n es la longitud de entrada.

El teorema de la jerarquía temporal para las máquinas de Turing deterministas de cintas múltiples fue demostrado por primera vez por Richard E. Stearns y Juris Hartmanis en 1965. ^[1] Se mejoró un año después cuando FC Hennie y Richard E. Stearns mejoraron la eficiencia de la máquina Universal de Turing. . ^[2] Como consecuencia del teorema, para cada clase de complejidad determinista con límite de tiempo , existe una clase de complejidad con límite de tiempo estrictamente mayor, por lo que la jerarquía de clases de complejidad con límite de tiempo no colapsa por completo. Más precisamente, el teorema de la jerarquía temporal para las máquinas deterministas de Turing establece que para todas las funciones construibles en el tiempo f ( n ),

${\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)})}$,

donde DTIME ( f ( n )) denota la clase de complejidad de los problemas de decisión que se pueden resolver en el tiempo O ( f ( n )). La clase de la izquierda implica poca notación o, refiriéndose al conjunto de problemas de decisión que se pueden resolver en un tiempo asintóticamente menor que f ( n ).

En particular, esto muestra que si y sólo si , entonces tenemos una jerarquía de tiempo infinita. ${\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}$ ${\displaystyle a<b}$

El teorema de la jerarquía temporal para las máquinas de Turing no deterministas fue probado originalmente por Stephen Cook en 1972. ^[3] Fue mejorado a su forma actual mediante una demostración compleja por Joel Seiferas, Michael Fischer y Albert Meyer en 1978. ^[4] Finalmente en 1983 Stanislav Žák logró el mismo resultado con la sencilla demostración que se enseña hoy. ^[5] El teorema de la jerarquía temporal para las máquinas de Turing no deterministas establece que si g ( n ) es una función construible en el tiempo, y f ( n +1) = o ( g ( n )), entonces

${\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))}$.

Los teoremas análogos para el espacio son los teoremas de jerarquía espacial . No se conoce un teorema similar para las clases de complejidad probabilística con límite de tiempo, a menos que la clase también tenga algún consejo . ^[6]

Fondo

Ambos teoremas utilizan la noción de función construible en el tiempo . Una función es construible en el tiempo si existe una máquina de Turing determinista tal que para cada , si la máquina se inicia con una entrada de n unos, se detendrá exactamente después de f ( n ) pasos. Todos los polinomios con coeficientes enteros no negativos son construibles en el tiempo, al igual que funciones exponenciales como 2 ⁿ . ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$

Resumen de pruebas

Necesitamos demostrar que alguna clase de tiempo TIME ( g ( n )) es estrictamente mayor que alguna clase de tiempo TIME ( f ( n )). Hacemos esto construyendo una máquina que no puede estar en el TIEMPO ( f ( n )), por diagonalización . Luego demostramos que la máquina está en TIEMPO ( g ( n )), usando una máquina simuladora .

Teorema determinista de la jerarquía del tiempo

Declaración

Teorema de la jerarquía del tiempo. Si f ( n ) es una función construible en el tiempo, entonces existe un problema de decisión que no puede resolverse en el tiempo determinista del peor de los casos o ( f ( n ) ), pero puede resolverse en el tiempo determinista del peor de los casos O ( f ( n ) )log f ( n )). De este modo

${\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).}$

Nota 1. f ( n ) es al menos n , ya que las funciones más pequeñas nunca son construibles en el tiempo.

Ejemplo. Hay problemas que se pueden resolver en el tiempo n log ² n pero no en el tiempo n . Esto sigue estableciendo , ya que n está en ${\displaystyle f(n)=n\log n}$

${\displaystyle o\left(n\log n\right).}$

Prueba

Incluimos aquí una prueba de un resultado más débil, a saber, que DTIME ( f ( n )) es un subconjunto estricto de DTIME ( f (2 n + 1) ³ ), ya que es más simple pero ilustra la idea de la prueba. Consulte la parte inferior de esta sección para obtener información sobre cómo extender la prueba a f ( n ) log f ( n ).

Para probar esto, primero definimos el lenguaje de las codificaciones de las máquinas y sus entradas que las hacen detenerse dentro de f.

${\displaystyle H_{f}=\left\{([M],x)\ |\ M\ {\text{accepts}}\ x\ {\text{in}}\ f(|x|)\ {\text{steps}}\right\}.}$

Observe aquí que esta es una clase de tiempo. Es el conjunto de pares de máquinas y entradas a esas máquinas ( M , x ) de modo que la máquina M acepta dentro de f (| x |) pasos.

Aquí, M es una máquina de Turing determinista y x es su entrada (el contenido inicial de su cinta). [ M ] denota una entrada que codifica la máquina de Turing M . Sea m el tamaño de la tupla ([ M ], x ).

Sabemos que podemos decidir la pertenencia de H _f mediante una máquina de Turing determinista R , que simula M para f ( x ) pasos calculando primero f (| x |) y luego escribiendo una fila de ceros de esa longitud, y luego use esta fila de 0 como "reloj" o "contador" para simular M durante como máximo esa cantidad de pasos. En cada paso, la máquina simuladora necesita revisar la definición de M para decidir cuál sería la siguiente acción. Es seguro decir que esto requiere como máximo f ( m ) ³ operaciones (ya que se sabe que se puede lograr una simulación de una máquina de complejidad temporal T ( n ) en el tiempo en una máquina multicinta, donde | M | es la longitud de la codificación de M ), tenemos que: ${\displaystyle O(T(n)\cdot |M|)}$

${\displaystyle H_{f}\in {\mathsf {TIME}}\left(f(m)^{3}\right).}$

El resto de la prueba demostrará que

${\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)}$

de modo que si sustituimos m por 2 n + 1 , obtenemos el resultado deseado. Supongamos que Hf se _encuentra en esta clase de complejidad temporal y llegaremos a una contradicción.

Si H _f está en esta clase de complejidad temporal, entonces existe una máquina K que, dada alguna descripción de la máquina [ M ] y la entrada x , decide si la tupla ([ M ], x ) está en H _f dentro de

${\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}$

Usamos esta K para construir otra máquina, N , que toma una descripción de máquina [ M ] y ejecuta K en la tupla ([ M ], [ M ]), es decir. M es simulado en su propio código por K , y luego N acepta si K rechaza y rechaza si K acepta. Si n es la longitud de la entrada a N , entonces m (la longitud de la entrada a K ) es el doble de n más algún símbolo delimitador, por lo que m = 2 n + 1. El tiempo de ejecución de N es, por tanto,

${\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {2n+1}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f(n)\right).}$

Ahora, si alimentamos [ N ] como entrada en el propio N (lo que hace que n sea la longitud de [ N ]) y preguntamos si N acepta su propia descripción como entrada, obtenemos:

• Si N acepta [ N ] (lo que sabemos que hace como máximo en f ( n ) operaciones ya que K se detiene en ([ N ], [ N ]) en f ( n ) pasos), esto significa que K rechaza ([ N ] , [ N ]), por lo que ([ N ], [ N ]) no está en H _f , y por lo tanto, según la definición de H _f , esto implica que N no acepta [ N ] en f ( n ) pasos. Contradicción.

• Si N rechaza [ N ] (lo que sabemos que hace en la mayoría de f ( n ) operaciones), esto significa que K acepta ([ N ], [ N ]), entonces ([ N ], [ N ]) está en H _f , y por lo tanto N acepta [ N ] en f ( n ) pasos. Contradicción.

Por lo tanto concluimos que la máquina K no existe, y por lo tanto

${\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}$

Extensión

El lector puede haberse dado cuenta de que la prueba da el resultado más débil porque hemos elegido una simulación simple de la máquina de Turing para la cual sabemos que

${\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)^{3}).}$

Se sabe ^[7] que existe una simulación más eficiente la cual establece que

${\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)\log f(m))}$.

Teorema de jerarquía temporal no determinista

Si g ( n ) es una función construible en el tiempo, y f ( n +1) = o ( g ( n )), entonces existe un problema de decisión que no puede resolverse en un tiempo no determinista f ( n ) pero puede ser resuelto en tiempo no determinista g ( n ). En otras palabras, la clase de complejidad NTIME ( f ( n )) es un subconjunto estricto de NTIME ( g ( n )).

Consecuencias

Los teoremas de la jerarquía temporal garantizan que las versiones determinista y no determinista de la jerarquía exponencial son jerarquías genuinas: en otras palabras, P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... y NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....

Por ejemplo, desde . De hecho, del teorema de la jerarquía temporal. ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$ ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}$ ${\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}$

El teorema también garantiza que hay problemas en P que requieren exponentes arbitrariamente grandes para resolverse; en otras palabras, P no colapsa a DTIME ( n ^k ) para cualquier k fijo . Por ejemplo, hay problemas que se pueden resolver en n ⁵⁰⁰⁰ veces pero no en n ⁴⁹⁹⁹ veces. Este es un argumento en contra de la tesis de Cobham , la convención de que P es una clase práctica de algoritmos. Si tal colapso ocurriera, podríamos deducir que P ≠ PSPACE , ya que es un teorema bien conocido que DTIME ( f ( n )) está estrictamente contenido en DSPACE ( f ( n )).

Sin embargo, los teoremas de la jerarquía temporal no proporcionan ningún medio para relacionar la complejidad determinista y no determinista, o la complejidad temporal y espacial, por lo que no arrojan luz sobre las grandes cuestiones no resueltas de la teoría de la complejidad computacional : si P y NP , NP y PSPACE , PSPACE y EXPTIME , o EXPTIME y NEXPTIME son iguales o no.

Teoremas de jerarquía más nítidos

La brecha de aproximadamente entre el límite de tiempo inferior y superior en el teorema de la jerarquía se puede atribuir a la eficiencia del dispositivo utilizado en la demostración, es decir, un programa universal que mantiene un conteo de pasos. Esto se puede hacer de manera más eficiente en ciertos modelos computacionales. Los mejores resultados, que se presentan a continuación, se han demostrado para: ${\displaystyle \log f(n)}$

• La máquina de acceso aleatorio de costo unitario ^[8]
• Un modelo de lenguaje de programación cuyos programas operan en un árbol binario al que siempre se accede a través de su raíz. Este modelo, introducido por Neil D. Jones ^[9], es más fuerte que una máquina de Turing determinista pero más débil que una máquina de acceso aleatorio.

Para estos modelos, el teorema tiene la siguiente forma:

Si f ( n ) es una función construible en el tiempo, entonces existe un problema de decisión que no puede resolverse en el tiempo determinista del peor de los casos f ( n ) pero que puede resolverse en el tiempo del peor de los casos af ( n ) para alguna constante a ( dependiente de f ).

Por tanto, un aumento de factor constante en el límite de tiempo permite resolver más problemas, en contraste con la situación de las máquinas de Turing (ver Teorema de aceleración lineal ). Además, Ben-Amram demostró ^[10] que, en los movimientos anteriores, para f de tasa de crecimiento polinomial (pero más que lineal), se da el caso de que, para todos , existe un problema de decisión que no puede resolverse en el peor de los casos. tiempo determinista f ( n ) pero se puede resolver en el peor de los casos . ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )f(n)}$

Ver también

• Teorema de la jerarquía espacial

Referencias

1. Hartmanis, J .; Stearns, RE (1 de mayo de 1965). "Sobre la complejidad computacional de los algoritmos". Transacciones de la Sociedad Matemática Estadounidense . 117 . Sociedad Estadounidense de Matemáticas: 285–306. doi : 10.2307/1994208 . ISSN  0002-9947. JSTOR  1994208. SEÑOR  0170805.
2. Hennie, FC; Stearns, RE (octubre de 1966). "Simulación de dos cintas de máquinas de Turing multicinta". J. ACM . 13 (4). Nueva York, NY, EE.UU.: ACM: 533–546. doi : 10.1145/321356.321362 . ISSN  0004-5411. S2CID  2347143.
3. Cocinero, Stephen A. (1972). "Una jerarquía para la complejidad temporal no determinista". Actas del cuarto simposio anual de ACM sobre teoría de la informática . STOC '72. Denver, Colorado, Estados Unidos: ACM. págs. 187-192. doi : 10.1145/800152.804913 .
4. Seiferas, Joel I.; Fischer, Michael J .; Meyer, Albert R. (enero de 1978). "Separación de clases de complejidad temporal no deterministas". J. ACM . 25 (1). Nueva York, NY, EE.UU.: ACM: 146–167. doi : 10.1145/322047.322061 . ISSN  0004-5411. S2CID  13561149.
5. Žák, Stanislav (octubre de 1983). "Una jerarquía temporal de la máquina de Turing". Informática Teórica . 26 (3). Elsevier Science BV: 327–333. doi : 10.1016/0304-3975(83)90015-4 .
6. Fortnow, L.; Santhanam, R. (2004). "Teoremas de jerarquía para el tiempo polinomial probabilístico". 45º Simposio anual del IEEE sobre fundamentos de la informática . pag. 316. doi : 10.1109/FOCS.2004.33. ISBN 0-7695-2228-9. S2CID  5555450.
7. Sipser, Michael (27 de junio de 2012). Introducción a la Teoría de la Computación (3ª ed.). Aprendizaje Cengage. ISBN 978-1-133-18779-0.
8. Sudborough, Ivan H.; Zalcberg, A. (1976). "Sobre familias de lenguas definidas por máquinas de acceso aleatorio con límite de tiempo". Revista SIAM de Computación . 5 (2): 217–230. doi :10.1137/0205018.
9. Jones, Neil D. (1993). "Los factores constantes sí importan". 25º Simposio sobre Teoría de la Computación : 602–611. doi :10.1145/167088.167244. S2CID  7527905.
10. Ben-Amram, Amir M. (2003). "Jerarquías de tiempo de factor constante más estrictas". Cartas de procesamiento de información . 87 (1): 39–44. doi :10.1016/S0020-0190(03)00253-9.

Otras lecturas

• Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación PWS. ISBN 0-534-94728-X.Páginas 310–313 de la sección 9.1: Teoremas de jerarquía.
• Christos Papadimitriou (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1.Sección 7.2: El teorema de la jerarquía, págs. 143-146.