Savitch's theorem
Jump to navigation
Jump to search
English[edit]
Etymology[edit]
Proved by Walter Savitch in 1970.
Proper noun[edit]
- (computing theory) A theorem giving a relationship between deterministic and non-deterministic space complexity.