Walter Savitch

Walter John Savitch (1943-2021) was a computer scientist and mathematician best known for defining the complexity class NL, nondeterministic logarithmic space, and for Savitch's theorem, which relates the NSPACE and DSPACE complexity classes by showing that nondeterminism costs at most a squaring of space. His work establishing complexity classes helped create the background against which non-deterministic and probabilistic reasoning can be performed. He also did extensive work on natural language processing and mathematical linguistics, and for over ten years studied computational complexity as it applies to genetics and biology. He wrote a number of textbooks for learning to program in C and C++, Java, Ada and Pascal. He received his PhD in mathematics from the University of California, Berkeley in 1969 under Stephen Cook and was afterwards a professor of computer science at the University of California, San Diego.