Teorema de Savitch

Teorema de Savitch

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

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


Walter Savitch (1970)

Como corolario, se tiene que PSPACE = NPSPACE.

Enlaces externos

Una prueba del Teorema de Savitch


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Teorema de Savitch — En teoría de la complejidad computacional, el Teorema de Savitch, demostrado por Walter Savitch in 1970, establece que: NSPACE(f(n)) ⊆ DSPACE(f²(n)). Como corolario, se tiene que PSPACE = NPSPACE …   Enciclopedia Universal

  • ESPACIONP — Saltar a navegación, búsqueda En teoría de la complejidad computacional, la clase de complejidad ESPACIONP (NPSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en… …   Wikipedia Español

  • ESPACIOP — Saltar a navegación, búsqueda En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial (S(n) …   Wikipedia Español

  • Jerarquía de clases de complejidad acotadas por espacio — En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en relación con la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser …   Wikipedia Español

  • PSPACE-completo — En teoría de la complejidad computacional, la clase de complejidad PSPACE completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los… …   Wikipedia Español

  • NPSPACE — En teoría de la complejidad computacional, la clase de complejidad NPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio polinómico y tiempo ilimitado. Por el teorema de… …   Wikipedia Español

  • PSPACE — En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial ( ) y tiempo ilimitado. La definición no depende del… …   Wikipedia Español

  • ESPACIOP — En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial y tiempo ilimitado. La definición no …   Enciclopedia Universal

  • ESPACIONP — En teoría de la complejidad computacional, la clase de complejidad ESPACIONP (NPSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio polinómico y tiempo… …   Enciclopedia Universal

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”