ラマモハン・パトゥリ

Ramamohan Paturi

k-SATアルゴリズムと指数時間仮説の研究で知られる、カリフォルニア大学サンディエゴ校の計算機科学教授。

記事1本最終言及

ラマモハン・パトゥリはカリフォルニア大学サンディエゴ校の計算機科学教授を務める理論計算機科学者である。計算複雑性理論と充足可能性問題のアルゴリズムを研究している。

ラッセル・インパリアッツォとともに指数時間仮説(ETH)を提案し、k-SATを2^nより速く解くPPZアルゴリズムおよびPPSZアルゴリズムの共同開発者でもある。

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

この項目を扱った記事

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

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

    記事を読む

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

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