Savitch's theorem
Teorema de Savitch
- Date
- 1970 · confidence high
- Place
- Ithaca, New York, United States
- Credited to
- Walter Savitch
- Field
- Knowledge & symbols
What was discovered
Computational complexity theory theorem relating deterministic and non-deterministic space complexity, proved by Walter Savitch in 1970.
What it led to
- The key PSPACE = NPSPACE result in complexity theory
- Basis for studying space complexity classes
- Influence on algorithms for deterministic simulation of non-deterministic machines
- Theoretical foundation for complexity problems in games and logic