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

Teorema de Borodin y consecuencias

Teorema 8.1 (Borodin)   Para cualquier función computable g, con $g(n)\geq n$, existe una función computable s_g tal que

$$\mbox{\rm DSPACE}(s_g(n))=\mbox{\rm DSPACE}(g\circ s_g(n)).$$

En otras palabras DSPACE se colapsa entre s_g y $g\circ s_g$.

Demostración: Sea $\left(M_i\right)_i$ una enumeración de los dispositivos en ${\cal C}$, y s_Mi la función de espacio de M_i, $i\geq 0$. Se construirá una función s tal que

$$\begin{array}{rcll} s_{M_i} &\leq& s &\mbox{\rm c.t.p. (casi... ...irc s&\mbox{\rm u.i.v. (una infinidad de veces).} \end{array}$$

Así pues ninguna función s_Mi puede estar ``entre'' s y $g\circ s$. Construimos s mediante el algoritmo de la Figura 6.1:

  

Figure 6.1: Construcción de la función s.

Ahora, supongamos que $L\in\mbox{\rm DSPACE}(g\circ s(n))-\mbox{\rm DSPACE}(s(n)).$ Entonces para M_i tal que L=L(M_i) tendremos $s_{M_i}\leq g\circ s\mbox{\rm c.t.p.},$ y por la construcción de s necesariamente se tendrá $n\geq i\;\Rightarrow\;s_{M_i}(n)\leq s(n),$ consecuentemente $L\in\mbox{\rm DSPACE}(s(n)),$ lo cual es una contradicción, q.e.d.

Corolario 8.1   Existe una función computable f tal que

$$\mbox{\rm DTIME}(f(n)) =\mbox{\rm NTIME}(f(n)) =\mbox{\rm DSPACE}(f(n)) =\mbox{\rm NSPACE}(f(n)).$$

Demostración: Para cualquier función g se tiene las inclusiones siguientes

$$\begin{array}{ccc} \mbox{\rm DTIME}(g(n)) & \subset & \mbox{... ... NTIME}(g(n)) & \subset & \mbox{\rm NSPACE}(g(n)) \end{array}$$

Veremos que existe f tal que $\mbox{\rm NSPACE}(f(n)) =\mbox{\rm DTIME}(f(n)).$ Vimos que para cualquier g existe c>0 tal que $\mbox{\rm NSPACE}(g(n)) \subset \mbox{\rm DTIME}(c^{g(n)}),$ y cuantimás hemos de tener $\mbox{\rm NSPACE}(g(n)) \subset \mbox{\rm DTIME}(g(n)^{g(n)}).$ Ahora, para la función G(n)=nⁿ, por el análogo del Teorema de Borodin para tiempo tenemos que $\exists f:\;\mbox{\rm DTIME}(f(n))=\mbox{\rm DTIME}(f(n)^{f(n)}).$ f es pues la función buscada. q.e.d.
Siguiente: Completitud-NP Un nivel arriba: Teoremas de jerarquía Anterior: Jerarquías en clases no-deterministas