Teorema de Savitch
Savitch's theorem
- Fecha
- 1970 · fiabilidad alta
- Lugar
- Ithaca, Nueva York, Estados Unidos
- Autoría
- Walter Savitch
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema de la teoría de la complejidad computacional que relaciona la complejidad espacial determinista y no determinista, probado por Walter Savitch en 1970.
A qué dio paso
- Resultado clave PSPACE = NPSPACE en teoría de la complejidad
- Base para el estudio de las clases de complejidad en espacio
- Influencia en algoritmos de simulación determinista de máquinas no deterministas
- Fundamento teórico para problemas de complejidad de juegos y lógica