Teorema de la jerarquía temporal

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 jerarquía temporal son afirmaciones 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 ² tiempos, pero no con n tiempos, donde n es la longitud de entrada.

El teorema de jerarquía temporal para máquinas de Turing multicinta deterministas fue demostrado por primera vez por Richard E. Stearns y Juris Hartmanis en 1965. ^[1] Fue mejorado un año después cuando FC Hennie y Richard E. Stearns mejoraron la eficiencia de la máquina de Turing universal . ^{[2] Consecuentemente con el teorema, para cada} clase de complejidad determinista limitada en el tiempo , existe una clase de complejidad limitada en el tiempo estrictamente mayor, y por lo tanto la jerarquía limitada en el tiempo de clases de complejidad no colapsa por completo. Más precisamente, el teorema de jerarquía temporal para máquinas de Turing deterministas 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 solucionables en un tiempo O ( f ( n )). La clase de la izquierda implica poca notación o , refiriéndose al conjunto de problemas de decisión solucionables en un tiempo asintóticamente menor que f ( n ).

En particular, esto demuestra 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 jerarquía temporal para máquinas de Turing no deterministas fue demostrado originalmente por Stephen Cook en 1972. ^[3] Fue mejorado a su forma actual a través de una prueba compleja por Joel Seiferas, Michael Fischer y Albert Meyer en 1978. ^[4] Finalmente en 1983, Stanislav Žák logró el mismo resultado con la prueba simple que se enseña hoy. ^[5] El teorema de jerarquía temporal para 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 clases de complejidad probabilística limitadas en el tiempo, a menos que la clase también tenga un consejo . ^[6]

Fondo

Ambos teoremas utilizan la noción de una 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 pone en marcha con una entrada de n unos, se detendrá después de exactamente f ( n ) pasos. Todos los polinomios con coeficientes enteros no negativos son construibles en el tiempo, al igual que las funciones exponenciales como 2 ⁿ . ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$

Resumen de la prueba

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

Teorema de la jerarquía temporal determinista

Declaración

Teorema de la jerarquía temporal. Si f ( n ) es una función construible en el tiempo, entonces existe un problema de decisión que no se puede resolver en el tiempo determinista del peor caso o ( f ( n )) pero sí se puede resolver en el tiempo determinista del peor caso O ( f ( n )log f ( n )). Por lo tanto

${\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 tiempo n log ² n pero no en tiempo n . Esto se deduce de establecer , 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 demostrarlo, primero definimos el lenguaje de las codificaciones de las máquinas y sus entradas que hacen que se detengan en un lapso de tiempo.

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

Observe aquí que se trata de una clase temporal. Es el conjunto de pares de máquinas y entradas a esas máquinas ( M , x ) 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 0 de esa longitud, y luego usando esta fila de 0 como un "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á la siguiente acción. Es seguro decir que esto requiere como máximo f ( m ) ³ operaciones (ya que se sabe que una simulación de una máquina de complejidad temporal T ( n ) para se puede lograr 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 mostrará que

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

De modo que si sustituimos 2 n + 1 por m obtenemos el resultado deseado. Supongamos que H _f está 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 una descripción de máquina [ M ] y una 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 simulada 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 entonces

${\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 bien, si introducimos [ N ] como entrada en N mismo (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 cual sabemos que hace en como máximo 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, por la definición de H _f , esto implica que N no acepta [ N ] en f ( n ) pasos. Contradicción.

• Si N rechaza [ N ] (lo cual sabemos que hace en como máximo f ( n ) operaciones), esto significa que K acepta ([ N ], [ N ]), por lo que ([ N ], [ N ]) está en H _f , y por lo tanto N acepta [ N ] en f ( n ) pasos. Contradicción.

Concluimos entonces 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 de máquina de Turing simple para la que sabemos que

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

Se sabe ^[7] que existe una simulación más eficiente que 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 se puede resolver en un tiempo no determinista f ( n ) pero sí en un 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 jerarquía temporal garantizan que las versiones deterministas y no deterministas de la jerarquía exponencial sean jerarquías genuinas: en otras palabras, P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... y NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....

Por ejemplo, desde . En efecto, a partir 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 solucionables 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 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 preguntas sin resolver 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 diferencia aproximada entre el límite de tiempo inferior y superior en el teorema de jerarquía se puede atribuir a la eficiencia del dispositivo utilizado en la prueba, es decir, un programa universal que mantiene un recuento de pasos. Esto se puede hacer de manera más eficiente en ciertos modelos computacionales. Los resultados más precisos, que se presentan a continuación, se han demostrado para: ${\displaystyle \log f(n)}$

• La máquina de acceso aleatorio de coste unitario ^[8]
• 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 se puede resolver en el tiempo determinista del peor caso f ( n ), pero sí se puede resolver en el tiempo del peor caso af ( n ) para alguna constante a (dependiente de f ).

Por lo 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 modelos anteriores, para f de tasa de crecimiento polinomial (pero más que lineal), es el caso de que para todo , existe un problema de decisión que no se puede resolver en el tiempo determinista del peor caso f ( n ) pero se puede resolver en el tiempo del peor caso . ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )f(n)}$

Véase también

• Teorema de jerarquía espacial

Referencias

1. Hartmanis, J. ; Stearns, RE (1 de mayo de 1965). "Sobre la complejidad computacional de los algoritmos". Transactions of the American Mathematical Society . 117 . American Mathematical Society: 285–306. doi : 10.2307/1994208 . ISSN  0002-9947. JSTOR  1994208. MR  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. Cook, Stephen A. (1972). "Una jerarquía para la complejidad temporal no determinista". Actas del cuarto simposio anual de la ACM sobre teoría de la computación . 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 determinista". 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 IEEE sobre fundamentos de la informática . pág. 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 lenguajes definidos por máquinas de acceso aleatorio con límites temporales". Revista SIAM de informática . 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 temporales de factores constantes más estrictas". Information Processing Letters . 87 (1): 39–44. doi :10.1016/S0020-0190(03)00253-9.

Lectura adicional

• Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. 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.