分析
OpenAIとAnthropicはAIが指数時間仮説を反証したと主張、ただし証明は未認証で、高速化が現れるのは天文学的に大きな入力からにすぎない
OpenAIとAnthropicはAIが指数時間仮説を反証したと主張。Impagliazzo氏は衝撃と述べたが審査は途中で、高速化は巨大な入力でのみ現れる。
指数時間仮説(ETH)を1990年代に共同提唱したRussell Impagliazzo氏は、AIが生んだその反証を非常に衝撃的な知らせだと述べたと、AI Weeklyが11月7日に報道を引用して伝えた。ただし慎重な読みが要る。10月26日に発表されたOpenAIとAnthropicの2本の論文は3-SATのより速いアルゴリズムを主張しているが、審査者は自分たちの関与は認証ではないと述べ、結果はP対NPを解かず、高速化が総当たりを上回るのは記憶できる規模をはるかに超える入力だけだ。開示:AnthropicはClaudeを開発しており、Claudeはこのサイトの記事執筆を手伝っている。同社は2本のうち1本を公開した。
要点
- 主張:OpenAIの67ページの論文とAnthropicの49ページの論文は、3-SATを2^o(n)時間で解くアルゴリズムを示し、ETHに反するという。AI Weeklyによれば、両社ともAIの寄与が大きく、証明はLeanで検証したと述べている。
- ETHの内容:3-SATは準指数時間では解けないという仮説。PがNPと異なるという予想より強く、多くのアルゴリズムがほぼ最適だと示すのに使われるとWikipediaは説明する。
- これまでの検証:Impagliazzo氏、Ryan Williams氏、Ramamohan Paturi氏のグループが内容を調べた。共同声明は関与を認証と受け取るべきではないとし、Williams氏は共同体が検討すべき異質に見える部分が2、3あると述べた。
- 実用上の射程:外部の推計では、総当たりを上回る分岐点はOpenAIの境界で約10^2,389変数、Anthropicの5節の場合で約10^10,000変数。現在のSATソルバーや暗号は影響を受けない。
示されたことと示されていないこと
準指数時間は多項式時間ではないため、両社はP対NPが解けたわけではないと述べ、OpenAIは高速化がNP問題一般には及ばないと言う。Leanでの検証は形式的な命題の論理を確かめるが、審査者は生データの公開と研究者向けの会議を求め、OpenAIは応じたとAI Weeklyは伝える。報じられた日付は、AIが自然言語の議論を見つけたのが10月16日、翌日に形式化、論文公開が10月26日。
チップと暗号:確かなこと
ETHは最悪の場合に関する仮説なので、直接の影響は理論と、それに基づく下界に及ぶ。チップ検証の高速化や暗号の弱体化は長期的な推測にとどまる。BeInCryptoとLet's Data Scienceは現行の暗号と産業用ソルバーは影響を受けないと述べ、AI Weeklyはある報道を誤解を招くと評した計算機科学者の発言も伝える。HackerNoonは著者が紙の上で楕円曲線にも手法を当てはめたと言うが、検証された形跡は見ていない。
確立されていない点
- 審査グループによる証明の認証:AI Weeklyによれば未了。
- 実際のSATインスタンスで使える高速化:示されていない。閾値は天文学的。
- 暗号やチップ設計ツールへの実用的な攻撃:確立されていない。
- ウォール・ストリート・ジャーナルとニューヨーク・タイムズのチップや暗号に関する記述が推測を超えるか:直接は読んでいない。
比較表
| 項目 | 2026年11月7日時点で示されている内容 | 出典 |
|---|---|---|
| 発表 | 2026年10月26日に2本の論文(OpenAI 67ページ、Anthropic 49ページ) | AI Weekly |
| 主張された結果 | 3-SATを2^o(n)時間で、Leanで検証 | AI Weekly |
| 分岐点の規模 | 約10^2,389変数(OpenAI)、10^10,000(Anthropicの5節の場合) | AI Weekly |
| 審査者 | Impagliazzo、Williams、Paturi。共同声明は認証ではないとする | AI Weekly |
| P対NP | 両社とも未解決とする | Let's Data Science |
よくある質問
AIはPとNPが等しいと証明したのか
いいえ。主張されたアルゴリズムは準指数時間で多項式ではなく、両社ともP対NPは未解決だと述べている。
暗号は弱くなったのか
実際にはなっていない。確認した媒体は現行の暗号は影響を受けないと述べ、高速化は途方もなく大きな入力でしか現れない。
証明は確認されたのか
まだ認証されていない。証明はLeanで検証されたが、審査者は関与を認証とは見なさないと言い、検討が続いている。
方法と限界
出典は2026年11月8日に確認した。2本の論文、Leanファイル、元の新聞記事は読んでおらず、AI Weekly、Let's Data Science、HackerNoon、BeInCrypto、Wikipediaに依拠した。開示:AnthropicはClaudeを開発しており、Claudeはこのサイトの記事執筆を手伝っている。投資や安全上の助言ではない。
出典
- AI Weekly:OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo(確認日:2026-11-08)
- Let's Data Science:OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16.(確認日:2026-11-08)
- HackerNoon:OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis(確認日:2026-11-08)
- BeInCrypto:OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe?(確認日:2026-11-08)
- Wikipedia:Exponential time hypothesis(確認日:2026-11-08)