Walter Savitch

From Wikipedia, the free encyclopedia

Walter Savitch is best known for creating the NL (nondeterministic logarithmic) class of complexity problems, and for Savitch's theorem which defines a relationship between the NSPACE and DSPACE complexity classes. NL was the first formally defined complete language and has subsequently lead to a large body of research in computational complexity theory. His work in establishing complexity classes has helped to create the background against which non-deterministic and probabilistic reasoning can be performed.

Aside from his work in theoretical computer science, Savitch has written a number of textbooks for learning to program in C/C++, Java, Ada and others. He has done extensive work in the field of natural language processing and mathematical linguistics. He has been focused on computational computing as it applies to genetics and biology for over 10 years.

Savitch received his PhD in mathematics from UC Berkeley in 1969. Since then he has been a professor at UCSD where he is currently a professor emeritus in the computer science department.