OpenAIとAnthropicは、それぞれが指数時間仮説が偽であることを示す証明を公開しました。
ETHは理論計算機科学における27年来の仮定で、一部の問題は力まかせ探索より大幅に速くは絶対に解けないとします。ところが今、トップAI研究所はそれが単に事実ではないと言っています。
もし証明が持ちこたえれば、これは計算機科学におけるAI生成の成果としてこれまでで最も重要なものになります。同時に、ETHを前提にしていた何百本もの研究論文を文字通り書き換える必要が生じます。
本記事では、指数時間仮説が実際に何を意味するのか、関連するP対NPと併せて平易に説明します。さらに、2つの研究所が具体的に何を主張しているのか、証明はどのように確認されたのか、そして暗号に関して何が（そして何が）変わらないのかを見ていきます。
平易に言うP対NP
P対NPは、「答えの正しさを簡単に確認できるすべての問題は、簡単に解くこともできるのか？」という問いです。ミレニアム懸賞問題の7つのうちの1つであり、今回のニュース後も未解決のままです。
数独は古典的な例です。埋められたグリッドのチェックは数秒で済みます。各行・列・ブロックに重複がないかを確かめるだけです。一方で、ほぼ空のグリッドから解を見つけるのははるかに時間がかかり、グリッドが大きくなるほどその差は爆発的に広がります。
- Pは、入力サイズnが増えるにつれて作業量がn2、n3のように多項式的に増える時間でコンピュータが解ける問題のクラスです。
- NPは、提案された解をコンピュータが多項式時間で検証できる問題のクラスです。
Pに属する問題はすべてNPにも属します。未解決なのはその逆が成り立つかどうかです。多くの計算機科学者はP ≠ NPと考えており、つまり、ある種の問題は本質的に解く方が確認するよりも難しいと信じています。現代暗号はこの信念に依拠しています。暗号化は容易だが、鍵なしでそれを解くのは難しいべきだ、というわけです。
指数時間仮説（ETH）とは？
ETHはさらに鋭い主張です。特定のNP問題である3-SATは、どれほど巧妙なアルゴリズムでも指数時間を要する、と言います。これは1990年代後半にUCサンディエゴのRussell ImpagliazzoとRamamohan Paturiが提案し、Francis Zaneも基礎的な仕事に貢献しました。
3-SAT問題
3-SATでは、n個の真偽変数と節のリストからなる論理式が与えられます。各節は3つの条件をORでつなぎます。例えば「x₁が真 OR x₄が偽 OR x₇が真」のように。課題は、すべての節を同時に満たすように変数の値を設定することです。
力まかせ探索は2ⁿ通りすべてを試すため、変数が1つ増えるごとに作業量は2倍になります。変数が100個程度でもはや絶望的になるのがわかるでしょう。
ETHの主張
ETHは、ある定数c > 1が存在して、どんなアルゴリズムでも3-SATをcⁿより速くは解けないと述べます。巧妙なアルゴリズムで底を2未満に縮めることはできても、準指数以下まで下げることは決してできない、というわけです。形式的には、δ > 0が存在して、3-SATは時間O(2δn)では解けない、となります。
何十年もの間、進展はこの絵に沿っていました。研究者たちは底を削り続けましたが、1より十分大きいままでした。3-SATは多くの他の問題に変換できるため、ETHは実用的な前提条件として広く使われました。研究者はクリーク、頂点被覆、独立集合などの問題も大幅には速く解けないと主張するのにETHを用いました。
新しい結果の位置づけ
| アプローチ | 3-SATの実行時間 | 指数的に増加？ |
|---|
| 力まかせ探索 | 2ⁿ | はい |
| 2026年10月以前の最良（決定的） | 約 1.328ⁿ | はい |
| 2026年10月以前の最良（乱択） | 約 1.308ⁿ | はい |
| OpenAIとAnthropic（2026年10月） | 2^O(n log log n / √log n) | いいえ：準指数 |
この新しい上界は略記で2o(n)と書かれます。追加される各変数あたりのコストはnが大きくなるほど1に近づきます。これはまさにETHが不可能だとしたものです。
OpenAIとAnthropicの発表内容
両研究所は事実上同じ準指数の上界に独立に到達し、いずれも証明を定理証明支援系Leanで機械検証しました。
| | OpenAI | Anthropic |
|---|
| 論文 | "The Exponential Time Hypothesis Is False"（67ページ） | "A 2o(n) Time Algorithm for 3-SAT"（49ページ） |
| モデル | 名称非公開の社内モデル | 著者としてクレジットされた社内Claude研究モデル |
| 中核アイデア発見 | 2026年10月16日 | 2026年10月16日 |
| 公開日 | 2026年10月26日 | 2026年10月26–27日 |
| 検証 | ETHを依然として反証するやや弱い上界のLean証明 | Mathlibに対するLean 4の証明を、第二のカーネルでも再検証 |
| 追加主張 | 高速化はNP全体には及ばない | 強ETH（SETH）も反証；新たな回路下界 |
Anthropicは、Claudeが約1,400万トークンの出力を生成した後、人間の入力なしで中核アルゴリズムを見つけたと述べています。その方法はテンソルネットワークとランク議論を用います。研究者は最終的な論文の仕上げを支援しました。
なぜ同じ日に両者が発見したのか？
どちらの研究所もタイミングについて説明していません。Anthropicの論文は、両結果は独立かつ同時であると述べ、2つの解説は本質的に同じ上界に至るまでの数学的経路が異なります。
いくつかの背景を踏まえると、この重なりは当初ほどは驚きではありません。両研究所はモデルを未解決問題の長いリストに向けており、OpenAIだけでも10月初旬に何百本ものAI生成数学原稿を公開しました。ETHはこの分野で最もよく知られた標的の1つで、両モデルは同じ公開研究から学習しています。独立かつ同時の発見は科学では古くから見られるパターンで、微積分におけるニュートンとライプニッツ、自然選択におけるダーウィンとウォレスのような例があります。
証明の堅牢性は？
Leanは、形式的な主張がその公理から論理的に導かれることを確認します。ただし、その形式的主張が論文と同じ内容を述べているかまでは確認できません。Anthropicは、この一致を機械がチェックしていないと述べ、OpenAIは自らのLeanファイルが見出しよりわずかに弱い上界を示しているとしています。
現在、この問題を提案した同じ研究者であるImpagliazzoとPaturi、さらにMITのRyan Williamsが、形式的主張が本当にETHを捉えているか評価するためのワークショップを組織しています。彼らの書簡は、レビューに参加することが支持を意味するわけではないと強調しています。この記事執筆時点では、公開された欠陥は見つかっていません。
WilliamsはOpenAIの証明の一部は手慣れたものに見える一方で、「2、3箇所の異質に見える部分」は依然として精査が必要だと述べています。ETHの提案者の一人であるImpagliazzoは、この結果をきわめて意外性の高いものと表現しています。
何が変わり、何が変わらないのか
実務上、今日すぐに変わることはほとんどありません（ほっ）。新しいアルゴリズムは、現実のコンピュータが保持し得る規模をはるかに超える巨大な入力でのみ力まかせ探索を上回ります。
高速なSATソルバは生まれない
Anthropicの論文によると、その手法が力まかせ探索を上回るのは天文学的に巨大な入力に限られます。典型的な「変数1個あたり5節」の式では、交差点は約1万桁の数字です。最も一般の場合では、およそ1億桁の数字になります。
著者らはまた、この手法が約1,000万変数未満では役に立たない可能性が高いと述べています。半導体検証、スケジューリング、計画で使われるSATソルバがこの結果で速くなることはありません。
暗号は破られていない
この結果はP対NPには触れていません。誰もそれを装ってはいません。OpenAIは、このアルゴリズムが実際の暗号系を破るかどうかを確認し、破らないとかなり自信を持っていると述べています。
理論は書き換えに
より大きな影響は研究面にあります。ETHやSETHに基づく困難性の結果は新たな拠り所を必要とし、自身の数年分の仕事を見直す必要があると語る研究者もいます。もっとも、すべてが崩れるわけではありません。Anthropicは、この結果が多くのきめ細かな計算量の結果を支える直交ベクトル問題を反証するものではないと述べています。
AIにとっての意味
見出しの本質は3-SATそのものというより、「誰が答えを見つけたか」です。専門家が一世代にわたり信じてきた予想を、2つのAIシステムが独立に覆しました。
研究の協働者としてのAI
研究者たちは今、1～2週間に1件のペースで新しいAI成果が現れ、進行中のプロジェクトを揺さぶっていると述べています。Leanのような形式手法は、機械が書いた長い証明を人間が一行ずつ再導出せずとも信頼できるため、中核的存在になりつつあります。
隠れた近道と自己改善
ETHは、ある種の探索問題には賢い近道が存在しないという信念を体現していました。もしその信念が誤りなら、他の明らかに難しそうな問題にも近道が隠れているかもしれません。
私は、アルゴリズム発見が再帰的自己改善（AIシステムがより良いAIの設計を助けるという考え）の観点で、そうした近道が大いに効く領域の一つだと考えています。AIを用いてより高速なアルゴリズムを見つけることは、その具体的な道筋の一つですが、今回の結果自体が直接それを実現しているわけではありません。
データ実務者への示唆
データでものづくりをする人にとって、次の3つが要点です。
- 計算量理論は机上の空論ではない：問題がNP困難である理由を知ることは、厳密探索ではなくヒューリスティック、近似、ソルバを検討すべき場面を見極める助けになります。
- 検証はスキル：AIがより多くのコードや分析を生み出すほど、その出力を（テスト、証明、再現可能なパイプラインで）チェックすることは、作ることと同じくらい重要になります。
- 漸近は誤解を招き得る：理論上「より速い」アルゴリズムが、現実的な規模では役に立たないことがあります。
結論
もし証明が専門家の精査を生き延びれば、指数時間仮説は（オイラーのべき乗和予想のように）広く信じられていたが誤りだった予想の短いリストに加わります。しかしP対NPは依然として未解決で、暗号は当面安全です。
今後注目すべき節目は、ETHの提案者が主導するレビュー・ワークショップ、アルゴリズムの独立再実装、そして誰かが上界をさらに引き締めるかどうかです。
この記事の背景にある基礎を身につけるには、データ構造とアルゴリズム、Pythonプログラミング、機械学習のコースをご覧ください。結果を読み解くのに役立つBig-Oの考え方も扱っています。
OpenAIとAnthropicは、それぞれが指数時間仮説が偽であることを示す証明を公開しました。
ETHは理論計算機科学における27年来の仮定で、一部の問題は力まかせ探索より大幅に速くは絶対に解けないとします。ところが今、トップAI研究所はそれが単に事実ではないと言っています。
もし証明が持ちこたえれば、これは計算機科学におけるAI生成の成果としてこれまでで最も重要なものになります。同時に、ETHを前提にしていた何百本もの研究論文を文字通り書き換える必要が生じます。
本記事では、指数時間仮説が実際に何を意味するのか、関連するP対NPと併せて平易に説明します。さらに、2つの研究所が具体的に何を主張しているのか、証明はどのように確認されたのか、そして暗号に関して何が（そして何が）変わらないのかを見ていきます。
平易に言うP対NP
P対NPは、「答えの正しさを簡単に確認できるすべての問題は、簡単に解くこともできるのか？」という問いです。ミレニアム懸賞問題の7つのうちの1つであり、今回のニュース後も未解決のままです。
数独は古典的な例です。埋められたグリッドのチェックは数秒で済みます。各行・列・ブロックに重複がないかを確かめるだけです。一方で、ほぼ空のグリッドから解を見つけるのははるかに時間がかかり、グリッドが大きくなるほどその差は爆発的に広がります。
Pに属する問題はすべてNPにも属します。未解決なのはその逆が成り立つかどうかです。多くの計算機科学者はP ≠ NPと考えており、つまり、ある種の問題は本質的に解く方が確認するよりも難しいと信じています。現代暗号はこの信念に依拠しています。暗号化は容易だが、鍵なしでそれを解くのは難しいべきだ、というわけです。
指数時間仮説（ETH）とは？
ETHはさらに鋭い主張です。特定のNP問題である3-SATは、どれほど巧妙なアルゴリズムでも指数時間を要する、と言います。これは1990年代後半にUCサンディエゴのRussell ImpagliazzoとRamamohan Paturiが提案し、Francis Zaneも基礎的な仕事に貢献しました。
3-SAT問題
3-SATでは、n個の真偽変数と節のリストからなる論理式が与えられます。各節は3つの条件をORでつなぎます。例えば「x₁が真 OR x₄が偽 OR x₇が真」のように。課題は、すべての節を同時に満たすように変数の値を設定することです。
力まかせ探索は2ⁿ通りすべてを試すため、変数が1つ増えるごとに作業量は2倍になります。変数が100個程度でもはや絶望的になるのがわかるでしょう。
ETHの主張
ETHは、ある定数c > 1が存在して、どんなアルゴリズムでも3-SATをcⁿより速くは解けないと述べます。巧妙なアルゴリズムで底を2未満に縮めることはできても、準指数以下まで下げることは決してできない、というわけです。形式的には、δ > 0が存在して、3-SATは時間O(2δn)では解けない、となります。
何十年もの間、進展はこの絵に沿っていました。研究者たちは底を削り続けましたが、1より十分大きいままでした。3-SATは多くの他の問題に変換できるため、ETHは実用的な前提条件として広く使われました。研究者はクリーク、頂点被覆、独立集合などの問題も大幅には速く解けないと主張するのにETHを用いました。
新しい結果の位置づけ
この新しい上界は略記で2o(n)と書かれます。追加される各変数あたりのコストはnが大きくなるほど1に近づきます。これはまさにETHが不可能だとしたものです。
OpenAIとAnthropicの発表内容
両研究所は事実上同じ準指数の上界に独立に到達し、いずれも証明を定理証明支援系Leanで機械検証しました。
Anthropicは、Claudeが約1,400万トークンの出力を生成した後、人間の入力なしで中核アルゴリズムを見つけたと述べています。その方法はテンソルネットワークとランク議論を用います。研究者は最終的な論文の仕上げを支援しました。
なぜ同じ日に両者が発見したのか？
どちらの研究所もタイミングについて説明していません。Anthropicの論文は、両結果は独立かつ同時であると述べ、2つの解説は本質的に同じ上界に至るまでの数学的経路が異なります。
いくつかの背景を踏まえると、この重なりは当初ほどは驚きではありません。両研究所はモデルを未解決問題の長いリストに向けており、OpenAIだけでも10月初旬に何百本ものAI生成数学原稿を公開しました。ETHはこの分野で最もよく知られた標的の1つで、両モデルは同じ公開研究から学習しています。独立かつ同時の発見は科学では古くから見られるパターンで、微積分におけるニュートンとライプニッツ、自然選択におけるダーウィンとウォレスのような例があります。
証明の堅牢性は？
Leanは、形式的な主張がその公理から論理的に導かれることを確認します。ただし、その形式的主張が論文と同じ内容を述べているかまでは確認できません。Anthropicは、この一致を機械がチェックしていないと述べ、OpenAIは自らのLeanファイルが見出しよりわずかに弱い上界を示しているとしています。
現在、この問題を提案した同じ研究者であるImpagliazzoとPaturi、さらにMITのRyan Williamsが、形式的主張が本当にETHを捉えているか評価するためのワークショップを組織しています。彼らの書簡は、レビューに参加することが支持を意味するわけではないと強調しています。この記事執筆時点では、公開された欠陥は見つかっていません。
WilliamsはOpenAIの証明の一部は手慣れたものに見える一方で、「2、3箇所の異質に見える部分」は依然として精査が必要だと述べています。ETHの提案者の一人であるImpagliazzoは、この結果をきわめて意外性の高いものと表現しています。
何が変わり、何が変わらないのか
実務上、今日すぐに変わることはほとんどありません（ほっ）。新しいアルゴリズムは、現実のコンピュータが保持し得る規模をはるかに超える巨大な入力でのみ力まかせ探索を上回ります。
高速なSATソルバは生まれない
Anthropicの論文によると、その手法が力まかせ探索を上回るのは天文学的に巨大な入力に限られます。典型的な「変数1個あたり5節」の式では、交差点は約1万桁の数字です。最も一般の場合では、およそ1億桁の数字になります。
著者らはまた、この手法が約1,000万変数未満では役に立たない可能性が高いと述べています。半導体検証、スケジューリング、計画で使われるSATソルバがこの結果で速くなることはありません。
暗号は破られていない
この結果はP対NPには触れていません。誰もそれを装ってはいません。OpenAIは、このアルゴリズムが実際の暗号系を破るかどうかを確認し、破らないとかなり自信を持っていると述べています。
理論は書き換えに
より大きな影響は研究面にあります。ETHやSETHに基づく困難性の結果は新たな拠り所を必要とし、自身の数年分の仕事を見直す必要があると語る研究者もいます。もっとも、すべてが崩れるわけではありません。Anthropicは、この結果が多くのきめ細かな計算量の結果を支える直交ベクトル問題を反証するものではないと述べています。
AIにとっての意味
見出しの本質は3-SATそのものというより、「誰が答えを見つけたか」です。専門家が一世代にわたり信じてきた予想を、2つのAIシステムが独立に覆しました。
研究の協働者としてのAI
研究者たちは今、1～2週間に1件のペースで新しいAI成果が現れ、進行中のプロジェクトを揺さぶっていると述べています。Leanのような形式手法は、機械が書いた長い証明を人間が一行ずつ再導出せずとも信頼できるため、中核的存在になりつつあります。
隠れた近道と自己改善
ETHは、ある種の探索問題には賢い近道が存在しないという信念を体現していました。もしその信念が誤りなら、他の明らかに難しそうな問題にも近道が隠れているかもしれません。
私は、アルゴリズム発見が再帰的自己改善（AIシステムがより良いAIの設計を助けるという考え）の観点で、そうした近道が大いに効く領域の一つだと考えています。AIを用いてより高速なアルゴリズムを見つけることは、その具体的な道筋の一つですが、今回の結果自体が直接それを実現しているわけではありません。
データ実務者への示唆
データでものづくりをする人にとって、次の3つが要点です。
結論
もし証明が専門家の精査を生き延びれば、指数時間仮説は（オイラーのべき乗和予想のように）広く信じられていたが誤りだった予想の短いリストに加わります。しかしP対NPは依然として未解決で、暗号は当面安全です。
今後注目すべき節目は、ETHの提案者が主導するレビュー・ワークショップ、アルゴリズムの独立再実装、そして誰かが上界をさらに引き締めるかどうかです。
この記事の背景にある基礎を身につけるには、データ構造とアルゴリズム、Pythonプログラミング、機械学習のコースをご覧ください。結果を読み解くのに役立つBig-Oの考え方も扱っています。