Siguiente: Algunas relaciones entre clases Un nivel arriba: Teoremas de jerarquía Anterior: Jerarquía en espacio

Jerarquía en tiempo

Una función t se dice ser constructible en tiempo si $\exists M\in {\cal C}$ tal que

$$\begin{array}{lcl} \mbox{\rm i) } t_M\asymp t &\mbox{\rm y }... ...ox{\bf x})\&\mbox{\it tiem}_{M}(\mbox{\bf x})=t(n) \end{array}$$

El siguiente teorema determina diferentes niveles de complejidad temporal.

Teorema 5.1   Sean t₁ y t₂ dos funciones constructibles en tiempo. Si

$$\liminf_{n\rightarrow +\infty}\frac{t_1(n)\log t_1(n)}{t_2(n)}=0,$$

entonces $\mbox{\rm DTIME}(t_1)\subset \mbox{\rm DTIME}(t_2)$ y la inclusión es propia.

Demostración: La demostración es similar al caso espacial. La condición de límite es más fuerte debido al siguiente

Lema 5.1   Si M es una máquina de Turing de varias cintas y función de tiempo t entonces existe una máquina de Turing M₁ equivalente a ella con tan sólo dos cintas y función de tiempo $t_1=t\log t.$

Construiremos una máquina M tal que $M\in\mbox{\rm DTIME}(t_2)- \mbox{\rm DTIME}(t_1).$ Para una entrada $\mbox{\bf x}$ con $n=\mbox{\it long}(\mbox{\bf x})$, M funciona como sigue:

1.

En todo momento M corre ``en paralelo'' con una máquina que construye en tiempo a t₂.

2.

Calcula i tal que $\mbox{\bf x}=\mbox{\bf x}_i$ y la máquina M_i.

3.

M reconoce a $\mbox{\bf x}$ si

• M_i corre en tiempo t₁,
• M realiza la simulación de M_i sobre $\mbox{\bf x}_i$ en tiempo t₂(n), y
• M_i NO acepta a $\mbox{\bf x}_i$.

Claramente $M\in\mbox{\rm DTIME}(t_2)$. Veamos que $M\not\in\mbox{\rm DTIME}(t_1)$. En efecto, si acaso $M\in\mbox{\rm DTIME}(t_1)$, entonces $\exists n:\; M=M_n\in\mbox{\rm DTIME}(t_1).$ De hecho, existiría una sucesión creciente de índices $\left(\phi(n)\right)_n$ tal que $M_{\phi(n)}\in \mbox{\rm DTIME}(t_1)$ sería equivalente a M. Ya que ${\displaystyle \liminf_{n\rightarrow +\infty}\frac{t_1(n)\log t_1(n)}{t_2(n)}=0,}$ se tiene que para cualquier constante positiva c, $\exists m:\;n>m\Rightarrow c\vert t_1(n)\log t_1(n)\vert < \vert t_2(n)\vert.$ Así pues, para n suficientemente grande M podría simular en tiempo t₂ a $M_{\phi(n)}$ a partir de la entrada inicial $\mbox{\bf x}_{\phi(n)}$. En estas condiciones se tendría $\forall n: \; (M \mbox{\rm reconoce a }\mbox{\bf x}_{\phi(n)}\;\Leftrightarrow\; M_{\phi(n)} \mbox{\rm reconoce a }\mbox{\bf x}_{\phi(n)}),$ lo cual entra en contradicción con la definición de M. q.e.d.
Siguiente: Algunas relaciones entre clases Un nivel arriba: Teoremas de jerarquía Anterior: Jerarquía en espacio