Teorema de Savitch

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

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


Walter Savitch (1970)

Como corolario, se tiene que PSPACE = NPSPACE.

Enlaces externos

Una prueba del Teorema de Savitch

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.