OpenAIは2026年10月26日、同社のAIモデルの一つが、計算機科学者が約30年にわたって基盤的な前提として扱ってきた予想「指数時間仮説(ETH)」は偽であるという証明を生み出したと発表しました。証明は、各論理ステップを機械で検証する対話型定理証明器Leanでチェックされ、OpenAIは論文を、この仮説を最初に定式化した計算複雑性理論の研究者たちに渡して、査読と取りまとめを委ねました。この結果はP=NPを示すものではなく、OpenAI社長のグレッグ・ブロックマン氏も同日にその旨を述べています。示されたのは、長らく総当たり探索が必要と考えられてきた問題のクラスに準指数時間の近道が存在するということであり、これは膨大な理論研究の足元を揺るがすものです。
指数時間仮説が主張していたこと
ETHはブール充足可能性問題、略してSATに関するものです。真か偽のいずれかの値を取る変数から組み立てた論理式が与えられたとき、式全体を真にする割り当てが存在するかどうかを問う問題です。約30年前にラッセル・インパリアッツォ氏、ラマモハン・パトゥリ氏、フランシス・ゼイン氏が提唱したこの仮説は、この問題のk-CNF版を解くには、変数の数に対して厳密に指数的に増大する時間が必要だと主張していました。平たく言えば、うまくいくまで構成を試し続ける以外に、意味のあるより良い戦略は存在しないということです。
この前提は研究の主力道具となりました。グラフ理論、計算生物学、データベース理論、計算幾何学の数百本の論文が、ETHを前提として「ETHが成り立つなら、この別の問題も高速には解けない」という形の条件付き困難性の結果を導いてきました。前提が外れても、下流のそれぞれの主張が誤りになるわけではありませんが、著者たちが想定していた土台の上にはもはや立っていないことになります。たとえるなら、理論的な建造物の一区画全体が一つの土地の上に建てられていたところ、その土地が誰もが信じていた形では存在しなかったと判明したようなものです。
新しい論文が示したこと
OpenAIの論文「The Exponential Time Hypothesis is False」には、2026年10月17日の初版日付と2026年10月25日の改訂日付が記されています。添付の発表によれば、モデルは10月16日に反証を見つけ、Leanによる形式化は10月17日に完了しました。中心となる定理は、k-CNF充足可能性を2のo(n)乗、すなわち準指数的な増大を表す形式的記法の時間で解く決定性アルゴリズムを提示しています。論文は、機械検証済みのLean証明と自然言語による説明を併記しています。
区別しておくべき2つの枠組みがあります。
| 主張 | 発表後の状態 |
|---|---|
| ETHは真である | OpenAIのLean検証済み証明により反証 |
| SATは準指数時間で解ける | 論文のアルゴリズムにより確立 |
| P=NP | 未証明。ブロックマン氏はおそらく依然として等しくないと発言 |
| 現代の暗号は破られた | 未証明。未解決のP対NP問題に依存 |
Anthropicもほぼ同時期に非常によく似た結果に到達したようで、これが確認されれば、2つの独立したAIシステムの注目すべき収束となります。

▲ 指数的な探索と高速な検証の対比
「準指数」が「高速」と同じではない理由
P、NP、指数時間の違いは、身近な物を使って理解できます。
10桁のダイヤルが1つのダイヤル錠は、総当たりで開けるのに最大10回の試行で済みます。ダイヤルが2つなら100回、3つなら1,000回、10個なら100億回に増えます。ダイヤルを1つ加えるごとに探索空間が掛け算で増える。これが指数的増大で、サイズのわずかな増加が作業量の爆発的な増加を生みます。
数独は、もう半分の側面を示します。空の9×9のマス目を手で埋めるのは時間がかかりますが、完成したマス目の確認は数秒で済みます。各行、各列、各3×3ブロックに1から9の数字が含まれていることを確かめるだけでよいからです。提案された答えを素早く検証できる問題はNPというクラスに属し、NPは非決定性多項式時間を意味します。
クラスPの多項式時間は、問題が大きくなるにつれて予測可能で扱いやすい形で難しくなる問題を扱います。洗濯物のかご1つを仕分けるのに10分かかるとすれば、かご5つなら比例して長くかかるだけで、何十億年もかかることはありません。
P対NP問題は、検証が簡単な問題はすべて解くのも簡単なのかを問います。50年以上にわたり、研究者はNP完全問題の多項式時間アルゴリズムを見つけるか、存在しないことを証明しようとしてきました。どちらも実現せず、コンセンサスはPはNPに等しくないという想定へ傾いていきました。
ETHはP≠NPよりも鋭い主張でした。SATに多項式時間アルゴリズムがないだけでなく、完全な指数時間が必要だと述べていたのです。新しいアルゴリズムはこの鋭い主張を打ち破りました。すべてのダイヤルを闇雲に回すのではなく、タンブラーの音を聞くピッキングの名人のように振る舞います。あるダイヤルが9にあると確定すれば、他の場所の数千通りの組み合わせを論理的に除外できるため、探索の枝全体が一度も訪れられません。実行時間は、これまで示されている限りでは依然としてどんな多項式よりも速く増大しますが、純粋な指数よりは遅くなります。
山のたとえを使うと階層がはっきりします。山を越えて地点Aから地点Bへ行くのに山頂を登って越えるのが全数探索で、P≠NPの世界です。地上の高さを走る平坦なトンネルがP=NPに当たります。ETHの反証は地上レベルのトンネルを開くものではありませんが、中間の高さで山を貫くトンネル、数十年の人間の努力でも見つけられなかった通路を明らかにしています。
暗号にとってこの結果が重要な理由と、暗号を破るわけではない理由
現代の暗号はほぼすべて、秘密鍵の復元が手に負えないNP探索問題であるという仮定に依存しています。これはスコット・アーロンソン氏のサーベイ論文「P =? NP」で指摘されている点です。パスワードや暗号鍵は、推測には数千年かかり、検証はミリ秒で済むように設計されています。この非対称性こそが要点であり、その起源はこの分野の最も初期の思考にまで遡ります。1955年にジョン・ナッシュ氏が国家安全保障局に宛てた書簡は、暗号を破るには鍵長に対して指数的に増大する空間を探索する必要があると論じ、1956年にクルト・ゲーデル氏がジョン・フォン・ノイマン氏に宛てた書簡は、同じ問いのメタ数学的な核心を定式化していました。
もしPがNPに等しいことが実用的なアルゴリズムとともに示されれば、インターネットのセキュリティ、電子バンキング、暗号資産システムは根本から危うくなり、デジタルインフラの全面的な見直しが必要になります。同じ近道は巨大な最適化問題も扱いやすくするでしょう。シフトのスケジューリング、サプライチェーンの経路計画、半導体チップのレイアウト、タンパク質構造のモデリング、創薬のすべてが劇的に加速します。OpenAIのある研究者は、物理学、数学、計算機科学の基礎的な突破口はAIの進歩そのものの追い風になるとも指摘しています。

▲ P対NPで問われる暗号と最適化
これらのいずれも、ETHの反証だけから導かれるわけではありません。「PはおそらくまだNPに等しくない」というブロックマン氏の投稿は35万回以上閲覧され、他のコメントでも、この結果は多項式時間への崩壊ではなく準指数アルゴリズムを指し示すものだと強調されました。もう一つの注意点があります。多項式時間アルゴリズムであっても、定数係数が天文学的であれば実用上は役に立たないことです。問題が数千年分の手作業の試行を超える規模になって初めて総当たりを上回るアルゴリズムは、誰の役にも立ちません。X上のあるコメント投稿者はこの考えをさらに進め、もしP=NPだが現実世界の住人には手の届かない定数でしか成り立たないなら、最も合理的な結論は、現実が意図的な速度制限を備えた設計されたシミュレーションだということになる、と論じました。これは発見ではなく思考実験ですが、理論上の効率と実用上の効率の差がここでなぜ重要なのかを言い当てています。
OpenAIによる公開の進め方
OpenAIは正式な著者としてのクレジットを取っていません。代わりに、UCサンディエゴのインパリアッツォ氏とパトゥリ氏、そしてETHのより強いバージョンの反証を以前に証明したMITのライアン・ウィリアムズ氏に、論文の査読と取りまとめを依頼しました。この進め方は、欠陥を見つけるのに最も適した立場の人々による精査を結果に与え、以前のAI関連の発表に続いたような反発を避けるために設計されたものと見られます。
ETH論文は、同じ発表に含まれる3つの結果の一つです。OpenAIは、タデウシュ・バワバン氏の構成的場の量子論のアプローチに基づき、2026年10月16日にLeanで形式化された純粋ヤン・ミルズ理論の厳密な存在証明も公開しました。これはクレイ数学研究所のヤン・ミルズ理論と質量ギャップ問題の主要な構成要素に取り組むものですが、公式に述べられたミレニアム懸賞問題の完全な解決ではありません。3つ目の結果は、1991年にクリストファー・ソッグ氏が提起した調和解析の問題である局所平滑化と掛谷予想に関するものです。約30日前、OpenAIはナビエ・ストークス方程式の存在と滑らかさに関する解析的証明とLean形式化を公開しており、こちらはまだ学術的な査読中です。全体として、AIシステムはおよそ90日の間に複数の主要な予想の証明を生み出したことになります。
スコット・アーロンソン氏は発表の約18時間前にポッドキャストで、AIが自分たちの分野には及ばないとかつて考えていた理論物理学者たちが、今ではその進歩を不安げに見守っていると述べ、数学者は誰が自分たちの問題に取り組んでよいかを決める裁定者ではないとも論じています。
覚えておきたい歴史的パターン
この結果は、ノースイースタン大学の計算機科学教授エマヌエーレ・ヴィオラ氏が2018年のエッセイ「I Believe P=NP」で示したパターンに当てはまります。1950年代、アンドレイ・コルモゴロフ氏は2つのnビット整数の乗算には2乗の時間が必要だと予想しましたが、23歳の教え子アナトリー・カラツバ氏は1週間以内により高速なアルゴリズムを見つけました。1968年にはフォルカー・シュトラッセン氏が、標準的な行列乗算が最適だという前提を覆しました。ヴィオラ氏の主張は、研究者は繰り返し計算上の障壁を宣言し、後に巧妙なアルゴリズムがそれを乗り越えてきたのであり、人類は効率的な計算の射程を過小評価してきたというものです。ETHの反証はそのリストに加わる新たな一例と見られますが、それが本物の実用的な近道なのか、理論上の境界をわずかに押し広げただけなのかは、まだはっきりしていません。
この記事から押さえておくこと
- 約30年にわたって前提とされてきた指数時間仮説は、Leanで機械検証されたAI生成の証明によって反証され、仮説の原著者たちが取りまとめを進めています。
- 証明はk-CNF充足可能性に対する決定性の準指数アルゴリズムを与えます。P=NPを示すものではなく、グレッグ・ブロックマン氏はPはおそらく依然としてNPに等しくないと述べています。
- 暗号、銀行、暗号資産のセキュリティがこの結果によって破られたことは示されていません。
- 理論上の限界を実際のソフトウェアの高速化に変換するには相当な追加研究が必要で、定数係数が実用を制限する可能性があります。
この分野を追う読者には、いくつかの実践的なステップがあります。条件付き困難性の仮定としてETHに依存する結果を持つ研究者は、その結果を再検討すべきです。今後のAI生成数学を評価する人は、主張を確定したものとして扱う前にLeanのような証明支援系での形式検証を確認し、主張されたアルゴリズムが実行可能な定数と指数を持つかどうかを、展開可能だと決めつけずに確かめるべきです。そして日常のセキュリティについては、錠前のたとえが今も当てはまります。文字を1つ加えるごとに攻撃者の探索空間が掛け算で増えるため、パスワードの長さは依然として最も簡単な防御策です。


