はじめに
2026年10月26日、OpenAIは、社内のAIシステムが 指数時間仮説（ETH）を反証した と発表しました。論文とLeanによる形式証明も公開されています。
ここでのETHは Exponential Time Hypothesis の略で、暗号資産のEthereumを指すものではありません。
このニュースを見て、「P＝NPが解けたのか」「暗号が破られるのか」「システム開発の何が変わるのか」と感じた方もいると思います。この記事では、スイッチのON・OFFを決める例から順に説明し、発表された成果と、そこから判断できる範囲を整理します。計算量理論の予備知識は必要ありません。詳しい数式や関連仮説は折りたたみに入れているので、最初は本文だけ読んでも大丈夫です。
正しければ、計算の限界の見積もりが変わる
今回の主張が正しいと確認されれば、 「問題が大きくなると、どうしても計算の手間が急増する」と予想されていた問題の一部で、その増え方の見積もりを変える ことになります。速いコンピューターを用意する話ではなく、計算手順そのものを工夫する話です。この計算手順を「アルゴリズム」と呼びます。
組合せ探索のイメージとして、勤務シフトや配送計画を考えてみます。勤務時間や必要な人数、立ち寄る場所や時間帯など、いくつもの条件を同時に満たす組み合わせを探します。こうした問題には、候補が増えると、一つずつ試す方法では現実的な時間に収まらなくなるものがあります。
今回の研究は、条件を論理式で表すSATについて、その難しさの予想を崩す計算手順を提示した、という発表です。正しければ、これまでの計算限界を見直し、より速い探索・計数アルゴリズムを研究する新しい出発点になります。一部の暗号候補についても、「逆算がどの程度難しいか」という理論上の見積もりに影響します。
将来、扱いやすい構成や実装へ改良できれば、最適化や設計を支援する技術につながる可能性があります。ただし、各業務へ適用できるかは、SATへの変換で問題がどれだけ大きくなるか、実装が実際に速いかを別に確認する必要があります。 今すぐ勤務シフトや配送が高速化する、AWS費用が下がる、既存暗号が解読できるという結果ではありません。
確認日は 2026年10月29日 です。以下はOpenAI公式発表、両社の公開論文・形式化資料、検証を主導する研究者の声明を照合した解説です。筆者がLeanプロジェクト全体を再ビルドしたり、証明全体の数学的な正しさを独立に検証したりしたものではありません。
先に結論
本記事での整理は、次のとおりです。
| 気になる点 | 2026年10月29日時点での読み方 |
|---|---|
| 何が発表されたか | 一定の形の条件式について、条件をすべて満たす組み合わせが何通りあるかを、従来の難しさの予想を崩す増え方の計算時間で正確に数える手順と証明 |
| どれほど重要か | 正しければ、計算量理論で広く使われてきたETHという前提を変える大きな成果 |
| 正しさは確定したか | 公開された形式証明は重要な材料。研究者グループは、参加が正しさの認証ではないと明記 |
| P＝NP問題は解けたか | 今回の結果だけでは、P＝NPもP≠NPも結論できない |
| 実務ですぐ速くなるか | 公開資料から、既存システムの即時の高速化やコスト削減は判断できない |
| 暗号への影響はあるか | 特定の理論的な困難性には影響するが、既存暗号の実用的な解読が示されたわけではない |
まず押さえたいのは、 理論的な重要性と、現在のコンピューターで実用になるかは、それぞれ確認が必要 ということです。
1. 3-SATとは「条件を全部満たす組み合わせがあるか」を調べる問題
SATは、 「いくつもの条件を、すべて同時に満たせるか」 を調べる問題です。名前はSatisfiability（充足可能性）に由来します。「充足」は、ここでは「条件を満たす」という意味です。
例えば、A・B・C・Dという4つのスイッチがあるとします。ONを1、OFFを0とし、次の条件を両方満たしたいと考えます。
- 条件1：AがON、BがOFF、CがONのうち、少なくとも一つを満たす。
- 条件2：AがOFF、BがON、DがONのうち、少なくとも一つを満たす。
AとBをON、CとDをOFFにすれば、条件1はAによって、条件2はBによって満たせます。したがって、この問題の答えは「満たせる」です。
このスイッチを順に変数として書くと、次の式になります。記号が苦手な場合は、上の二つの条件を短く書いたものだと読んでください。
$$
(x_1 \lor \neg x_2 \lor x_3)
\land
(\neg x_1 \lor x_2 \lor x_4)
$$
記号を読み替えると、こうなります。
| 記号・用語 | 意味 |
|---|---|
| $x_i$ | 真か偽を取る変数。1か0と考えてもよい |
| $\neg x_i$ | $x_i$ の否定 |
| $\lor$ | OR。どれか一つが真ならよい |
| $\land$ | AND。両方とも真である必要がある |
| リテラル | 変数そのもの、またはその否定 |
| 節 | かっこ内のように、リテラルをORでつないだ条件 |
3-SATでは、一つの節に含まれるリテラルを最大3個に制限します。節をANDでつないだ形を CNF、各節が最大 $k$ 個のリテラルを持つものを $k$-CNF と呼びます。
上のスイッチの例は、$x_1=1, x_2=1, x_3=0, x_4=0$ という割り当てです。「割り当て」とは、各変数を1か0のどちらにするか決めることです。条件をすべて満たす割り当てを、この問題の「解」と呼びます。
変数が $n$ 個あれば、割り当ては $2^n$ 通りです。これは「2をn回掛ける」という意味です。スイッチが一つ増えるたびに、組み合わせが2倍になります。4変数なら16通り、100変数なら約 $1.27\times10^{30}$ 通りに増えます。すべての候補を順番に調べる方法が「全探索」です。
一方、誰かが解の候補を一つ渡してくれれば、各節を順に調べて正しいかを確認できます。 候補を検査することと、候補を見つけることの難しさは同じとは限りません。
以上はSATの基礎を説明するための筆者の例です。用語と問題設定はAnthropic論文のIntroductionでも説明されています。
2. ETHは、どの程度の「難しさ」を仮定していたのか
「仮説」と「反証」を言い換える
仮説は、もっともらしいと考えられていても、まだ証明されていない主張です。ETHは、大まかには 「3-SATには、規模を大きくしたときにも越えられない、指数的な難しさがある」 という予想です。
反証は、その主張が成り立たないことを示すことです。今回は、3-SATの特定の問題を一つ速く解けただけでは足りません。一般の入力に対して、仮説が禁止していた速さを保証するアルゴリズムと、その証明が必要です。
指数時間と亜指数時間は、計算の手間の「増え方」
「計算量」は、問題の規模が増えたときに、必要な計算の手間がどう増えるかを表します。今回見るのは、主に計算時間の増え方です。
全探索の候補数は、スイッチ10個なら1,024通り、20個なら1,048,576通り、30個なら1,073,741,824通りです。このように、規模を一定量増やすたび、一定の倍率で増えるのが「指数的」な増え方です。
対して、 「亜指数時間」は、どの固定した正の割合の指数時間よりも、十分大きな規模では増え方が遅い という意味です。「亜」が付いていても、小さい、すぐ終わる、という意味ではありません。
ETHは、この亜指数時間では一般の3-SATを解けないと予想していました。
数式でも確認したい方へ：ETHの定義と計算時間の比較
以下では、変数数を $n$ とします。
より正確には、ある定数 $\delta>0$ が存在して、3-SATを $O(2^{\delta n})$ 時間で解くアルゴリズムは存在しない、という形で述べられます。ここでは入力を読む時間などの多項式因子を省略しています。固定幅の式では、重複する節を除けば節数も変数数の多項式に抑えられます。
ETHの定式化と位置付けは、Impagliazzo・Paturiの論文と、Anthropic論文のIntroduction・Section 6を参照してください。
全探索より速いだけでは、ETH反証にならない
次の表は、$n$ に依存する計算時間の主な部分を比べるための例です。入力長の多項式因子は省略しています。
| 計算時間の例 | 分類 | 3-SAT一般にこの保証を得た場合 |
|---|---|---|
| $2^n$ | 指数時間 | 全探索の基本形 |
| $1.1^n$ | 指数時間 | ETHと両立する |
| $2^{n/1000}$ | 指数時間 | これでもETHと両立する |
| $2^{\sqrt n}$ | 亜指数時間 | ETHを反証する |
| $n^3$ など、入力長の多項式時間 | 多項式時間 | ETH反証に加えてP＝NPを導く |
$2^{n/1000}$ は非常に速く見えますが、指数部分は依然として $n$ に比例しています。
対して、亜指数時間を表す $2^{o(n)}$ は、指数部分を $n$ で割った値が、$n$ の増加とともに0へ近づくことを意味します。$2^{\sqrt n}$ なら、$\sqrt n/n=1/\sqrt n$ が0に近づきます。
今回の主張は、指数の底を少し小さくする改善を超え、この亜指数時間へ到達したというものです。 「何倍速くなったか」だけではなく、「規模を増やしたときの増え方が変わるか」がポイントです。
3. OpenAIが示したと主張するのは「解の個数」を数える手順
先ほどのスイッチの例では、「条件を満たせるか」に加えて、「満たす設定は何通りあるか」も考えられます。筆者の例を全16通り調べると、条件を満たす設定は12通りあります。
| 調べたいこと | この例の答え |
|---|---|
| 条件を満たす設定はあるか | ある |
| 条件を満たす設定は何通りか | 12通り |
| 条件を満たす設定を全部書き出す | 12個の設定を一つずつ出力する |
今回の主張は、二つ目の「何通りか」を正確に求める手順です。OpenAI論文の定理1.1は、固定した $k\ge2$ について、$k$-CNFを満たす割り当ての個数を、決定的なアルゴリズムで正確に数えるとしています。「固定したk」とは、一つの条件に入れられる項の上限を先に決め、問題が大きくなってもその上限は変えない、という意味です。
「解があるか」を判定するSATに対し、解の個数を数える問題は #SAT と呼ばれます。今回の結果は、この計数を対象にしています。個数が0なら解なし、正なら解ありなので、計数ができればSATの判定もできます。
ここで、「個数を数える」と「すべての解を出力する」は区別します。
解が最大 $2^n$ 個あっても、個数を二進数で表すだけなら $n+1$ ビットで足ります。したがって、出力が全解のリストのような長さになるとは限りません。
「決定的」とは、同じ入力に対して、乱数の選び方に依存せず、決まった手順で計算するという意味です。発見にAIを使っていても、発見されたアルゴリズムは通常の計算手順として記述されています。実行のたびに大規模言語モデル（LLM）へ相談することを前提にした速度保証ではありません。
論文とLeanでは、保証している計算時間が違う
論文に書かれた最も強い速度保証と、Leanという検証ツール向けに証明を書いた範囲は一致していません。Lean側が対象にするのは、論文よりも弱い速度保証です。それでも、正しければETHを反証するには十分な亜指数時間になっています。
ここでいう「時間上界」は、 「どんな入力でも、計算時間はこの範囲までに収まる」という保証 です。実際に動かして測った所要時間とは区別します。
詳しい時間上界：論文とLeanの数式を比較する
OpenAIの形式化対象の説明は、この違いを明示しています。以下は、その説明と論文定理1.1の要約です。
- $n$：変数数
- $m$：節数
- $k$：一つの節に含まれるリテラルの最大数。固定する
- $L$：入力を符号化したビット長
- $D$：節数の条件に使う固定の正定数
| 対象 | 公表されている時間上界 |
|---|---|
| 改訂論文の一般の場合 | $(n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})}$ |
| 改訂論文で $m\le Dn$ の場合 | $(n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})}$ |
| 公開Lean形式化の対象 | $(L+1)^{O_k(1)}2^{O_k(n(\log\log n)^2/\sqrt{\log n})}$ |
$O_k$ という添字は、隠れている定数が固定した $k$ に依存しうることを表します。論文はビット演算、Leanは定義した機械のステップとして時間を扱います。使用領域には、多項式の上界を与えるとしています。
ここでの $\log$ は対数です。例えば底を2とする対数なら、「2を何回掛けると、その数になるか」を表します。$\log\log n$ は、対数を取った値に、もう一度対数を取る記号です。
それでも、
$$
\frac{(\log\log n)^2}{\sqrt{\log n}}\longrightarrow0
$$
なので、この弱い上界も亜指数時間です。定義と証明が適切なら、ETH反証には十分です。
4. どうやって全探索を避けるという話なのか
以下は、OpenAI論文のSections 2〜6とAppendix Dから、読むための着眼点を筆者が整理したものです。証明そのものの代わりになる説明ではありません。
まず、全探索なら、スイッチの設定を一つずつ試し、条件を全部満たせば1点、満たさなければ0点として足せば、解の個数が出ます。しかし、それでは候補数の多さがそのまま計算の手間になります。
論文が扱うのは、条件を数式の計算へ置き換え、問題を分割した結果と、グループ間のつながりを使って、全体の個数を復元する方法です。筆者の読み方としては、 「答えを一つずつ並べずに、答えの個数をまとめて計算できるか」 と考えると、狙いをつかみやすくなります。
ただし、社員の配置を部署別に分けても、「同じ人を二つの部署へ同時に配置できない」という条件は残ります。SATでも同様に、分けたグループをまたぐ条件を、少ない手間で正確に処理できるかが難しい点です。
手法をもう少し詳しく：計数式・補間・テンソルネットワーク
解の個数は、概念的には次の式で表せます。$\sum$ は足し合わせること、$\prod$ は掛け合わせることを表します。
$$
\text{解の個数}
=\sum_{\text{全割り当て}}
\prod_{\text{各条件}}\mathbf{1}[\text{条件を満たす}]
$$
条件を満たせば1、満たさなければ0です。積を取ると、すべての条件を満たした割り当てだけが1として残ります。ただし、この総和をそのまま計算すれば全探索です。
論文本文では、論理式を多項式の計数問題へ移し、グループ間で共有する情報を線形な要約へ集め、分割した計算から補間で正確な個数を復元する構成を扱っています。より強い速度保証には、付録Dのテンソルネットワークの縮約を使っています。ここでのテンソルネットワークは、局所的な条件同士のつながりを多次元の配列で表し、総和や積を計算する表現だと考えてください。
「補間」は、必要な地点で求めた値を使って、元の多項式の情報を復元する操作です。ここでは、単なる近似や予測という意味ではありません。「縮約」は、配列の添字に沿って積や和を取り、全体の値を計算する操作です。
読む際の核心は、その依存関係を少ない計算で処理できるのか、変換や補間の費用、扱う整数の桁数まで含めて速度保証が成り立つのか、という点にあります。
5. 「Leanで検証した」は、どこまでを意味するのか
Lean（リーン）は、数学の証明を機械で検査するためのツールです。「形式証明」とは、定義や証明を、機械が厳密に扱える言語で書いたものです。自然言語の文章だけを読む場合に比べ、推論の抜けを検査できる重要な材料になります。
イメージとしては、答案の結論だけを見るのではなく、途中の一行一行が決められたルールから導けるかを確かめる仕組みです。ただし、 答案の筋道が正しいことに加えて、「本当に、解きたかった問題を正しく書けているか」も確かめる必要があります。 問題文や計算時間の数え方を意図と違う形で定義していれば、その定義の下で証明が通ることだけでは不十分です。
一方、確認する対象には複数の層があります。次の表と図は、Anthropicの形式化説明も踏まえて、筆者が整理したものです。
| 確認する層 | 確かめること |
|---|---|
| 形式的な正しさ | 定義された命題が、許可された公理から証明されているか |
| 定義の適切さ | 通常のSAT、入力表現、計算時間、ETHを意図どおり表しているか |
| 論文との対応 | 論文で主張する範囲と、形式化された定理の範囲が対応しているか |
表の「命題」は正しいかどうかを問える主張、「公理」は推論の出発点として認める前提です。
機械が検査した命題と、読者が理解している数学的な主張との対応も重要です。例えば、入力を読む費用が適切に数えられているか、許される操作に不自然なものが含まれていないか、などを確認します。
sorry を見つけたことだけでは、未完成とは判断できない
Leanの sorry は、証明を埋めずに置くための記法です。最終定理が sorry に依存していれば問題になります。
ただし、今回の公開物には、比較用に「証明すべき命題」を置くファイルと、実際の証明側のファイルがあります。
OpenAIの比較用ファイルには sorry がありますが、検証設定は別の証明モジュールと最終定理を指定しています。証明側のFinal.leanには、その定理の証明本体があります。
したがって、比較用ファイルだけを見て判断せず、実際の証明の依存先と検証結果を確認する必要があります。設定に許可公理が書かれていることと、その設定での検査を自分が再現したことも区別します。
検証を主導する研究者も、正しさの認証とは区別している
Russell Impagliazzo・Ramamohan Paturi・Ryan Williamsの声明は、3氏の参加が主張の正しさの認証ではないと明記しています。正しさ、限界、帰結を、コミュニティで独立に検討する方針です。
OpenAIは公式発表で、共同研究を主導する研究者への報酬を支払わず、秘密保持契約を求めず、結論の公表を自由にすると説明しています。
2026年10月29日時点で今回確認した一次資料からは、この検証グループが独立検討の完了を宣言したことまでは確認できませんでした。
6. Anthropicも同時期に、別の反証を公開している
Anthropicの公式リポジトリにも、論文とLean 4形式化が公開されています。
発見と公開の日付は、資料に応じて区別します。次の表は、OpenAI公式発表、両社の論文、Anthropicの公開コミットから整理しました。
| 日付 | 資料に記載された出来事 |
|---|---|
| 10月16日 | 両社が、それぞれ社内モデルによる核心となる発見の日として説明 |
| 10月17日 | OpenAIがLean形式化の日として説明。OpenAI論文表紙の初稿日 |
| 10月25日 | OpenAI公開論文に記載された改訂日 |
| 10月26日 | OpenAI公式発表の日。Anthropic論文表紙に記載された日付 |
| 10月27日 | Anthropicが論文・Lean形式化をGitHubへ追加したコミットの日付 |
Anthropic論文の2ページ目は、核心となるアルゴリズムを社内のClaude研究モデルが10月16日に発見し、出力トークン数は 1,400万、その段階では人間の入力はなかったと説明しています。その後、研究者がClaudeと説明を改善したとしています。これは発見経緯についてのAnthropic自身の説明です。
両社とも、固定幅SATの解の個数を亜指数時間で正確に数えるという主張ですが、 二社が発表したこと自体が、それぞれの正しさや発見経緯の独立性を保証するわけではありません。 各社の論証を確認する必要があります。
また、社内研究モデルの成果から、通常提供されているChatGPTやClaudeで同じ発見を再現できるとは判断できません。
7. P＝NP問題、既存の論文、ほかの問題には何が起きるのか
P＝NPも、P≠NPも結論していない
先ほどのスイッチなら、正しい設定を教えてもらえば、条件を満たすかを順に確認できます。しかし、誰も設定を教えてくれないときに、それを自分で見つけるのも同じ程度に容易なのでしょうか。この違いに関わるのがP対NP問題です。
Pは多項式時間で判定できる問題のクラスです。NPは、「YESという答えの証拠」を多項式時間で検査できる問題のクラスです。NPは「多項式時間では解けない」の略ではありません。
「多項式時間」は、入力の長さに対して、二乗・三乗など、固定した次数の多項式で計算時間を抑えられるという意味です。例えば三乗なら、規模が2倍になると計算量は8倍になります。理論上の効率を分ける基準ですが、次数や定数が大きければ、実際に短時間で終わるとは限りません。
SATなら、変数の割り当てが「解がある」という答えの証拠です。P対NP問題は、こうした検査が容易な問題を、判定自体も多項式時間で解けるのか、という問いです。
論理関係として、ETHはP≠NPを含意します。
$$
\mathrm{ETH}\Rightarrow\mathrm{P}\ne\mathrm{NP}
$$
しかし、ETHが偽でも、P＝NPとは限りません。「多項式時間では解けないが、亜指数時間では解ける」という可能性が残ります。
今回示されたという亜指数時間の上界は、多項式時間で解けるという保証ではありません。同時に、この上界だけで「これ以上は速くならず、絶対に多項式時間にはならない」と証明したことにもなりません。
SETHや#ETHには影響するが、帰結は一つずつ読む
ETHに近い別の仮説にも影響します。ただし、 「ある難しさの予想が崩れた」ことと、「ほかの未解決問題も全部解けた」ことは分けて確認します。 詳しい名前を知らなくても、この点を押さえれば先へ進めます。
関連仮説とNP完全性への影響を確認する
以下はAnthropic論文のIntroduction・Section 7と、今回の計数結果から整理した帰結です。主張が正しいことを前提にしています。
| 対象 | 今回の結果からいえること |
|---|---|
| ETH | 反証される |
| SETH：強指数時間仮説 | SETHはETHを含意するため、反証される |
| #ETH：数え上げ版の指数時間仮説 | 今回は正確な計数まで対象としているため、反証される |
| P＝NP／P≠NP | 決着しない |
| NP完全性という分類 | その分類自体は維持される |
| Orthogonal Vectors仮説 | 今回の結果から反証されたとはいえない |
#ETHについては、単にETHを否定しただけで自動的に否定されるのではなく、今回のアルゴリズムが計数まで対象にしていることが理由です。
「NP完全」は、NPのすべての問題を多項式時間の変換で持ち込める、NPに属する問題の分類です。その分類と、具体的にどの速度で解けるかは別に扱います。Orthogonal Vectorsは、ベクトル同士の内積が0になる組があるかを問う問題で、その計算時間に関する仮説へ影響を自動的に広げることはできません。
「ETHを前提にした論文が全部間違い」にはならない
既存の定理が「ETHが正しければ、問題Xをこの速度では解けない」という条件付きのものだったとします。
ETHが反証されても、その条件付きの推論自体が誤りになるとは限りません。変わるのは、ETHを現実の難しさの根拠として使えるかどうかです。また、前提が崩れただけで、問題Xの速いアルゴリズムが手に入るわけでもありません。
研究者3氏の声明も、ETH研究から生まれたアイデア、問題間の還元、技法の価値は残ると述べています。
「すべてのNP問題が亜指数時間になる」とも限らない
還元 は、元の問題の答えを得るために、別の問題へ変換することです。例えば、配置の条件をSATの条件式へ書き直し、SATの解から元の問題の答えを得る、と考えてください。この変換で、入力サイズが膨らむことがあります。
例えば、元の問題サイズが $N$、変換後のSAT変数数が $n=N^2$ なら、$2^{o(n)}$ の保証は $2^{o(N^2)}$ になります。これだけでは $2^{o(N)}$ を意味しません。
具体例として、SATを $2^{\sqrt n}$ 時間で解けたとしても、$n=N^2$ を代入すれば $2^N$ です。元のサイズに対しては指数時間のままです。
一方、サイズを適切に保つ還元がある独立集合、クリーク、頂点被覆、固定色数の彩色などには大きな影響があります。これらの扱いはOpenAI論文の系1.3やAnthropic論文のSection 7で議論されています。
8. 業務システムは、すぐに高速化するのか
現時点の公開結果から、既存の業務システムがすぐ高速化するとは判断できません。今回の主張は、入力を限りなく大きくしたときの計算時間の増え方を扱っています。このように、十分大きな規模での振る舞いに注目する見方を「漸近的」といいます。
例えば、毎回の準備に非常に長い時間がかかる新方式と、準備は短いけれど件数が増えるほど急激に遅くなる旧方式を比べると、逆転するのが途方もない件数になることがあります。増え方の改善と、手元のデータで速くなることを分ける必要があるのは、このためです。これは理解のための例で、今回の実測結果ではありません。
Anthropicは公式READMEで、実用的な式を解くことについては何も示さないと明記しています。さらに論文2ページ目では、節数が $m=5n$ の場合、自分たちの上界が全探索の $2^n$ を下回るには、
$$
n>10^{10,000}
$$
が必要だと説明しています。1の後ろに0が1万個続く規模です。これは Anthropic側の上界の話 で、OpenAIの性能値ではありません。
多項式空間という保証も、「現在のPCでメモリに余裕をもって動く」という意味ではありません。隠れた定数や多項式の次数が実用性を左右します。
こうした制約があっても、ETH反証としての数学的な価値が失われるわけではありません。ETH自体が、十分大きな入力まで含む計算量についての仮説だからです。
OpenAIの構成にも、非常に大きなサイズ条件がある
OpenAI論文のAppendix D.4.1〜D.4.2、57〜58ページには、小さいサイズを直接総和で処理し、条件を満たす十分大きなサイズで高速化部分を使う構成があります。
そこで使うパラメータは、$\lambda=\lceil\log_2 s\rceil$、$\varepsilon=1/(128\cdot1024)=1/131072$、根の深さでは $u_0=\lfloor\varepsilon\lambda\rfloor$ です。必要条件の一つに $\lambda^{4/5}\le u_0$ があります。
$2\le s\le2^{131071}$ では $u_0=0$ なので、この条件を満たせません。これは、論文の式から導ける 特定の構成の条件についての観察 です。$s$ は常にSATの変数数そのものではなく、この境界を超えれば速くなるという保証でもありません。将来の改良版にも同じ規模が必要だと示したものでもありません。
9. 暗号・Bitcoin・Ethereumへの影響はどう考えるか
暗号では、正しい鍵を持つ人は読めても、鍵を知らない第三者には読み解くのが難しい、という性質を利用します。今回確認したETH関連資料は、RSA、AES、楕円曲線暗号について、具体的な鍵長・計算資源・所要時間を伴う実用的な解読結果を示していません。
SATを速く解けることから具体的な暗号への攻撃を評価するには、少なくとも、どの方式を、何変数のSATへ変換し、どの程度の前処理・時間・メモリで解けるかが必要です。鍵長とSATの変数数が同じになるとは限りません。
例えば鍵長が $\lambda$ ビットでも、SAT化して変数数が $\lambda^2$ になれば、計算量の式に代入するのは $\lambda^2$ です。その保証が $2^\lambda$ の鍵全探索より優れているとは限りません。
なお、「最悪ケースの結果だから、平均的な入力を使う暗号には関係ない」という説明も適切ではありません。すべての入力をある時間以内で解ける最悪ケースの上界なら、平均的な入力にも適用できます。重要なのは、還元後のサイズと実際の計算費用です。
定数局所性を持つ候補一方向関数には、理論的な影響がある
OpenAI論文のAppendix C.2、52〜53ページは、出力の各ビットが定数個の入力ビットだけに依存する写像について、逆像を数え、存在すれば見つける手順を示しています。例としてGoldreich型の候補一方向関数を挙げています。
一方向関数は、大まかには、順方向の計算は容易でも逆算は難しいことを期待する関数です。Goldreichの構成では、入力の小さな部分集合ごとに関数を適用し、それらの集合が重なり合います。
出力ビット数が入力ビット数の多項式に収まる設定では、今回の主張が正しければ、これらの定数局所性の構成を亜指数時間で逆算できるとしています。したがって、$2^{\Omega(n)}$ 級の逆算困難性は否定されます。
ただし、多項式時間で逆算できることまでは示していません。通常の、多項式時間の攻撃に対する一方向性まで否定したわけではありません。
現時点では、 特定の理論的な安全性の見積もりには影響するが、BitcoinやEthereumを含む既存システムが実用的に破られたという結果にはなっていない と読むのが適切です。
10. AI活用とシステム開発の立場で受け止める
ここからは、公開資料を踏まえた筆者の判断です。
この発表だけを理由に、クラウド構成、DB、認証基盤、暗号方式、既存の最適化ソルバーを変更する根拠は読み取れません。実務への導入には、対象ワークロードでの実装、ベンチマーク、メモリ使用量、既存方式との比較が必要です。今回の式から「処理時間が何％減る」「AWSコストが何％下がる」といった数字は導けません。
一方、日々の開発にも取り入れられるのは、 AIの提案と、検査できる成果物を対応付ける考え方 です。
例えば、アルゴリズムの提案には正しさの説明と反例探索、コード変更には仕様との対応と実行結果、最適化案には条件をそろえた計測を付ける。セキュリティの主張には、前提と対象範囲を明示する、といった進め方です。
今回の成果が正しいと確認されれば、AIによる科学的発見の重要な事例になります。ただし、一つの研究成果から、幅広い業務での判断の安定性やAGIの完成までを結論することはできません。
今後確認したいのは、独立検証の具体的な報告、形式化と通常のETHとの対応、証明の簡略化、実用的な構成や実装、暗号や最適化への対象を絞った評価です。成果を発見することに加え、理解し、問い直し、次の研究へつなぐ仕事も重要になります。
参考・確認先
確認日はいずれも2026年10月29日です。OpenAI論文は10月25日改訂版、Anthropic論文は表紙に10月26日と記載された版を参照しました。
- OpenAI：学術コミュニティとの連携による科学的理解の深化
- Impagliazzo・Paturi・Williams：ETH Refutation: Examination and Discussion
- OpenAI：The Exponential Time Hypothesis is False
- OpenAI：Lean形式化の対象範囲
- Anthropic：A 2^o(n) Time Algorithm for 3-SAT・論文と形式化
- Anthropic：形式化した主張・計算モデル・論文との差異
- Impagliazzo・Paturi：On the Complexity of k-SAT
おわりに
ETH反証のニュースを読む際は、発表された主張、機械で検査する範囲、人が照合する定義、実務に持ち込む条件を分けて確認することが大切です。
Wealthy Design, Inc.では、Webシステム開発、クラウド活用、AIを使った業務改善に取り組んでいます。
AWS・Web開発・AI活用のご相談や、採用・カジュアル面談については、Wealthy Design, Inc.公式LINEでもお問い合わせいただけます。