Teorema de Savitch

Summary

En teoría de la complejidad computacional, el teorema de Savitch establece que:

NSPACE(f(n)) DSPACE(f²(n))


Como corolario, se tiene que PSPACE = NPSPACE.

Enlaces externos

editar

Una prueba del Teorema de Savitch

  •   Datos: Q954210