El teorema de la jerarquía temporal para máquinas de Turing deterministas fue probado por Richard Stearns y Juris Hartmanis.
Más concretamente, el teorema de jerarquía temporal para máquinas de Turing deterministas dice que para toda función computable
[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
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.
es computable si existe una máquina de Turing determinista tal que por cada
, si la máquina empieza con una entrada de n unos, se parará precisamente tras
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 TIME(f(n)) mediante diagonalización.
Entonces mostramos que la máquina pertenece a TIME(g(n)), mediante modelado numérico.
una función computable, entonces existe un problema de decisión el cual no puede ser resuelto en el mejor caso de tiempo determinista
pero que puede ser resuelto el peor caso de tiempo determinista
En otras palabras, la clase de complejidad DTIME
es al menos n, pues funciones más pequeñas no serían computables.
Incluimos aquí una prueba de que DTIME(f(n)) es un subconjunto estricto de DTIME(f(2n + 1)3) 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)2.
Para probarlo, primero definimos el siguiente lenguaje: Siendo M una máquina de Turing determinista, y x su entrada (el contenido inicial de su cinta).
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.
Asumamos que Hf es en esa clase de complejidad temporal, e intentemos llegar a una contradicción.
Si Hf 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 Hf dentro de
Por consiguiente podremos usar esa K para construir otra máquina, N, la cual tome una descripción de máquina [M], ejecute K en la tupla ([M], [M]), y acepte solo 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.
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: Por tanto concluimos que la máquina K no existe, de lo cual 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 Se ha mostrado[4] que un modelo de simulación más eficiente existe el cual establece que pero como ese modelo de simulación se ve bastante elaborado, no se incluye aquí.
En otras palabras, la clase de complejidad NTIME(f(n)) es un subconjunto estricto de NTIME(g(n)).
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 ⊂ ...
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(nk) para ninguna k constante.
Si esa convergencia ocurriese, podríamos deducir que P ≠ PSPACE, puesto que un teorema conocido establece que DTIME(f(n)) está estrictamente contenido en DSPACE(f(n)).