Teorema de la jerarquía temporal

En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que pueden ser solucionados en tiempo O(n²) pero no en O(n).

El teorema de la jerarquía temporal para máquinas de Turing deterministas fue probado por Richard Stearns y Juris Hartmanis.^[1] Como consecuencia, para cada cada clase de complejidad acotada temporalmente, hay otra clase de complejidad estrictamente mayor, tal que la jerarquía de acotación temporal para clases de complejidad converja por completo. Más concretamente, el teorema de jerarquía temporal para máquinas de Turing deterministas dice que para toda función computable f(n), :$\operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \operatorname{DTIME}(f(n))$.

El teorema de jerarquía temporal para máquinas de Turing no deterministas fue probado por Stephen Cook.^[2] El teorema de la jerarquía temporal para máquinas de Turing no deterministas dice que si g(n) es una función computable, y f(n+1) = o(g(n)), entonces

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

Los teoremas análogos para espacio son los teoremas de jerarquía espacial. Para el caso de clases de complejidad probabilística acotada en el tiempo no hay teoremas similares, salvo que la clase tenga también aviso.^[3]

Introducción

Ambos teoremas usan la noción de una función computable. Una función $f:\mathbb{N}\rightarrow\mathbb{N}$ es computable si existe una máquina de Turing determinista tal que por cada $n\in\mathbb{N}$, si la máquina empieza con una entrada de n unos, se parará precisamente tras f(n) pasos. Todo polinomio con coeficientes de integración no negativos es computable, así como las funciones exponenciales tales como 2ⁿ.

Idea de la prueba

Necesitamos probar que alguna clase temporal TIME(g(n)) es estrictamente mayor que otra clase temporal TIME(f(n)). Hacemos esto construyendo una máquina tal que no se pueda dar en IME(f(n)) mediante el diagonalización. Entonces mostramos que la máquina pertenece a TIME(g(n)), mediante modelado numérico.

Teorema de la jerarquia temporal determinista

Declaración

El teorema declara que: Sea f(n) una función computable, entonces existe un problema de decisión el cual no puede ser resuelto en el peor caso de tiempo determinista f(n) pero que puede ser resuelto el el peor caso de tiempo determinista f(n)². En otras palabras, la clase de complejidad DTIME(f(n)) es un subconjunto estricto de DTIME(f(n)²). Obsérvese que f(n) es al menos n, pues funciones más pequeñas no serían computables.

Se puede generalizar que si f(n) es computable, entonces $\operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)$ es contenida en $\operatorname{DTIME}(f(n))$. Por ejemplo, hay problemas con solución en tiempo n² pero no en tiempo n, pues n está en $o\left(\frac{n^2}{\log {n^2}}\right)$.

Prueba

Teorema de la jerarquía temporal
Fecha de publicación	March 2009

Incluimos aquí una prueba de que DTIME(f(n)) es un subconjunto estricto de DTIME(f(2n + 1)³) puesto que es más sencillo. Véase el final de esta sección para encontrar información sobre cómo extender la prueba a f(n)².

Para probarlo, primero definimos el siguiente lenguaje:

$H_f = \left\{ ([M], x)\ |\ M \ \mbox{acepta}\ x \ \mbox{en}\ f(|x|) \ \mbox{pasos} \right\}.$

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

Sabemos que podemos determinar la pertenencia de H_f mediante una máquina de turing determinista que primero calcula f(|x|), y luego escribe una fila de 0s de esa longitud, y que luego usa esa fila de 0s como "reloj" o "contador" para simular M con ese límite de pasos. En cada paso, la máquina simulada necesita mirar a través de la definición de M para decidir cuál será la siguiente acción a tomar. Es seguro decir que eso conlleva como mucho f(m)³ operaciones, por lo que

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

El resto de la prueba mostrará que

$H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor ))$

por lo que si sustituimos 2n + 1 for m, tendremos el resultado deseado. Asumamos que H_f es en esa clase de complejidad temporal, e intentemos llegar a una contradicción.

Si H_f está en esta clase de complejidad temporal, significa que podemos construir alguna máquina K la cual, dada una descripción de máquina [M] y una entrada x, decide si la tupla ([M], x) está en H_f dentro de $\mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor ))$.

Por consiguiente podremos usar esa K para construir otra máquina, N, la cual tome una descripción de máquina [M] y ejecutes K en la tupla ([M], [M]), y acepte sólo si K rechaza, y rechace si K acepta. Si ahora n es la longitud de la entrada para N, entonces m (la longitud de la entrada para K) es el doble de n más algún símbolo delimitador, por lo que m = 2n + 1. Por lo tanto, el tiempo de ejecución de N $\mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) = \mathsf{TIME}(f( \left\lfloor (2n+1)/2 \right\rfloor )) = \mathsf{TIME}(f(n)).$

Si alimentamos ahora [N] como entrada en la misma N (siendo n la longitud de [N]) y preguntamos si N acepta su propia descripción como entrada, obtenemos:

• Si N acepta [N] (la cual sabemos que al menos hace f(n) operaciones), significa que K rechaza ([N], [N]), por lo que ([N], [N]) no pertenece a H_f, por lo que N no acepta [N] en f(n) pasos. ¡Contradicción!
• Si N rechaza [N] (la cual sabemos que al menos hace f(n) operaciones), significa que K acepta ([N], [N]), por lo que ([N], [N]) pertenece a H_f, por lo que N acepta [N] en f(n) pasos. ¡Contradicción!

Por tanto concluímos que la máquina K no existe, de lo cual

$H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )).$

Extensión

El lector se puede haber percatado de que la prueba es sencilla puesto que hemos elegido una simulación de una máquina de Turing sencilla, para lo cual podemos estar seguros de que

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

Se ha mostrado^[4] que un modelo de simulación más eficiente existe el cual establece que

$H_f \in \mathsf{TIME}(f(m) \log f(m))$

pero como ese modelo de simulación se ve bastante involucarado, no se incluye aquí.

Teorema de la jerarquía temporal no determinista

Si g(n) es una función computable, y f(n+1) = o(g(n)), existe un problema de decisión el cual no puede ser solucionado en tiempo no determinista f(n) pero sí 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 la versión determinista y la no determinista de la jerarquía exponencial son jerarquías genuinas: en otras palabras P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ ..., y NP ⊂ NEXPTIME ⊂ 2-EXPTIME ⊂ ... Por ejemplo, P ⊂ EXPTIME desde $P \subseteq DTIME(2^n) \subsetneq DTIME(2^{2n}) \subseteq EXPTIME$.

El teorema también garantiza que hay problemas en P que requieren exponentes arbitrariamente largos para ser resueltos; en otras palabras, P no converge a DTIME(n^k) para ninguja k constante. Por ejemplo, hay problemas solucionables en tiempo O(n⁵⁰⁰⁰) pero no en O(n⁴⁹⁹⁹). Este es un argumento contra la tesis de Cobham, la convención de que P es una clase práctica de algoritmos. Si esa convergecia ocurriese, podríamos deducir que P ≠ PSPACE, puesto que un teorema conocido estable ce que DTIME(f(n)) está estrictamente contenido en DSPACE(f(n)).

Sin embargo, los teoremas de jerarquía temporal no proporcionan medios para relacionar la complejidad determinista y la no determinista, y tampoco la complejidad espacial y temporal, por lo que no iluminan sobre las grandes cuestiones pendientes 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.

Referencias

1. ↑ «On the computational complexity of algorithms». Transactions of the American Mathematical Society 117:  pp. 285–306. 1 de mayo de 1965. doi:10.2307/1994208. ISSN 00029947. 
2. ↑ Stephen Cook (1972). A hierarchy for nondeterministic time complexity. Proceedings of the fourth annual ACM symposium on Theory of computing, pp. 187–192.
3. ↑ Fortnow, L. (2004). Hierarchy Theorems for Probabilistic Polynomial Time.  pp. 316. doi:10.1109/FOCS.2004.33. 
4. ↑ Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Páginas 310–313 de la sección 9.1: Hierarchy theorems.

• Christos Papadimitriou (1993). Computational Complexity (1a edición). Addison Wesley. ISBN 0-201-53082-1.  Sección 7.2: The Hierarchy Theorem, pp. 143–146.