Teorema de la jerarquía temporal

En la teoría de la complejidad computacional, los teoremas de la jerarquía del tiempo son afirmaciones importantes sobre el cálculo limitado en el tiempo en las máquinas de Turing. Informalmente, 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 tiempo n² pero no tiempo n.

El teorema de la jerarquía temporal para las máquinas de Turing deterministas de múltiples cintas fue probado por primera vez por Richard E. Stearns y Juris Hartmanis en 1965. Se mejoró un año después cuando F. C. Hennie y Richard E. Stearns mejoraron la eficiencia de la máquina Universal de Turing.. Como consecuencia del teorema, para cada clase de complejidad limitada en el tiempo determinista, hay una clase de complejidad limitada en el tiempo estrictamente más grande, 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),

DTIME()o()f()n)log⁡ ⁡ f()n)))⊊ ⊊ DTIME()f()n)){displaystyle {mathsf {}left(oleft({frac {f(n)}{log f(n)}}right)subsetneq {mathsf {mathsf {f}(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 )).

El teorema de la jerarquía temporal para las máquinas de Turing no deterministas fue probado originalmente por Stephen Cook en 1972. Joel Seiferas, Michael Fischer y Albert Meyer lo mejoraron a su forma actual mediante una prueba compleja en 1978. Finalmente, en 1983, Stanislav Žák logró el mismo resultado con la prueba simple que se enseña hoy. El teorema de la 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

NTIME()f()n))⊊ ⊊ NTIME()g()n)){displaystyle {mathsf {NTIME}(f(n))subsetneq {mathsf {NTIME}(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 limitada en el tiempo, a menos que la clase también tenga un consejo.

Antecedentes

Ambos teoremas utilizan la noción de una función reconstructible en el tiempo. Una función f:N→ → N{displaystyle f:mathbb {N} rightarrow mathbb {N} es tiempo-constructible si existe una máquina de Turing determinista tal que para cada n▪ ▪ N{displaystyle nin mathbb {N}, si la máquina se inicia con una entrada de n uno, se detendrá después precisamente f()n) pasos. Todos los polinomios con coeficientes de enteros no negativos son constructibles en el tiempo, como son funciones exponenciales como 2ⁿ.

Descripción general de la prueba

Necesitamos probar 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 mostramos 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 del Tiempo. Si f()n) es una función de tiempo-constructible, entonces existe un problema de decisión que no se puede resolver en el peor de los casos determinístico tiempo f()n) pero se puede resolver en el peor de los casos determinístico tiempo f()n)². En otras palabras,

DTIME()f()n))⊊ ⊊ DTIME()f()n)2).{displaystyle {mathsf {DTIME}(f(n)subsetneq {mathsf {DTIME}left(f(n)^{2}right). }

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

Nota 2. Aún más generalmente, se puede demostrar que si f(n) es construible en el tiempo, entonces

DTIME()o()f()n)log⁡ ⁡ f()n)))⊊ ⊊ DTIME()f()n)).{displaystyle {mathsf {}left(oleft({frac {f(n)}{log f(n)}right)subsetneq {mathsf {}left(f(n)right). }

Por ejemplo, hay problemas solucionables en el tiempo n² pero no en el tiempo n, ya que n es en

o()n2log⁡ ⁡ n2).{displaystyle oleft {frac}{log {c}}}}derecho).}

Prueba

Incluimos aquí una prueba de que DTIME(f(n)) es un subconjunto estricto de DTIME (f(2n + 1)³) ya que es más simple. Consulte la parte inferior de esta sección para obtener información sobre cómo extender la prueba a f(n)².

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

Hf={}()[M],x)SilencioMaceptaxdentrof()SilencioxSilencio)pasos}.{displaystyle H_{f}=left{(M],x) Silencio M {text{accepts} x\ {text{in}} f(Principiada) {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) para que la máquina M acepte 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 a 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 0s de esa longitud, y luego usar esta fila de 0s como un "reloj" o "contador" para simular M para como máximo esa cantidad de pasos. En cada paso, la máquina de simulación necesita revisar la definición de M para decidir cuál sería la siguiente acción. Es seguro decir que esto toma como máximo f(m)³ operaciones (ya que se sabe que una simulación de una máquina del tiempo complejidad T(n) se puede lograr en el tiempo O(TlogT)), tenemos que:

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

El resto de la prueba mostrará que

Hf∉ ∉ TIME()f()⌊m2⌋)){displaystyle No. {fnMitsf {fnMicrosoft}m}rfloor right)}

de modo que si sustituimos 2n + 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 de tiempo, entonces existe una máquina K que, dada alguna descripción de máquina [ M] e ingresa x, decide si la tupla ([M], x) está en H_f dentro

TIME()f()⌊m2⌋)).{displaystyle {mathsf {}left(fleftleftlfloor {frac {m}{2}rightrfloor 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 = 2n + 1. N's el tiempo de ejecución es así

TIME()f()⌊m2⌋))=TIME()f()⌊2n+12⌋))=TIME()f()n)).{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicros {f}}derechorfloorderecho)={mthsf {m}left(leftleftlfloor {2n+1}{2} {fright}fright}fright}frightm}m}m} {m}m}m} {m}m}m}m}m}m}m}m} {m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m}m} }

Ahora, si alimentamos [N] como entrada en N mismo (lo que hace que n tenga la longitud de [N]) y hacemos la pregunta si N acepta su propia descripción como entrada, obtenemos:

• Si N acepta [N# (que sabemos que lo hace al máximo f()n) operaciones desde K paradas ([N], [N] f()n) pasos), esto significa que K rechazos [N], [N]), así ([N], [N]) No está en H_f, y así por la definición de H_f, esto implica que N no acepta [NEn f()n) pasos. Contradicción.

• Si N rechazos [N# (que sabemos que lo hace al máximo f()n) operaciones), esto significa que K acepta [N], [N]), así ([N], [N]) es dentro H_f, y así N ¿Sí? aceptar [NEn f()n) pasos. Contradicción.

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

Hf∉ ∉ TIME()f()⌊m2⌋)).{displaystyle No. {mathsf {f}left(leftleftlfloor {frac {m}{2}rightrfloor right)right). }

Extensión

El lector puede haberse dado cuenta de que la prueba es más simple porque hemos elegido una simulación de máquina de Turing simple para la cual podemos estar seguros de que

Hf▪ ▪ TIME()f()m)3).{displaystyle H_{f}in {mathsf {TIME}(f(m)^{3}). }

Se ha demostrado que existe un modelo de simulación más eficiente que establece que

Hf▪ ▪ TIME()f()m)log⁡ ⁡ f()m)){displaystyle H_{f}in {mathsf {TIME}(f(m)log f(m)}

pero dado que este modelo de simulación es bastante complicado, no se incluye aquí.

Observe sin embargo que un argumento idéntico como arriba implica entonces que DTIME()r()f()2m+1))){displaystyle DTIME(r(f(2m+1))} no está contenido DTIME()f()m)){displaystyle DTIME(f(m)} si r()f()SilencioMSilencio+SilencioxSilencio)){displaystyle r(f(PrincipalidadM sobrevivir)} es una función que da un tiempo dentro del cual es posible simular una máquina M{displaystyle M} con la complejidad del tiempo f()n){displaystyle f(n)} sobre la entrada x{displaystyle x}.

Teorema de la 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 se puede resolver 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, P⊊ ⊊ EXPTIME{displaystyle {Mathsf}subsetneq {fnMithsf {}}} desde entonces P⊆ ⊆ DTIME()2n)⊊ ⊊ DTIME()22n)⊆ ⊆ EXPTIME{displaystyle {mathsf {}subseteq {mathsf {f}(2^{n})subsetneq {mathsf {f}(2^{2n})subseteq {mathsf {f}}}}}}}}}}} {fn0}. De hecho, DTIME()2n)⊆ ⊆ DTIME()o()22n2n))⊊ ⊊ DTIME()22n){displaystyle {mathsf {}left(2^{n}right)subseteq {fnMicrosoft}left(oleft({frac {2} {2n} {2n}right)subsetneq {mathsf {DTIME}}(2^{2n}}} desde el teorema de la jerarquía temporal.

El teorema también garantiza que hay problemas en P que requieren exponentes arbitrariamente grandes para resolverlos; en otras palabras, P no colapsa a DTIME(n^k) para cualquier k fijo. Por ejemplo, hay problemas que se pueden resolver en tiempo n⁵⁰⁰⁰ pero no en tiempo n⁴⁹⁹⁹. 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 ≠ PESPACIO, 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 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.