指数時間仮説

Exponential Time Hypothesis

3-SATなどのk-SAT問題は準指数時間では解けないとする計算複雑性理論の予想。

記事1本最終言及

指数時間仮説(Exponential Time Hypothesis、ETH)は、変数n個の3-SATを準指数時間、すなわち2^{o(n)}時間で解くアルゴリズムは存在しないとする計算複雑性理論の予想である。1990年代末にラッセル・インパリアッツォとラマモハン・パトゥリがk-SATの複雑性に関する研究で提案し、フランシス・ゼインを加えた後続研究のスパース化補題によって多くの問題に適用できるようになった。

ETHはP≠NPより強い仮定である。P≠NPはNP完全問題に多項式時間アルゴリズムがないことを主張するのに対し、ETHは指数時間より意味のある程度に速いアルゴリズムすら存在しないとする。この仮定を前提に、グラフ問題、パラメータ化計算量、細粒度計算量などの分野で条件付き下界が導かれてきた。3-SATを2^{(1-ε)n}時間で解けないとするより強い予想は強指数時間仮説(SETH)と呼ばれる。

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

この項目を扱った記事

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

    OpenAIは2026年10月26日、同社のAIモデルの一つが、計算機科学者が約30年にわたって基盤的な前提として扱ってきた予想「指数時間仮説(ETH)」は偽であるという証明を生み出したと発表しました。

    記事を読む

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

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