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
Other Languages