Teorema de Savitch

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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

NSPACE(f(n)) \subseteq DSPACE(f²(n))


Como corolario, se tiene que PSPACE = NPSPACE.

Enlaces externos[editar]

Una prueba del Teorema de Savitch