Fødsel | 21. februar 1943 |
---|---|
Død | 1 st februar 2021 (kl. 77) |
Nasjonalitet | amerikansk |
Opplæring | University of California i Berkeley |
Aktiviteter | Matematiker , informatiker , ingeniør , universitetsprofessor |
Jobbet for | University of California San Diego |
---|---|
Felt | Informatikk |
Veileder | Stephen kokk |
Walter John Savitch , født den21. februar 1943 og døde den 1 st februar 2021, er professor og forsker innen informatikk og teoretisk informatikk . Han er mest kjent for Savitchs teorem ( Savitch 1970 ), i kompleksitetsteori som spesifiserer forholdet mellom klassene i rommet ved hjelp av deterministiske Turing-maskiner og de som bruker ikke-determinisme . Spesielt gir denne teorem likheten PSPACE = NPSPACE .
Savitch doktorgraden i matematikk fra Berkeley University i 1969, under veiledning av Stephen Cook . Han er professor emeritus ved UCSD .
(en) Walter John Savitch , " Relationships between non- deterministic and deterministic tape complexities " , Journal of Computer and System Sciences , vol. 4, n o to1970, s. 177-192