Walter Savitch

Walter John Savitch (21 de febrero de 1943 – 1 de febrero de 2021) ^[2] fue más conocido por definir la clase de complejidad NL (espacio logarítmico no determinista) y por el teorema de Savitch , que define una relación entre las clases de complejidad NSPACE y DSPACE . Su trabajo en el establecimiento de clases de complejidad ha ayudado a crear el contexto en el que se puede realizar el razonamiento no determinista y probabilístico.

También realizó una amplia labor en el campo del procesamiento del lenguaje natural y la lingüística matemática . Durante más de 10 años se centró en la complejidad computacional aplicada a la genética y la biología .

Además de su trabajo en informática teórica , Savitch escribió varios libros de texto para aprender a programar en C/C++ , Java , Ada , Pascal y otros.

Savitch se doctoró en matemáticas en la Universidad de California, Berkeley, en 1969, bajo la supervisión de Stephen Cook . Desde entonces, fue profesor en el departamento de informática de la Universidad de California, San Diego .

• Richard J. Lipton , Teorema de Savitch . Ofrece un relato histórico sobre cómo se descubrió el Teorema de Savitch.