x
1

Teorema de Savitch



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.

Una prueba del Teorema de Savitch



Escribe un comentario o lo que quieras sobre Teorema de Savitch (directo, no tienes que registrarte)


Comentarios
(de más nuevos a más antiguos)


Aún no hay comentarios, ¡deja el primero!