Loading article…
アラン・ルイス・セルマン（1941年4月2日 - 2021年1月22日）[ 1 ]は、構造的複雑性理論の研究で知られるアメリカの数学者および理論計算機科学者であり、個々のアルゴリズムの問題ではなく、複雑性クラス間の関係の観点から計算の複雑性を研究した。[ 2 ] [ 3 ]
セルマンはニューヨーク市立大学の卒業生である。カリフォルニア大学バークレー校で修士号を取得した後、1970年にペンシルベニア州立大学で博士号を取得した。[ 4 ]彼の博士論文「有限構造で有効な算術的還元可能性と公式の集合」は、スティーブン・コール・クリーネの教え子であるポール・アックスの指導を受けた。[ 5 ]
彼はカーネギーメロン大学で博士研究員、フロリダ州立大学で数学の助教授を務めた後、アイオワ州立大学のコンピュータサイエンス学科に移り、最終的にそこで正教授となった。1980年代後半にはノースイースタン大学に移り、そこで学部長代理を務め、1990年にはバッファロー大学にコンピュータサイエンス学科長として再び移った。2014年に退職し、2021年1月22日に亡くなった。[ 4 ]
彼は毎年開催される計算複雑性会議の初代議長であり[ 4 ]、2001年から18年間、ジャーナル「Theory of Computing Systems」の編集長を務めた[ 6 ]。[ 3 ]
セルマンの研究論文には、計算能力によるさまざまなタイプの還元の分類、プロミス問題の定式化、曖昧さのないチューリングマシンで解ける問題の複雑性クラスUP 、およびそれらの暗号の計算複雑性への応用に関する引用の多い研究が含まれている。[ 2 ] [ 3 ]
セルマンは、いくつかの編著書の編集者であるだけでなく、教科書『計算可能性と複雑性理論』 （スティーブ・ホーマーとの共著、Springer、2001年、第2版、2011年）の共著者でもある。[ 7 ]
セルマンはフルブライト奨学生およびフンボルト奨学生であった。[ 4 ]彼は1998年に「計算複雑性理論への影響力のある貢献者であり、学術的なコンピュータ科学コミュニティにおける献身的な専門家」としてACMフェローに選ばれた。[ 8 ] 2002年には、ACM SIGACT （ Association for Computing Machineryのアルゴリズムと計算理論に関する特別利益団体）から功労賞を授与され、計算複雑性会議の設立に貢献したこと、および国立科学財団の政策報告書の作成を通じて理論計算機科学研究への資金提供に貢献したことが評価された。[ 9 ]
学術誌「Theory of Computing Systems」は、彼の功績を称える記念号を企画している。[ 6 ]