公開:2026年11月1日, 最終更新:2026年11月1日
指数時間仮説(ETH: Exponential Time Hypothesis)は、理論計算機科学における計算複雑性理論の分野で提唱された困難性仮説である。代表的なNP完全問題「3-SAT」を解くには、最悪ケースで変数数 $n$ に対して指数時間($2^{\Omega(n)}$)が必ずかかり、準指数時間($2^{o(n)}$)で解くアルゴリズムは存在しないと主張する。
概要
ETHは、カリフォルニア大学サンディエゴ校のRussell ImpagliazzoとRamamohan Paturiが1999年の論文で提唱し、2001年の詳細化論文(Francis Zaneとの共著)でさらに整理された仮説である。3-SAT(各節が高々3変数の論理和で構成された論理積標準形の充足可能性問題)の最悪計算時間に関する下限を主張するものであり、「$P \neq NP$」よりも強い主張を含む。ETHが正しければ自動的に「$P \neq NP$」が真となるが、ETHが偽であっても直ちに「$P = NP$」を意味するわけではない点に注意が必要である。
なお、略称「ETH」は暗号資産イーサリアムのティッカーシンボルと同一だが、学術的・技術的な関係は一切ない。
仕組み・ポイント
- 主張の核心:$k$-SATを $O(2^{\delta n})$ 時間で解くアルゴリズムが存在するような $\delta$ の下限を $s_k$ とした場合、$k=3$ 以上では $s_k > 0$ である(すなわち、ゼロにならない定数コストの指数時間が必須である)と主張する。2-SATは多項式時間で解けるため $s_2 = 0$ だが、3-SAT以上ではこの主張が本質的に変わる。
- 条件付き証明の基盤:パラメータ化計算量(Parameterized Complexity)や精密計算量(Fine-Grained Complexity)の分野で、アルゴリズムの計算量下限を示す前提条件として広く用いられており、グラフ理論・計算生物学・データベース・計算幾何学など幅広い領域で800件以上の論文がETHを根拠として記述されている。
- 強指数時間仮説(SETH)との関係:ETHの強化版として「強指数時間仮説(SETH)」が存在し、$k$ が無限大に近づくにつれて $k$-SATの必要計算時間が $2^n$ に限りなく近づくことを主張する。ETHとSETHはともに、現代のアルゴリズム研究における下限証明の重要な理論的足場となっている。
なぜ今注目されているのか
2026年10月26日、OpenAIおよびAnthropicは内部のAIモデルを活用して「ETHは偽である」とする論文『The Exponential Time Hypothesis is False』を発表し、$k$-CNF論理式の解を準指数時間($2^{O(n \log \log n / \sqrt{\log n})}$)で数える決定的アルゴリズムを発見したと主張した。定理証明支援系「Lean」による形式化コードもGitHubで公開されており、単なる主張にとどまらない形式的裏付けが示されている。ただし、発見されたアルゴリズムの計算時間は従来の純粋な指数時間を下回るものの、その差は限定的であり、直ちに実用的な超高速化をもたらすものではないとされる。主張の正否を巡っては、ETHの提唱者であるImpagliazzoおよびPaturi、さらにMITのRyan Williamsら計算量理論の専門家グループによる人間の検証が進行中であり、理論計算機科学コミュニティ全体が注視する状況にある。
日本企業への示唆
ETH自体は純粋な理論的仮説であり、日本企業が直接ビジネス実装に用いるものではない。しかし、ETHが条件付き証明の基盤として機能してきたグラフ最適化・データベースクエリ・組み合わせ最適化などの分野は、ロジスティクスや製造業での意思決定最適化に広く応用されており、仮説の真偽に関する学術的決着は中長期的にアルゴリズム設計の限界認識を変え得る。また、今回の発表がAIモデルによる数学的定理発見という形で行われた点は、AIを研究・開発の補助ツールとして活用する流れを象徴しており、R&D部門でのAI活用戦略を検討している企業にとって注目すべき事例といえる。専門家による検証が完了するまでは主張の扱いに慎重さが求められる段階であることも、意思決定の参考として認識しておきたい。
※ 本ページはAI News JAPAN編集部が最新の動向を踏まえて解説したものです。内容は随時見直します。


