Teorema de Savitch

En teoría de la complejidad computacional, el teorema de Savitch establece que: NSPACE(f(n))

{\displaystyle \subseteq }

DSPACE(f²(n)) Como corolario, se tiene que PSPACE = NPSPACE.

Una prueba del Teorema de Savitch