Escribir una publicación
En teoría de la complejidad computacional, el teorema de Savitch establece que:
NSPACE(f(n)) ⊆ {\displaystyle \subseteq } DSPACE(f²(n)) Walter Savitch (1970)
NSPACE(f(n)) ⊆ {\displaystyle \subseteq } DSPACE(f²(n))
Como corolario, se tiene que PSPACE = NPSPACE.
Una prueba del Teorema de Savitch