ラッセル・インパリアッツォ

Russell Impagliazzo

指数時間仮説の提案や「五つの世界」の分類で知られる、カリフォルニア大学サンディエゴ校の米国の計算機科学者。

記事1本最終言及

ラッセル・インパリアッツォは米国の理論計算機科学者で、カリフォルニア大学サンディエゴ校の計算機科学教授である。カリフォルニア大学バークレー校でマニュエル・ブラムの指導のもと博士号を取得し、計算複雑性理論、暗号理論、擬似乱数性を研究している。

ラマモハン・パトゥリとともにk-SATの複雑性を研究し、指数時間仮説(ETH)を提案した。1995年には、P対NP問題と暗号の関係に応じてあり得る世界をAlgorithmica、Heuristica、Pessiland、Minicrypt、Cryptomaniaの五つに分類した「五つの世界」の議論で広く知られるようになった。擬似乱数生成器と脱乱択化に関するインパリアッツォ=ウィグダーソンの定理にもその名が付いている。

この説明は、AIPOSTの記事と広く知られた事実をもとにまとめたものです。誤りがあれば訂正依頼でお知らせください。

この項目を扱った記事

  • OpenAIのAIが指数時間仮説を反証、P=NPではないが理論の土台が揺らぐAIニュース ·

    約30年前にラッセル・インパリアッツォ氏、ラマモハン・パトゥリ氏、フランシス・ゼイン氏が提唱したこの仮説は、この問題のk-CNF版を解くには、変数の数に対して厳密に指数的に増大する時間が必要だと主張していました。

    記事を読む

説明の誤りや、見つからない項目はありますか?

事典の説明は、AIPOSTの記事と広く知られた事実をもとにまとめています。誤りは訂正依頼でお知らせいただければ、確認して修正します。新しい記事に登場した名前は、記事の公開後に事典に加わります。