Siguiente: Teorema de Borodin y Un nivel arriba: Teoremas de jerarquía Anterior: Algunas relaciones entre clases

Jerarquías en clases no-deterministas

Sea ${\cal K}$ cualquiera de los símbolos $\mbox{\rm NSPACE},\mbox{\rm DSPACE},\mbox{\rm NTIME},\mbox{\rm DTIME}$.

Lema 7.1   Si F₁,F₂, f son constructibles entonces

$${\cal K}(F_1(n)) \subset{\cal K}(F_2(n)) \;\Rightarrow\; {\cal K}(F_1\circ f(n)) \subset{\cal K}(F_2\circ f(n)).$$

De aquí resulta

Teorema 7.1   Para todo $r\geq 0$ se cumple: $\epsilon >0 \;\Rightarrow\; \mbox{\rm NSPACE}(n^r) \subset \mbox{\rm NSPACE}(n^{r+\epsilon})$ propiamente.

Demostración: Dados $r,\epsilon$ sean p,q enteros positivos tales que $r\leq \frac{p}{q} < \frac{p+1}{q} \leq r+\epsilon$, veamos que la inclusión $\mbox{\rm NSPACE}(n^{\frac{p}{q}}) \subset \mbox{\rm NSPACE}(n^{\frac{p+1}{q}})$ se cumple propiamente. Si acaso $\mbox{\rm NSPACE}(n^{\frac{p+1}{q}}) \subset \mbox{\rm NSPACE}(n^{\frac{p}{q}})$ al componer con la función f_i(n)=n^(p+i)q obtendríamos $\mbox{\rm NSPACE}(n^{(p+1)(p+i)}) \subset \mbox{\rm NSPACE}(n^{p(p+i)}).$ Como $p(p+i)\leq (p+1)(p+i-1)$ tendríamos $\mbox{\rm NSPACE}(n^{(p+1)(p+i)}) \subset \mbox{\rm NSPACE}(n^{(p+1)(p+i-1)}).$ Reiterando, para $i=p,p-1,\ldots,1$ obtendríamos $\mbox{\rm NSPACE}(n^{(p+1)(2p)}) \subset \mbox{\rm NSPACE}(n^{(p+1)p}).$ Por la misma razón $\mbox{\rm NSPACE}(n^{(p+1)p}) \subset \mbox{\rm NSPACE}(n^{p\cdot p}).$ Por tanto $\mbox{\rm NSPACE}(n^{(p+1)(2p)}) \subset \mbox{\rm NSPACE}(n^{p^2}).$ De acuerdo con la Prop. 6.6.4 anterior tendríamos $\mbox{\rm NSPACE}(n^{p^2}) \subset \mbox{\rm DSPACE}((n^{p^2})^2).$ Ahora bien, como ${\displaystyle\liminf_{n\rightarrow +\infty}\frac{n^{2p^2}}{n^{2(p^2+p)}}=0}$ se tendría $\mbox{\rm DSPACE}((n^{p^2})^2)\subset \mbox{\rm DSPACE}(n^{2(p^2+p)})$ propiamente. Encadenando las inclusiones anteriores concluiríamos

$$\mbox{\rm NSPACE}(n^{(p+1)(2p)}) \subset \mbox{\rm DSPACE}(n^{2(p^2+p)}) \subset \mbox{\rm NSPACE}(n^{(p+1)(2p)})$$

donde la primera inclusión es propia. Esta contradicción prueba el teorema. q.e.d. También como en el caso determinista, de manera similar al teorema 6.5.1, se tiene el siguiente teorema de separación:

Teorema 7.2   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 NTIME}(t_1)\subset \mbox{\rm NTIME}(t_2)$ y la inclusión es propia.