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.