分析

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本を公開した。

要点

示されたことと示されていないこと

準指数時間は多項式時間ではないため、両社はP対NPが解けたわけではないと述べ、OpenAIは高速化がNP問題一般には及ばないと言う。Leanでの検証は形式的な命題の論理を確かめるが、審査者は生データの公開と研究者向けの会議を求め、OpenAIは応じたとAI Weeklyは伝える。報じられた日付は、AIが自然言語の議論を見つけたのが10月16日、翌日に形式化、論文公開が10月26日。

チップと暗号:確かなこと

ETHは最悪の場合に関する仮説なので、直接の影響は理論と、それに基づく下界に及ぶ。チップ検証の高速化や暗号の弱体化は長期的な推測にとどまる。BeInCryptoとLet's Data Scienceは現行の暗号と産業用ソルバーは影響を受けないと述べ、AI Weeklyはある報道を誤解を招くと評した計算機科学者の発言も伝える。HackerNoonは著者が紙の上で楕円曲線にも手法を当てはめたと言うが、検証された形跡は見ていない。

確立されていない点

比較表

比較表
項目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はこのサイトの記事執筆を手伝っている。投資や安全上の助言ではない。

出典

この記事の誤りに気づかれましたか? 報告する · 訂正ポリシー

OrigoTechのロゴ

新登場:アプリ iPhone・iPad

OrigoTechがiPhone・iPadアプリになりました

記事をネイティブで読めます。未読の「新着」表示、端末内検索、読み込み済み記事のオフライン閲覧に対応。無料、アカウント不要、iOS 17以降。記事の合間に広告が表示されます。

Rekhaのアイコン:一筆書きで描かれた家

同じ筆者による作品 自社紹介

一筆書きの道を、指でたどる

OrigoTechの筆者が作ったiPhoneゲーム「Rekha」:同じ線を二度たどらずに、すべての点を一筆でつなぐ。500種類の図形は、どれも必ず解けます。

OrigoTechニュースレター

AIツールのニュースを、出典付きで毎週まとめて配信。

次に読む