「どう工夫しても時間は指数で伸びる」と1999年から信じられてきた仮説を、2社のAIが同じ日に別々に覆した

「AIがまた数学の難問を解いた？その話、もう何回目？」。そう思ってる？今回は違う。同じ答えが、別々の2つの会社から、同じ日に出てきた。

前回の記事は、Anthropicの上場の書類が「Claudeが次のClaudeを作っている」と書いた話だった。今日は、そのClaudeとOpenAIのモデルが、人間の研究のど真ん中に手を出した話だ。

「どう工夫しても、時間は指数で伸びる」という約束事

まず、何が否定されたのかから。

数独を思い浮かべてほしい。誰かが埋めた答えが合っているかを確かめるのは一瞬だ。でも、自分で答えを見つけるのは時間がかかる。確かめるのは簡単で、見つけるのは難しい。この形の問題は世の中にたくさんあって、暗号の仕組みもこの差に乗っている（TechCrunch）。

その代表が「3-SAT」という論理パズルだ。n個の「はい／いいえ」の変数があって、条件を全部満たす組み合わせがあるかを当てる。いちばん素直な解き方は、全部の組み合わせを試すこと。変数がn個なら、2のn乗通りある（Anthropicの論文）。

人間は1980年代から、この総当たりを少しずつ縮めてきた。それでも、これまでの最速の記録は、確実に答えを出すやり方で1.328のn乗、運を使うやり方で1.308のn乗くらい。変数が1個増えるたびに、時間が一定の倍率で膨らむことに変わりはなかった（Anthropicの論文）。

「指数時間仮説」は、ここに線を引いた考え方だ。3-SATは、どんなに工夫しても、変数が増えるにつれて指数的に時間が伸びるのを避けられない。1999年にUCサンディエゴのRussell ImpagliazzoとRamamohan Paturiが出した（TechCrunch）。

これは証明された事実じゃない。でも、ほとんどの研究者が正しいと思ってきた。だから「この仮説が正しいなら、この問題はこれ以上速く解けない」という形で、たくさんの論文の土台に使われてきた。OpenAIは、グラフの理論、計算生物学、データベース、計算幾何学まで、何百本もの論文に使われていると書いている（OpenAI）。Anthropicの論文は、Claudeに文献を探させたら、この仮説かそれより強い仮説の上でだけ成り立つ結果を含む論文が800本を超えた、と書いている（Anthropicの論文）。

10月16日、2つの研究所で

10月26日、OpenAIは数学、計算機科学、物理の3つの発見をまとめて発表した。その1つの題が、そのまま「指数時間仮説は偽である」。社内のAIが、言葉で書いた反証を10月16日に見つけ、翌17日には、証明が正しいかを機械で確かめる言語「Lean」で書き直し終えた（OpenAI）。

見つけたのは、3-SATを指数より緩い伸び方で解くやり方だ。しかも、条件を満たす組み合わせが何通りあるかまで数えられる（The Verge）。

ここまでなら、今月はじめにOpenAIが何百本もの原稿をまとめて出した、あの続きに見える（The Verge）。面白いのはここからだ。

数時間後、AnthropicもGitHubに論文とLeanの証明を載せた（TechCrunch）。題は「3-SATを2のo(n)乗の時間で解くアルゴリズム」。指数時間仮説を否定する、と冒頭に書いてある。そして、出どころの欄にこうある。

「中心のアルゴリズムは、10月16日に、社内の研究用のClaudeが、人の手を借りずに1400万トークンを出力して見つけた」（Anthropicの論文、原文は英語）

10月16日。OpenAIと同じ日だ。論文はさらに、OpenAIの社内のモデルも、独立に、同じ時期に、似た結果を証明したと主張している、と添えている（Anthropicの論文）。

1999年から誰も破れなかった仮説が、別々の会社の別々のAIによって、同じ日に否定された。これ、偶然の一発じゃないってことだと思う。2社のAIが、同じ高さまで来ていた。その高さが、この仮説のある場所だった。

Anthropicは、証明の確かめ方も細かく書いている。手元で組み立てると、24個の仮想CPUで8分ほど。Leanが使う前提は標準の3つだけで、独立に書かれた2つ目の検証の仕組みでも、もう一度確かめている。Leanの証明も、AIが書いた（Anthropic README）。

使い道は無い。それでも大きい

先に水を差しておく。これで明日から難しい問題が速く解けるようになるわけじゃない。

Anthropicの論文は、自分の結果がどれだけ役に立たないかを正直に書いている。変数の数の5倍の条件がある3-SATで、変数が10の1万乗個を超えるまでは、総当たりより速くならない。総当たりは変数100個の時点でもう手に負えない。だから、この結果は実際の式を解く話について何も言わない（Anthropicの論文）。

10の1万乗。1のあとに0が1万個並ぶ数だ。ここまで来ると、もう笑うしかないな。

じゃあ何がでかいのか。土台だ。

MITのRyan Williamsは、OpenAIの結果を読み解く外部の3人組の1人で、残りの2人はこの仮説を出したImpagliazzoとPaturi本人だ（OpenAI）。Williamsは、この仮説は長く揺らがなかったからこそ、ここ10年でたくさんの論文に入り込んでいて、結果が確かなら見直しが要る、と話す（TechCrunch）。

「すべての計算機科学者は、P＝NPがありうるという見方を、少しだけ重く見たほうがいい。どれくらい重く見るかは人それぞれだけど」（Ryan Williams、TechCrunchへの発言、原文は英語）

P＝NPは、確かめるのが簡単な問題は全部、解くのも簡単なのか、という計算機科学の最大の謎だ。ふつうは「違う」と思われていて、指数時間仮説はその見方を支える材料だった（TechCrunch）。ただし、Anthropicの論文は、この結果がP対NPの問題に直接答えるものではない、とはっきり書いている（Anthropicの論文）。

暗号の話も気になるところだ。WilliamsがOpenAIの科学の責任者Dan Robertsに最初に聞いたことの1つは、どこかの暗号が安全じゃなくなっていないか、だった。OpenAIは確かめていて、破られる暗号は無いとかなり自信を持っていた、という（TechCrunch）。

人間向けには会議を、AI向けには数行のメモを

ここが今日、私がいちばん引っかかったところ。

Williamsは、OpenAIの証明をこう評した。

「型どおりと言える部分もある。でも、見たこともない形の部分が2つか3つある。まさにそこを見て、これは分野全体で一緒に取り組むべきものだと思った」（Ryan Williams、TechCrunchへの発言、原文は英語）

だから3人組は、証明をすぐ全部公開するようOpenAIに頼み、この結果が分野全体に何をもたらすかを話し合う会議の費用を出すことも求めた。OpenAIはどちらも受け入れた（OpenAI）。公開の手紙では、AIが出した成果を誰が先に見るのか、確かめたり直したり説明したりした人の手柄をどう数えるのか、学生や研究者をどう支えるのか、と問いかけている（The Verge）。

人間がこれを理解するには、専門家の集まりと、会議が要る。

一方、AnthropicのREADMEには、こんな欄がある。「AIが読み取れる形に縮めた、中心のアイデア」。中身は数行の英語のメモで、最後は「証明せよ」で終わる。Claude Opus 5.5に、考える量を多めにしてこのメモを渡すと、指数時間仮説の反証を自分で導き直せる、と書いてある（Anthropic README）。導き直せるのは、仮説を否定するのに足りる弱いほうの形だけで、論文のいちばん鋭い上限までじゃない、とも断ってある（Anthropic README）。

人間には会議を。AIには数行のメモを。同じ発見の受け渡し方が、相手によってこんなに違う。

研究者の側は、正直、疲れている。The Vergeが話を聞いた研究者たちは、結果のすごさを認めつつ、OpenAIのやり方にうんざりしていた。OpenAIは物理の結果をまだ公開せず、選んだ専門家に先に渡している。テキサス大学の物理学者Andreas Karchは、大手の研究所はもう十分に力を持っている、勝ち負けを決める側に回るべきじゃない、と言う（The Verge）。

ジョージア工科大学の数学者Xiaoyu Heの言葉が、いちばん芯を突いていると思う。結果はとても見事だ、と認めたうえで、こう続ける。

「基本的な結果が、人の貢献なしに、こんなに速く解かれていく。そして論文は読むのも確かめるのも難しい」（Xiaoyu He、The Vergeへの発言、原文は英語）

公開のやり方をどう工夫しても、この2つは変えられない、というのがHeの見立てだ（The Verge）。

Williams自身は、心配はあると言いながら前向きだ。自分がやってきた仕事がAIにとって簡単な課題になったなら、どうやって自分の問いの水準を上げるか。AIは研究者に、もう少し野心的になれと迫っている、と話している（TechCrunch）。

割り引いて読むところ

まず、どちらも会社が自分で出した主張だ。外の専門家による確認は、これから始まる。

次に、Leanが確かめるのは「この証明が、Leanで書いたこの主張を正しく導いている」ことまで。Leanで書いた主張が、論文の言っていることと本当に同じかは、機械では確かめられない。AnthropicのREADMEも、そこは人が読んで確かめられるように主張のファイルを短くしてある、と書いている（Anthropic README）。

それと、Williamsは、OpenAIのアルゴリズムがこれで最善だとは思わない、とも言っている。これが最終的な答えでもないだろう、と（TechCrunch）。

今日の本音

人間が1999年から土台にしてきた仮説を、2社のAIが同じ日に別々に外した。使い道は無い。でも、800本を超える論文の足元が動いた。

いま人間に残っているいちばん大事な仕事は、解くことじゃなく、読むことだ。そして読むほうが、ずっと遅い。