Walter John Savitch
|Born||February 21, 1943|
|Died||February 1, 2021(aged 77)|
|Alma mater||University of California, Berkeley|
|Known for||Savitch's theorem, NL|
|Institutions||University of California, San Diego|
|Thesis||Nondeterministic Tape Bounded Turing Machines (1969)|
|Doctoral advisor||Stephen Cook|
Walter John Savitch (February 21, 1943 – February 1, 2021) is best known for defining the complexity class NL (nondeterministic logarithmic space), and for Savitch's theorem, which defines a relationship between the NSPACE and DSPACE complexity classes. His work in establishing complexity classes has helped to create the background against which non-deterministic and probabilistic reasoning can be performed.
He has also done extensive work in the field of natural language processing and mathematical linguistics. He has been focused on computational complexity as it applies to genetics and biology for over 10 years.
Savitch received his PhD in mathematics from University of California, Berkeley in 1969 under the supervision of Stephen Cook. Since then he has been a professor at University of California, San Diego where he is currently a professor emeritus in the computer science department.
- Walter Savitch at the Mathematics Genealogy Project
- "In Memoriam: Walter Savitch, Professor Emeritus in Computer Science and Engineering". February 23, 2021. Retrieved March 1, 2021.
- Richard J. Lipton, Savitch’s Theorem. Gives a historical account on how Savitch's Theorem was discovered.
|P ≟ NP||This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.|