Siguiente: Jerarquía en tiempo Un nivel arriba: Teoremas de jerarquía Anterior: Tiempos y espacios

Jerarquía en espacio

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

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

El siguiente teorema determina diferentes niveles de complejidad espacial.

Teorema 4.1   Sean s₁ y s₂ dos funciones constructibles en espacio, ambas mayores que log. Si

$$\liminf_{n\rightarrow +\infty}\frac{s_1(n)}{s_2(n)}=0,$$

entonces $\mbox{\rm DSPACE}(s_1)\subset \mbox{\rm DSPACE}(s_2)$ y la inclusión es propia.

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

1.

M marca s₂(n) casillas. Como s₂ es constructible en espacio esto se logra haciendo correr ``en paralelo'' a M con una máquina que construye a s₂. En todo momento, si M fuera a ocupar espacio fuera de lo marcado se la detiene y se suspende su corrida sin reconocimiento.

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 ocupa espacio s₁,
• M realiza la simulación de M_i sobre $\mbox{\bf x}_i$ en espacio s₂(n), y
• M_i NO acepta a $\mbox{\bf x}_i$.

Claramente $M\in\mbox{\rm DSPACE}(s_2)$. Veamos que $M\not\in\mbox{\rm DSPACE}(s_1)$. En efecto, si acaso $M\in\mbox{\rm DSPACE}(s_1)$, entonces $\exists n:\; M=M_n\in\mbox{\rm DSPACE}(s_1).$ De hecho, existiría una sucesión creciente de índices $\left(\phi(n)\right)_n$ tal que $M_{\phi(n)}\in \mbox{\rm DSPACE}(s_1)$ es equivalente a M. Ya que ${\displaystyle \liminf_{n\rightarrow +\infty}\frac{s_1(n)}{s_2(n)}=0,}$ se tiene que para cualquier constante positiva c, $\exists m:\;n>m\Rightarrow c\vert s_1(n)\vert < \vert s_2(n)\vert.$ Así pues, para n suficientemente grande M podría simular en espacio s₂ 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 está en contradicción con la definición de M. q.e.d.
Siguiente: Jerarquía en tiempo Un nivel arriba: Teoremas de jerarquía Anterior: Tiempos y espacios