En la teoría de la complejidad computacional , los teoremas de la 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 con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que pueden resolverse con n 2 tiempos pero no n tiempo.
Richard E. Stearns y Juris Hartmanis probaron por primera vez el teorema de la jerarquía de tiempo para las máquinas de Turing deterministas de cintas múltiples en 1965. [1] Se mejoró un año después cuando FC Hennie y Richard E. Stearns mejoraron la eficiencia de la máquina de Turing universal. . [2] Como consecuencia del teorema, para cada clase de complejidad determinista limitada en el tiempo , existe una clase de complejidad limitada en el tiempo estrictamente mayor, por lo que la jerarquía de clases de complejidad limitada en el tiempo no colapsa por completo. Más precisamente, el teorema de la jerarquía temporal para máquinas de Turing deterministas establece que para todas las funciones construibles en el tiempo f ( n ),
- .
El teorema de la jerarquía de tiempo para las máquinas de Turing no deterministas fue probado originalmente por Stephen Cook en 1972. [3] Fue mejorado a su forma actual a través de una demostración compleja de Joel Seiferas, Michael Fischer y Albert Meyer en 1978. [4] Finalmente en 1983. , Stanislav Žák logró el mismo resultado con la demostración simple 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 )),
- .
Los teoremas análogos para el espacio son los teoremas de la jerarquía espacial . No se conoce un teorema similar para las 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 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 arranca 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 funciones exponenciales como 2 n .
Resumen de la prueba
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 TIEMPO ( f ( n )), por diagonalización . Luego mostramos que la máquina está en TIEMPO ( g ( n )), usando una máquina simuladora .
Teorema de la jerarquía de tiempo determinista
Declaración
Teorema de la jerarquía temporal. Si f ( n ) es una función que se puede construir en el tiempo, entonces existe un problema de decisión que no puede resolverse en el tiempo determinista del peor caso f ( n ), pero puede resolverse en el tiempo determinista del peor caso f ( n ) 2 . En otras palabras,
Nota 1. f ( n ) es al menos n , ya que las funciones más pequeñas nunca son construibles en el tiempo.
Nota 2. Incluso de manera más general, se puede demostrar que si f ( n ) es construible en el tiempo, entonces
Por ejemplo, hay problemas que se pueden resolver en el tiempo n 2 pero no en el tiempo n , ya que n está en
Prueba
Incluimos aquí una prueba de que DTIME ( f ( n )) es un subconjunto estricto de DTIME ( f (2 n + 1) 3 ) ya que es más simple. Consulte la parte inferior de esta sección para obtener información sobre cómo extender la prueba af ( n ) 2 .
Para probar esto, primero definimos un lenguaje de la siguiente manera:
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 a H f mediante una máquina de Turing determinista que primero calcula f (| x |), luego escribe una fila de ceros de esa longitud y luego usa esta fila de ceros como un "reloj". o "contador" para simular M durante como máximo esa cantidad de pasos. En cada paso, la máquina de simulación necesita examinar 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 ) 3 operaciones, por lo que
El resto de la prueba mostrará que
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 e intentaremos llegar a una contradicción.
Si H f está en esta clase de complejidad de tiempo, significa que podemos construir alguna 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
Por lo tanto, podemos usar 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 ]), y luego acepta solo si K rechaza, y rechaza si K acepta. Si ahora n es la longitud de la entrada a N , entonces m (la longitud de la entrada a K ) es dos veces n más algún símbolo delimitador, entonces m = 2 n + 1. El tiempo de ejecución de N es entonces
Ahora, si alimentamos [ N ] como entrada en N mismo (lo que hace que n tenga la longitud de [ N ]) y nos preguntamos si N acepta su propia descripción como entrada, obtenemos:
- Si N acepta [ N ] (lo cual sabemos que lo hace como máximo en f ( n ) operaciones), esto significa que K rechaza ([ N ], [ N ]), por lo que ([ N ], [ N ]) no está en H f , y por lo tanto N no acepta [ N ] en f ( n ) pasos. ¡Contradicción!
- Si N rechaza [ N ] (lo cual sabemos que lo hace como máximo en f ( n ) operaciones), esto significa que K acepta ([ N ], [ N ]), por lo que ([ N ], [ N ]) está en H f , y por lo tanto N hace aceptar [ N en] f ( n ) pasos. ¡Contradicción!
Por tanto, llegamos a la conclusión de que la máquina K no existe, por lo que
Extensión
El lector puede haberse dado cuenta de que la demostración es más simple porque hemos elegido una simulación de máquina de Turing simple para la cual podemos estar seguros de que
Se ha demostrado [7] que existe un modelo de simulación más eficiente que establece que
pero como este modelo de simulación es bastante complicado, no se incluye aquí.
Teorema de jerarquía de tiempo 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 sí puede resolverse 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 deterministas y no deterministas de la jerarquía exponencial son jerarquías genuinas: en otras palabras, P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... y NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....
Por ejemplo, desde . En efecto, del teorema de la jerarquía temporal.
El teorema también garantiza que hay problemas en P que requieren exponentes arbitrariamente grandes para resolver; en otras palabras, P no colapsa a DTIME ( n k ) para cualquier k fijo . Por ejemplo, hay problemas que se pueden resolver en n 5000 veces pero no n 4999 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 del tiempo no proporcionan ningún medio para relacionar la complejidad determinista y no determinista, o la complejidad del tiempo y el espacio, por lo que no arrojan luz sobre las grandes cuestiones 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.
Ver también
Referencias
- ^ Hartmanis, J .; Stearns, RE (1 de mayo de 1965). "Sobre la complejidad computacional de los algoritmos" . Transacciones de la American Mathematical Society . Sociedad Matemática Estadounidense. 117 : 285-306. doi : 10.2307 / 1994208 . ISSN 0002-9947 . JSTOR 1994208 . Señor 0170805 .
- ^ Hennie, FC; Stearns, RE (octubre de 1966). "Simulación de dos cintas de máquinas de Turing de varias cintas". J. ACM . Nueva York, NY, EE.UU .: ACM. 13 (4): 533–546. doi : 10.1145 / 321356.321362 . ISSN 0004-5411 .
- ^ Cook, Stephen A. (1972). "Una jerarquía para la complejidad del tiempo no determinista". Actas del cuarto simposio anual ACM sobre teoría de la computación . STOC '72. Denver, Colorado, Estados Unidos: ACM. págs. 187-192. doi : 10.1145 / 800152.804913 .
- ^ Seiferas, Joel I .; Fischer, Michael J .; Meyer, Albert R. (enero de 1978). "Separación de clases de complejidad de tiempo no determinista". J. ACM . Nueva York, NY, EE.UU .: ACM. 25 (1): 146-167. doi : 10.1145 / 322047.322061 . ISSN 0004-5411 .
- ^ Žák, Stanislav (octubre de 1983). "Una jerarquía de tiempo de la máquina de Turing". Informática Teórica . Elsevier Science BV 26 (3): 327–333. doi : 10.1016 / 0304-3975 (83) 90015-4 .
- ^ Fortnow, L .; Santhanam, R. (2004). "Teoremas de jerarquía para el tiempo polinomial probabilístico". 45º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación . pag. 316. doi : 10.1109 / FOCS.2004.33 . ISBN 0-7695-2228-9.
- ^ Luca Trevisan, Notas sobre teoremas de jerarquía , UC Berkeley
- Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de 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.