「自分の生きているうちには見られないと思っていた」
先端AIやグラフィックス論文の解説でおなじみの海外YouTubeチャンネル（Two Minute Papers）が、珍しく興奮を隠せない様子で動画を公開していました。
オープンAI（OpenAI）の研究チームが、計算機科学の根幹を揺るがすプレプリント論文を公開したというのです。
タイトルは直球そのもので、『The Exponential Time Hypothesis is False（指数時間仮説は偽である）』。
順列組み合わせ爆発の天井が、ついに破られたのかもしれません。
＊＊＊
ここで、少しだけ数理科学の事実（ファクト）を整理しておきましょう。
コンピュータの世界には、「3-SAT（3充足可能性問題）」と呼ばれる有名な難問があります。
無数の条件（「AまたはBまたはCが真」「DまたはEまたはFが真」…）が複雑に絡み合ったときに、すべての条件を同時に満たす組み合わせが存在するかどうかを判定する問題です。
条件が10個や20個なら力任せ（総当たり）で解けますが、100個、1,000個と増えていくと、調べるべき組み合わせの数が 2^n のように指数関数的に膨れ上がります。
宇宙の寿命（138億年）どころか、何兆年スーパーコンピュータをぶん回しても計算が終わらない。これがいわゆる「順列組み合わせ爆発」です。
そして計算複雑性理論の世界には、「どんなに賢いアルゴリズムを作っても、最悪ケースでは指数関数的な計算時間 2^{\Omega(n)} が絶対にかかる」という強力な予想（指数時間仮説：ETH）が存在していました。
「この問題には魔法の近道などない。爆発するものは爆発するのだ」というのが、過去数十年にわたる人類の共通認識だったわけです。
ところが今回のOpenAIの論文は、「3-SATを劣指数時間（Sub-exponential Time：真の指数爆発よりもずっと遅いペースでしか増えない計算時間）で解く具体的なアルゴリズムを発見した」と主張しています。
※もちろん、これは査読前のプレプリント（事前公開論文）ですから、世界中の数学者や計算機科学者による徹底的な検証（反証チェック）はこれからです。数式に致命的な穴が見つかって幻に終わる可能性も十分にあります。
＊＊＊
もし、万が一この証明が正しかった場合、工学の現場には何が起きるでしょうか。
ここからは論理的な推測（アナリシス）です。
3-SATという問題は、数学の世界ではあらゆる「NP完全問題」の総本山（ハブ）として知られています。
・無数の配送先を最も効率よく回る「巡回セールスマン問題」
・何千億個ものトランジスタを最小面積で配線する「LSIのチップレイアウト」
・複雑に絡み合う分子の結合を探る「創薬・タンパク質フォールディング」
・全国の発電所と工場の電力をリアルタイムで最適配分する「電力グリッド制御」
現代社会を支える無数の最適化問題は、すべて数学的に3-SATへ変換（リダクション）できます。
これまで産業界のエンジニャーたちは、「どうせ厳密に解こうとしたら組み合わせ爆発で死ぬのだから」と諦め、遺伝的アルゴリズムや焼きなまし法といった近似計算（ヒューリスティクス）でお茶を濁してきました。
その「計算量の天井」が一段低い場所へ引きずり下ろされるとすれば、半導体設計から新薬開発、物流網の設計に至るまで、産業の基盤が根本から塗り替えられることになります。
＊＊＊
ここから先は、純粋な妄想（思考実験）です。
もし組み合わせ爆発の天井が本当に消滅したとして、ニポーンの現場の生産性は劇的に向上するでしょうか？
例えば、アルゴリズムが全国の物流拠点の「数学的に完璧な最適配送ルート」をわずか0.01秒で弾き出したとします。
しかし、その最適ルートを実行に移すためには、
1. 運行管理部長への事前説明資料をパワポで作る（3日）
2. 購買部門と下請け各社の調整会議を開く（1週間）
3. 役員会の稟議にかけてハンコを4人からもらう（2週間）
という、別の次元の「組織のむだ時間」が控えています。
アルゴリズムが計算時間を何億年分短縮してくれようが、伝票バケツリレーの待ち時間が数週間単位で横たわっている限り、システム全体のボトルネックは1ミリも動きません。
制御理論の「サイクルタイム」の法則を思い出すまでもありませんな。
むしろ本当に困るのは、「この問題は組み合わせ爆発が起きるため、スーパーコンピュータでも検討に3ヶ月かかります」と言って、高額な調査費と工数を請求していたITコンサルや受託SIerの方々かもしれません。
「できません」と言い訳できる数学の盾が、音を立てて砕け散ろうとしているわけですから。
※もっとも、そのときは「アルゴリズムの計算結果が正しいかどうかを人間が目視で確認する検証作業」という新たな人月ビジネスが発明されるだけな気もしますが。
→数学の天井が破られても、人間のバケツリレーの天井はどこまでも頑丈なのでしたぁ。
ツイッキー：
なお、ネットの一部で「これで現代の暗号（RSAや楕円曲線暗号）が明日にも全滅する！」と大騒ぎしている向きもありますが、暗号の安全性は主に素因数分解などの別ジャンルの計算困難性に基づいているため、直ちに銀行口座がすっからかんになる心配はありません。世界中の暗号学者が胸を撫で下ろしているのか、あるいは徹夜で論文の追試をしているのかは知りませんが。
脚注：
We present a randomized algorithm that solves 3-SAT in sub-exponential time, refuting the Exponential Time Hypothesis (ETH). The algorithm runs in time 2^{o(n)} on formulas with $n$ variables, establishing a new upper bound for the core NP-complete problem.
OpenAI: The Exponential Time Hypothesis is False (Preprint, Oct 2026) / Two Minute Papers: OpenAI Claims It Just Did The Impossible
りんくる：
・富の源泉2020SPウィンターゲート：サイクルタイム、サイクルタイム、大事なことなので2回（略
・富の源泉2010年末特別編：ムーアの呪いとの闘い
・不連続都市伝説シリーズ：ホワイトカラーの生産性はもっと上げられる
