Fødsel | 21. februar 1943 |
---|---|
Død | 1 st februar 2021 (ved 77) |
Nationalitet | amerikansk |
Uddannelse | University of California i Berkeley |
Aktiviteter | Matematiker , datalog , ingeniør , universitetsprofessor |
Arbejdede for | University of California San Diego |
---|---|
Mark | Computer videnskab |
Tilsynsførende | Stephen laver mad |
Walter John Savitch , født den21. februar 1943 og døde den 1 st februar 2021, er professor og forsker inden for datalogi og teoretisk datalogi . Han er bedst kendt for Savitch's sætning ( Savitch 1970 ) i kompleksitetsteori, der specificerer forholdet mellem klasser i rummet ved hjælp af deterministiske Turing-maskiner og dem, der bruger ikke-determinisme . Især giver denne sætning ligestillingen PSPACE = NPSPACE .
Savitch fik sin doktorgrad i matematik fra Berkeley University i 1969 under vejledning af Stephen Cook . Han er professor emeritus ved UCSD .
(en) Walter John Savitch , " Forholdet mellem ikke-deterministisk og deterministisk båndkompleksitet " , Journal of Computer and System Sciences , bind. 4, n o 21970, s. 177-192