📡 Signal｜OpenAI、指数時間仮説の反証を Lean 検証付きで公開

OpenAI は10月26日、社内の AI モデルが数学・計算機科学・物理の 3 分野で新しい結果を出したと発表した。計算機科学の結果は、計算量理論で広く正しいと信じられてきた「指数時間仮説 (ETH)」が偽だとする証明で、形式証明の言語 Lean による検証とともに GitHub で公開された。

ETH は数百本の論文が「この問題はこれ以上速くは解けない」と示すための前提に使ってきた仮説だ。証明が専門家の検証に耐えれば、計算の限界を描いた地図の一部が描き直される。OpenAI は結果の解釈を外部の研究者グループに委ねる手順もあわせて示した。

第一報は27日の 速報 で伝えた。本稿は OpenAI の発表文と公開された証明から、3 つの結果の中身と公開の手順を拾う。

ETH とは何か、反証はどこまで届くか

ETH は、論理式の充足可能性問題 (3-SAT) を解くには、変数の数に対して指数関数的な時間がどうしてもかかるという予想だ。1999年に Russell Impagliazzo 氏と Ramamohan Paturi 氏が定式化した。P ≠ NP より強い主張で、発表文によればグラフ理論・計算生物学・データベース・計算幾何などで「条件付きの計算困難性」を導く前提として、数百本の論文に使われてきた。

OpenAI のシステムが自然言語で反証を見つけたのは10月16日、Lean での形式化は翌17日だ。発表文は、反証によって「これらの作業がどこまで速くなりうるか」という問いが開き直されるとしつつ、実際に速いアルゴリズムを見つけて実用の改善につなげるには「相当なさらなる研究が要る」とも書いている。

Lean で検証済みということは、証明の論理の筋道に穴がないことを機械が確かめたという意味だ。一方で、形式化された命題が ETH そのものを正しく表しているかの確認は、人間の専門家の仕事として残る。

暗号資産の読者が気にする点にも触れておく。ビットコインやイーサリアムの署名の安全性は、楕円曲線上の離散対数問題の難しさに依っており、ETH を前提にしていない。反証が直ちに既存の署名方式を破るわけではない。

数学と物理の 2 つの結果

数学の結果は、波が一点に集まる度合いについての Sogge の局所平滑化予想 (1991年) を、すべての次元で証明したとするものだ。発表文によると、これで掛谷予想と Stein の制限予想もすべての次元で解決する。2019年に Guth・Wang・Zhang の 3 氏が 2 次元の場合を、2025年に Wang・Zahl の両氏が掛谷予想の 3 次元の場合を証明していた。AI の出力は10月18日、Lean での形式化は翌19日に得られた。

物理の結果は、量子色力学 (QCD) と、標準模型を統一的に完成させた理論を含む 4 次元の場の量子論が、数学的に厳密な意味で存在することの証明だ。部分問題として、クレイ数学研究所のミレニアム懸賞問題の一部である純粋な Yang–Mills 理論の存在証明も含む。Yang–Mills の存在の自然言語の証明は 9月9日、QCD は 9月18日に出ており、Yang–Mills 部分の Lean での形式化は10月16日に終わった。

3 つの結果で、公開の仕方を変えた

OpenAI は外部の専門家に「羊飼い (shepherd)」の役を頼み、その助言に沿って結果ごとに公開の仕方を変えた。

• 数学 — AI の出力をそのまま公開し、解説は研究者が自由に組織する
• 計算機科学 — Impagliazzo 氏・Paturi 氏 (ともに UC San Diego) と Ryan Williams 氏 (MIT) が率いるグループが検証と解説を担い、自然言語の証明と Lean の証明は即日公開
• 物理 — 2004年ノーベル物理学賞の David Gross 氏が率いるグループに委ね、AI の生成物の公開は見送ってグループ自身が論文を書く

協力には 4 つの原則がある。秘密保持契約を結ばないこと、OpenAI が社内モデルの発見に学術上の功績を求めないこと、解説を書いたグループが評価を受けること、参加は任意かつ無報酬で結論は各自のものであることだ。計算機科学のグループの求めに応じ、OpenAI は結果の生データをすべて公開し、この結果の意味を議論する学会に資金を出すと約束した。

ETH を定式化した当人たちが、AI の反証を検証する側に回った。AI が先に答えを出し、人間が後から意味と正しさを確かめる。研究の順番が入れ替わり始めたことを、OpenAI は公開の手順の設計として示した。

次に見るもの

確認先は、Impagliazzo 氏らのグループが呼びかけた ETH 反証の公開の検証だ。GitHub の openai/math リポジトリにある自然言語の証明 (10月25日付) と Lean の証明を、計算量理論の研究者がどう読むか。OpenAI が資金を出すと約束した学会の日程の発表が、検証の進み具合を測る最初の目安になる。

ことば

• 指数時間仮説 (ETH) — 3-SAT は変数の数に対して指数関数的な時間をかけないと解けない、という計算量理論の予想。多くの問題の「これ以上速くならない」という結論の前提に使われてきたため、反証されると各分野の下限の議論が見直しになる。
• Lean — 数学の証明をコンピュータが一行ずつ検査できる形で書くための言語と証明支援系。AI が出した長い証明の論理の正しさを、人間の査読より先に機械で確かめる道具として使われ始めている。
• ミレニアム懸賞問題 — クレイ数学研究所が2000年に選んだ 7 つの未解決問題。Yang–Mills 理論の存在と質量ギャップはその一つで、今回の物理の結果はその前半の「存在」に関わる。

🔗 一次ソース

• OpenAI「Working with academic communities to build scientific understanding」(10月26日) — 3 つの結果、発見と Lean 形式化の日付、検証グループの顔ぶれ、協力の 4 原則を確認openai.com
• OpenAI の自然言語の証明「The Exponential Time Hypothesis is False」(GitHub・10月25日付・PDF)GitHub
• ETH 反証の Lean の証明 (GitHub openai/math)GitHub
• 局所平滑化予想の自然言語の証明 (GitHub・10月25日付・PDF)GitHub