ウォルター・サヴィッチ

ウォルター・ジョン・サヴィッチ（1943年2月21日 - 2021年2月1日）^[2]は、複雑性クラスNL（非決定性対数空間）の定義と、NSPACE複雑性クラスとDSPACE複雑性クラス間の関係を定義するサヴィッチの定理で最もよく知られています。複雑性クラスの確立における彼の仕事は、非決定性および確率的推論を実行するための背景を作り出すのに役立ちました。

彼はまた、自然言語処理と数理言語学の分野でも幅広い研究を行っており、遺伝学と生物学に適用される計算複雑性に10 年以上 にわたって注力してきました。

理論計算機科学の研究の他に、サヴィッチはC/C++、Java、Ada、Pascalなど のプログラミングを学習するための教科書を多数執筆しました。

サヴィッチは1969年にカリフォルニア大学バークレー校でスティーブン・クックの指導の下、数学の博士号を取得しました。その後、カリフォルニア大学サンディエゴ校のコンピューターサイエンス学部の教授を務めました。

• Richard J. Lipton著「サビッチの定理」。サビッチの定理がどのように発見されたかについての歴史的説明が述べられています。