Hispanopedia Wiki
Articulo de referencia

Teorema de la jerarquía temporal

En la teoría de la complejidad computacional , los teoremas de jerarquía temporal son enunciados importantes sobre la computación con límite de tiempo en máquinas de Turing . De...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , los teoremas de jerarquía temporal son enunciados importantes sobre la computación con límite de tiempo en máquinas de Turing . De manera informal, estos teoremas indican que, con 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 la entrada.

El teorema de jerarquía temporal para máquinas de Turing deterministas de múltiples cintas 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 ] Como consecuencia del teorema, para cada clase de complejidad determinista acotada en el tiempo , existe una clase de complejidad acotada en el tiempo estrictamente mayor, por lo que la jerarquía acotada en el tiempo de las 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 ), DTIMETROmi(o(F(norte)))⊊DTIMETROmi(F(norte)registro⁡F(norte)),{\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 resolubles en tiempo O ( f ( n )). La clase de la izquierda utiliza la notación o pequeña , refiriéndose al conjunto de problemas de decisión resolubles en un tiempo asintóticamente menor que f ( n ).

En particular, esto demuestra queDTIMETROmi(nortea)⊊DTIMETROmi(norteb){\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}si y solo sia<b{\displaystyle a<b}, por lo tanto, tenemos una jerarquía de tiempo infinita.

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 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 demostración simple que se enseña hoy en día. [ 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 norteTIMETROmi(F(norte))⊊norteTIMETROmi(gramo(norte)).{\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 una función construible en el tiempo . Una funciónF:norte→norte{\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }es construible en el tiempo si existe una máquina de Turing determinista tal que para cadanorte∈norte{\displaystyle n\in \mathbb {N} }, si la máquina se inicia con una entrada de n unos, se detendrá después de precisamente f ( n ) pasos. Todos los polinomios con coeficientes enteros no negativos son construibles en el tiempo, al igual que las funciones exponenciales como 2 n .

Resumen de la demostración

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 )), mediante diagonalización . Luego mostramos que la máquina está en TIEMPO ( g ( n )), usando una máquina simuladora .

Teorema de 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 puede resolverse en el peor caso de tiempo determinista o ( f ( n )) pero sí puede resolverse en el peor caso de tiempo determinista O ( f ( n )log f ( n )). Por lo tanto,

DTIMETROmi(o(F(norte)))⊊DTIMETROmi(F(norte)registro⁡F(norte)).{\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).} De forma equivalente, siF,gramo{\displaystyle f,g}son construibles en el tiempo yF(norte)ln⁡F(norte)=o(gramo(norte)){\displaystyle f(n)\ln f(n)=o(g(n))}, entonces

DTIMETROmi(F(norte))⊊DTIMETROmi(gramo(norte)){\displaystyle {\mathsf {DTIME}}(f(n))\subsetneq {\mathsf {DTIME}}(g(n))}

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

Ejemplo.DTIMETROmi(norte)⊊DTIMETROmi(norte(ln⁡norte)2){\displaystyle {\mathsf {DTIME}}(n)\subsetneq {\mathsf {DTIME}}(n(\ln n)^{2})}.

Prueba

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

Para demostrar esto, primero definimos el lenguaje de las codificaciones de las máquinas y sus entradas que hacen que se detengan en f (| x |) pasos: HF={([METRO],incógnita) | METRO acepta incógnita en F(|incógnita|) pasos}.{\displaystyle H_{f}=\left\{([M],x)\ |\ M\ {\text{acepta}}\ x\ {\text{en}}\ f(|x|)\ {\text{pasos}}\right\}.}

Nótese que se trata de una clase temporal. Es el conjunto de pares de máquinas y entradas a esas máquinas ( M , x ) de modo que la máquina M acepta en 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 a H f mediante una máquina de Turing determinista R , que simula M durante f ( x ) pasos calculando primero f (| x |) y luego escribiendo una fila de 0s de esa longitud, y luego usando esta fila de 0s 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ía la siguiente acción. Se puede decir con seguridad que esto toma como máximo f ( m ) 3 operaciones (ya que se sabe que una simulación de una máquina de complejidad temporal T ( n ) para se puede lograr en tiempoO(T(norte)⋅|METRO|){\displaystyle O(T(n)\cdot |M|)}en una máquina multitape, donde | M | es la longitud de la codificación de M ), tenemos que: HF∈TIMETROmi(F(metro)3).{\displaystyle H_{f}\in {\mathsf {TIME}}\left(f(m)^{3}\right).}

El resto de la prueba demostrará que HF∉TIMETROmi(F(⌊metro2⌋)){\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 pertenece a 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 máquina [ M ] y entrada x , decide si la tupla ([ M ], x ) está en H f dentro de TIMETROmi(F(⌊metro2⌋)).{\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 = 2n + 1. El tiempo de ejecución de N es, por lo tanto, TIMETROmi(F(⌊metro2⌋))=TIMETROmi(F(⌊2norte+12⌋))=TIMETROmi(F(norte)).{\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 introducimos [ N ] como entrada en N' y nos preguntamos si N acepta su descripción 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 tanto ([ 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'] (que sabemos que lo hace en como máximo f(n) operaciones), esto significa que K acepta ([ N'], [ N']), por lo tanto ([ 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 consiguiente, HF∉TIMETROmi(F(⌊metro2⌋)).{\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 demostración da el resultado más débil porque hemos elegido una simulación simple de máquina de Turing para la cual sabemos que HF∈TIMETROmi(F(metro)3).{\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)^{3}).}

Se sabe [ 7 ] que existe una simulación más eficiente que establece que HF∈TIMETROmi(F(metro)registro⁡F(metro)).{\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 tiempo y f ( n +1) = o ( g ( n )), entonces existe un problema de decisión que no puede resolverse en tiempo no determinista f ( n ) pero sí puede resolverse 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 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,PAG⊊miincógnitaPAGTIMETROmi{\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}desdePAG⊆DTIMETROmi(2norte)⊊DTIMETROmi(22norte)⊆miincógnitaPAGTIMETROmi{\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}. En efecto,DTIMETROmi(2norte)⊆DTIMETROmi(o(22norte2norte))⊊DTIMETROmi(22norte){\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}del teorema de la jerarquía temporal.

El teorema también garantiza que existen problemas en P que requieren exponentes arbitrariamente grandes para su resolución; en otras palabras, P no se reduce a DTIME ( n k ) para ningún k fijo . Por ejemplo, hay problemas que se pueden resolver en n 5000 tiempo, pero no en n 4999 tiempo. 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 se produjera tal reducción, 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, ni la complejidad temporal y espacial, 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.

Teoremas de jerarquía más precisos

La brecha de aproximadamenteregistro⁡F(norte){\displaystyle \log f(n)}La discrepancia entre los límites de tiempo inferior y superior en el teorema de jerarquía se debe a la eficiencia del dispositivo utilizado en la demostración, concretamente un programa universal que mantiene un contador de pasos. Esto se puede realizar de forma más eficiente en ciertos modelos computacionales. Los resultados más precisos, que se presentan a continuación, se han demostrado para:

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 peor caso de tiempo determinista f ( n ) pero se puede resolver en el peor caso de tiempo af ( n ) para alguna constante a (que depende 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 (véase el 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), se cumple que para todoε>0{\displaystyle \varepsilon >0}, existe un problema de decisión que no se puede resolver en el peor caso de tiempo determinista f ( n ) pero se puede resolver en el peor caso de tiempo(1+ε)F(norte){\displaystyle (1+\varepsilon )f(n)}.

Véase también

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 multitapa" . 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). "Separando 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.). CENGAGE learning. 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ímite de tiempo". SIAM Journal on Computing . 5 (2): 217– 230. doi : 10.1137/0205018 .
  9. ↑ Jones, Neil D. (1993). "Los factores de tiempo constante sí importan". Actas del vigésimo quinto simposio anual de la ACM sobre Teoría de la Computación - STOC '93 . págs. 602–611 . doi : 10.1145/167088.167244 . ISBN  0-89791-591-7. S2CID 7527905 . 
  10. ↑ Ben-Amram, Amir M. (2003). "Jerarquías de tiempo de factor constante más estrictas". Information Processing Letters . 87 (1): 39– 44. doi : 10.1016/S0020-0190(03)00253-9 .

Lecturas adicionales

  • 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 .

Obtenido de " https://en.wikipedia.org/w/index.php?title=Time_hierarchy_theorem&oldid=1330565043 "