Siguiente: Jerarquías en clases no-deterministas Un nivel arriba: Teoremas de jerarquía Anterior: Jerarquía en tiempo

Algunas relaciones entre clases

Las siguientes proposiciones son inmediatas:

Proposición 6.1   $\mbox{\rm DTIME}(f(n))\subset\mbox{\rm DSPACE}(f(n))$.

En efecto, si se hacen f(n) movimientos no se puede ocupar más de f(n) localidades.

Proposición 6.2   $(L\in\mbox{\rm DSPACE}(f(n)))\&(f(n)>\log n)\;\Rightarrow\;(L\in\mbox{\rm DTIME}(f(n))$.

En efecto: Si $M\in{\cal C}$ posee q estados, utiliza un alfabeto de entrada de m símbolos y ocupa espacio f(n) entonces el número de descripciones instantáneas (DI) es q(n+2)f(n)m^f(n). Como $f(n)>\log n$ existe c tal que $c^{f(n)}\geq q(n+2)f(n)m^{f(n)}$. Esta es una cota para el número de DI's a generarse por un simulador de M.

Proposición 6.3   $\mbox{\rm NTIME}(f(n))\subset\mbox{\rm DTIME}(c^{f(n)}).$

En efecto, un árbol de altura f tiene del orden de 2^O(f) nodos.

Proposición 6.4 (Lema de Savitch)   Se tiene la inclusión $\mbox{\rm NSPACE}(f(n))\subset\mbox{\rm DSPACE}(f^2(n))$ siempre que f sea constructible en espacio.

Con espacio f(n) se tiene c^f(n)=2^O(f(n)) DI's. Dadas dos DI's I,J una computación legal de longitud k+1 es una sucesión de DI's

$$I=I_0\stackrel{M}{\rightarrow}I_1\stackrel{M}{\rightarrow}\cdots\stackrel{M}{\rightarrow} I_k=J.$$

Escribamos $I\stackrel{M,2^i}{\vdash}J$ para denotar que se arriba de I a J por una computación legal de longitud 2ⁱ. Tenemos

$$I\stackrel{M,2^i}{\vdash}J\;\Leftrightarrow\;\exists K: I\stackrel{M,2^{i-1}}{\vdash}K\&K\stackrel{M,2^{i-1}}{\vdash}J.$$

Se puede revisar esto último en espacio f²(n).
Siguiente: Jerarquías en clases no-deterministas Un nivel arriba: Teoremas de jerarquía Anterior: Jerarquía en tiempo