next up previous contents
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{displaymath}\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}\end{displaymath}

El siguiente teorema determina diferentes niveles de complejidad espacial.

Teorema 4.1   Sean s1 y s2 dos funciones constructibles en espacio, ambas mayores que log. Si

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

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 s2(n) casillas. Como s2 es constructible en espacio esto se logra haciendo correr ``en paralelo'' a M con una máquina que construye a s2. 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 Mi.
3.
M reconoce a $\mbox{\bf x}$ si
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 s2 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.
next up previous contents
Siguiente: Jerarquía en tiempo Un nivel arriba: Teoremas de jerarquía Anterior: Tiempos y espacios
Guillermo Morales-Luna
2000-07-10