OpenAIとAnthropic、AIモデルが指数時間仮説に異議を唱えると主張
重要ポイント
- •OpenAIは10月26日、自社のAIモデルが指数時間仮説に異議を唱える証明を生成し、準指数時間アルゴリズムのLean機械検証による形式化を含めると発表した。
- •その数時間後、AnthropicはClaudeが3-SATを指数時間未満で解ける決定的アルゴリズムを発見したと報告したが、同社はこの結果が純粋に漸近的かつ理論的なものだと明記している。
- •ETHが反証されれば、グラフ理論、データベース、計算生物学などの分野の数百本の論文の結論を見直す必要が生じる可能性がある。
- •OpenAIはETHの先駆者であるImpagliazzo氏とPaturi氏、MITのRyan Williams教授を含む検証チームを編成し、会議の支援と調査結果の公開に同意した。
- •仮に検証されても、この結果はP対NP問題を決着させるものでも既存の暗号を弱体化させるものでもなく、理論的発見を実用的なソフトウェアに変換するには数年を要する可能性がある。
OpenAIとAnthropicは、自社のAIモデルが計算の限界に関する長年の仮説に異議を唱える結果を導き出したと発表した。主張が裏付けられれば、計算量理論が再形成される可能性があるが、両社ともより高速な実用ソフトウェアの開発や既存の暗号の解読には成功していない。
1999年の仮説に圧力
指数時間仮説(ETH)は1999年にRussell Impagliazzo氏とRamamohan Paturi氏によって提唱された。ETHは、特定の論理問題がサイズの増加に伴い指数関数的に多くの計算時間を必要とするとしており、研究者たちは数十年にわたりこの仮定の上に研究を積み重ねてきた。実務的には、この仮説は近道を排除するものであり、これらの問題に対するあらゆるアルゴリズムは入力の増大に伴い指数関数的に遅くなるため、それより緩やかに実行時間が増加する準指数時間の手法は仮説に真っ向から矛盾する。OpenAIによれば、グラフ理論、データベース、計算生物学などの分野で計算限界を証明するためにETHを用いた研究論文は数百本に上る。ETHが誤りであれば、それらの結論の多くを見直す必要が生じる可能性がある。
二つの研究室、二つの反証の主張
10月26日、OpenAIは、自社のAIモデルがETHに異議を唱える証明を生成したと発表した。これは、調和解析や場の量子論の成果も含む幅広い公開の一環だった。結果のLean形式化はLean証明支援系で機械検証されており、準指数時間アルゴリズムの妥当性を確認している。付随する論文はより強力な理論的証明を提示している。
そのわずか数時間後、Anthropicも自社の発見を発表した。同社によれば、Claudeが3-SAT — 計算困難性研究における代表的なベンチマーク問題 — を指数時間未満で解ける決定的アルゴリズムを発見したといい、その詳細は公開リポジトリで示されている。ただし同リポジトリは、この発見が依然として理論的なものにとどまることを明記している。「この結果は純粋に漸近的であり、実際に数式を解くことについては何も述べていない」。
研究自体をめぐる疑問も浮上した。TechCrunchの報道によると、Anthropicの数学者Levent Alpöge氏は、OpenAIの研究のどれほどが既存の研究に依拠したものかを疑問視した。
専門家が検証できること、できないこと
OpenAIは、ETHの先駆者であるImpagliazzo氏とPaturi氏、そしてMITのRyan Williams教授を含む検証チームを編成し、会議を支援して調査結果を公開し、さらなる検証に供することにも同意した。
Williams氏は以前、AI生成の証明の洪水を批判し、数学者が検証すべき作業量に圧倒されていると主張していた。しかしOpenAIの今回の発見には興味をひかれたという。TechCrunchとのインタビューで、証明の一部は見覚えがあるものの、際立つ部分もあったと述べた。「異質に見える部分が2つか3つある」。
そこでこそ人間の専門知識が重要になる。Leanは形式証明が論理的に健全かどうかを確認できるが、研究者は未知の推論を理解し、それが実用的なアルゴリズムにつながるかどうかを判断する必要がある。OpenAIが支援に同意した会議と、その後に公開される調査結果が、次の検証の節目となる。「異質に見える部分」が学界を説得できるかどうかが問われる場だ。
P対NP問題でも、暗号解読でもない
ETHの反証は、P対NP問題 — 答えを素早く検証できるあらゆる問題が素早く解けるかどうかという数十年にわたる別の問い — を決着させるものではなく、既存の暗号の弱点を明らかにするものでもない。それでも、暗号資産保有者には注目する理由がある。Cryptopolitanはこれまでに、イーサリアムの研究者Justin Drake氏が、OpenAIが別に公開した722本の原稿を含むAI生成の数学が、最終的にデジタル署名を脅かす可能性があると警告したと報じている。現時点ではこれは警告であり、実証された侵害ではない。
7月には、AnthropicのClaude Mythos Previewが、60時間の研究を経て、耐量子署名候補のHAWKへの攻撃を改善した。稼働中のシステムへの影響はなかった。
終わりの見えないAI研究競争
State of AI 2026レポートは、Anthropic、OpenAI、Googleの間で拡大する競争を描いている。Anthropicの社内測定によれば、Claudeは8月に追跡対象のモデル研究開発作業の26%を担当し、2月の1%未満から上昇した。一方、英国のAI Security Instituteは、AIが完了できる特定のサイバーセキュリティ作業の所要時間が約8か月ごとに倍増していると報告している。ETHをめぐる両社の競合する発表は、AI支援による研究の成果がフロンティアの進展を測る指標としてますます注視される such な状況の中で行われた。
AIは研究者の発見を加速させているが、数学的なブレークスルーがそのまま優れたソフトウェアにつながるわけではない。たとえETHが覆されても、実用的なアルゴリズムの開発には数年を要する可能性がある。人間の研究者にはまだやるべき仕事が多く残されている。
