メインコンテンツへスキップ
見出し画像

AIは計算機科学の「常識」を覆したのか~25年信じられてきた指数時間仮説に、二つのAIが反証を主張した~

    最近、Rishabh Karnawat(@rishabhkio)さんのX投稿を読みました。MITのRyan Williamsさんのスレッドを引用し、OpenAIの社内モデルが指数時間仮説(ETH)の反証を主張した件を、専門外の人にもわかる言葉で説明した投稿です。

    面白いのは、AIが難問に答えを出したという点だけではありません。仮説を提唱した研究者を含む3人が、コミュニティによる検証の取りまとめ役に回り、「私たちの関与はお墨付きではない」と書いたところです。

    この記事は、投稿を手始めに、ETHとは何か、主張が正しければ何が揺らぎ何は揺らがないのか、「Leanで検査済み」は何を保証するのか、の順で整理します。

    2026年10月28日の時点で、二つの反証はどちらもコミュニティの検証中です。この記事では「反証された」とは書かず、「反証を主張」「各社がLeanで検査したと書く」と書き分けます。

    【発端】 同じ壁に、二つのAIが別々に反証を主張

    画像
    Anthropicの論文は「独立かつ同時に」と書く。両社ともLeanで検査したと主張している

    これは一社の発表ではなく、二社が同じ時期に同じ結論を主張している話です。OpenAIの主張については、検証の枠組みが公開で作られています。

    OpenAIは2026年10月26日の発表で、自社のシステムがETHは偽だと証明し、Leanで検証したと書きました。

    自然言語の反証は10月16日、Leanの形式化は10月17日です。OpenAIの発表にあります。

    Anthropicも、研究用のClaudeモデルが2^{o(n)}時間の3-SATアルゴリズムを見つけ、Lean 4で形式化したと主張しています。核になる発見は同じ10月16日で、出力は1,400万トークン、人の入力はなかったと書きます。

    論文は「独立かつ同時に」OpenAIのモデルも同様の結果を主張していると述べています。Anthropicの論文とLeanで読めます。

    【基礎】 3-SATは「倍々に増える組み合わせ」の問題

    画像
    ETHは約25年前にImpagliazzoとPaturiがZaneと提唱した仮説。証明はされていない

    ETHは「スイッチが増えれば、どんな工夫でも時間は指数的に増え続ける」という仮説です。

    3-SATは、はい・いいえのスイッチがたくさんあり、「このスイッチはこう並べてはいけない」という規則が並んだパズルです。全部の規則を満たす並べ方を探します。

    総当たりなら、スイッチが1つ増えるたびに候補が倍になります。10個なら1,024通り、20個なら約100万通りです。

    投稿は、数百個で宇宙の年齢でも足りなくなると説明しています。

    ETHは約25年前にImpagliazzoとPaturiがZaneと提唱しました。n個のスイッチの3-SATを最悪の場合に解くには、2^{Ω(n)}の時間が要るという主張です。

    投稿はETHを「自然法則」と言い換えていますが、これは投稿の表現です。ETHは証明されていない仮説です。

    Anthropicの論文によれば、Williamsさんは2019年に、ETHが真である見込みを70%と見積もっていました。

    【違い】 揺らぐのは下界の足場、P vs NPの解決とは別

    画像
    洗い直しが必要になるのは理論の地図。手元のソルバーが速くなるかは別の問い

    洗い直しが必要になるのは理論の地図です。手元のソルバーが速くなるかどうかは、別の問いです。

    これまで、多くの論文が「ETHを仮定すれば、この問題はこれ以上速くならない」という形の結果を示してきました。条件付き下界と呼びます。

    Williamsさんは「何百本」と書き、Anthropicの文献調査はETHかそれを含意する仮説の下でだけ成り立つ論文を800本超と数えています。

    主張が正しければ、そのどれが本当の壁で、どれが探すのをやめた場所だったかを調べ直すことになります。

    ETH前提の下界

    • 主張が正しいとき:足場が揺らぎ、洗い直しが必要

    • それでも変わらないこと:別の仮説からも出る下界は残りうる

    実用の速さ

    • 主張が正しいとき:結果は漸近的

    • それでも変わらないこと:実際に式を解く話ではない

    P vs NP

    • 主張が正しいとき:直接は関わらない

    • それでも変わらないこと:解けたわけではない

    NP全体

    • 主張が正しいとき:3-SATの数え上げが準指数時間

    • それでも変わらないこと:一般の帰着では移らず、全問題が速くなるとは言えない

    実用面の数字は慎重に読んでください。Anthropicの論文は、節の数が5nの3-CNFでは、nが10の10,000乗を超えるまで総当たりの2^nより良くならないと書きます。

    総当たりはn=100ですでに非現実的なので、改善は実用の場面に現れません。

    一方でWilliamsさんは、実用のSATソルバーへの影響を「まだわからない」と答え、12か月以内に大きな更新がありうるとも、ないかもしれないとも述べています。OpenAIも、実用化には相当な追加研究が要ると書いています。

    【仕組み】 Leanが検査するのは証明、読むのは人

    画像
    検証は二層。機械の層と人の層が、別の問いに答える

    検証は二層です。機械が証明の正しさを見て、人が主張の中身を読みます。

    Leanは、証明を機械的に検査する道具です。AnthropicのREADMEは、使う公理がLean標準の3つで、Comparatorと独立に書かれた第二のカーネルで再検査すると書いています。

    ただし同じREADMEが、「主張を書いたファイルが論文の言っていることを言っているか」は機械が確かめない、と明記しています。だからそのファイルは短く、読者が自分で確かめられるようにしてあります。

    Williamsさんの返信に、この点に通じるやりとりがあります。「本当に確か?」と尋ねたら「Leanで検証した」と返ってきたので、「わかった、でも本当に確か?」と聞いた、という話です。

    検証の体制も公開されています。OpenAIの発表は、検証グループの参加者にNDAを求めず、参加は無報酬だと書いています。

    グループはOpenAIに、生データ(PDFとLeanのソース)の公開と会議の資金提供を求め、OpenAIは両方に同意したと発表は書きます。

    書簡には「お墨付きと受け取られるべきではない」とあります。書簡で全文を読めます。

    OpenAI側のリポジトリにも慎重さの手がかりがあり、原稿は721本で、上位の結果の約42%がLeanで形式化済みです。

    形式化のないものには誤りがありうると書かれ、10月7日には符号の誤りで3本を取り下げた記録もあります。

    【具体例】 同じ下界でも、足場が一本の論文と二本の論文

    画像
    最長共通部分列と正規表現マッチングは、OVCからも下界が出る

    「ETHが崩れた」の影響は、下界ごとに足場の数で変わります。

    OpenAIの論文は、最長共通部分列と正規表現マッチングの下界を例に挙げています。この二つはOrthogonal Vectors予想(OVC)からも出るので、ETHが崩れても残りうるとのことです。

    一方、ETHかその仲間の仮説だけを足場にした結果は、足場を失います。Anthropicの調査が数えた800本超は、OVCのように今回の反証の対象にならない仮説でも証明できる結果を除いた数です。

    たとえば「ETHを仮定すれば、この問題は速くならない」と書かれた論文に出会ったとします。その結果が他の仮説からも導けるなら影響は小さく、ETHだけが頼りなら再点検の対象になります。

    これはこの記事の整理で、各論文の個別の判定ではありません。

    【関連概念】 残る仮説と、AI成果の扱い方

    ETHの周りには、反証の対象になった仮説、残る仮説、そして人間側の決め事があります。

    • 反証の対象:OpenAIの論文はETH、SETH、Gap-ETH、NSETHを反証すると書く

    • 残る仮説:OVCは今回の反証の対象外(Anthropicの論文はOVCを反証しないと書く)

    • 数え上げ:両社とも、解の有無ではなく解の個数を数える#SAT型のアルゴリズム

    • 回路下界:主張が正しければ、E^NPは線形サイズの回路を持たない(Williamsさんの定理6.1)

    もう一つの論点が、AIが出す成果の扱い方です。書簡は、早期アクセスの公平さ、利益相反の開示、検証や説明の仕事へのクレジット、学生と研究者の支援を、これから話し合う問いとして挙げています。

    参考情報・参考書籍(PR)

    本記事をより深く理解するために、概念マップスライドを作成しました。こちらをみることで理解の補助になるはずです。

    Michael Sipserの『計算理論の基礎 [原著第3版] 3.複雑さの理論』は、PやNP、NP完全性を扱う教科書の邦訳です。3-SATとETHの背景にある、複雑さの理論を順に学べます。

    井上亜星さんの『ゼロから始めるLean言語入門』は、自然数と整数をLeanで作りながら、Leanが何を検査するのかを小さな例で知る入門書です。記事で扱う「Leanが検査するのは証明」の話の助けになります。

    関連記事

    【まとめ】 「仮定すれば」の前提を確かめる一歩

    画像
    今日からできる最初の一歩

    今日からできる最初の一歩は、「〇〇を仮定すれば」と書かれた主張を見たとき、その〇〇を確かめることです。

    何を仮定しているのか。証明されているのか、別の仮説からも同じ結論が出るのか。

    OVCの例のように、足場の数で重みが変わります。

    次に、AIが出した証明を見たら、検査済みかどうかに加えて、「何を主張しているか」を人が読みます。Anthropicのように主張のファイルが短く公開されていれば、そこから読めます。

    進み具合は、公開の議論ページとOpenAIの原稿一覧で追えます。確定した結論と、まだ可能性にすぎない話を分けて読むのが、この件の付き合い方です。

    参考情報

     
     
    海外でバズった最新テック関連情報をわかりやすく整理します! スキの数やページビューが多いなどの反響が多いものがあれば、実際の環境で操作した結果や手順などを共有する記事も作成したいとも思ってます! とりあえずこれを見ておけばディープな最新情報もキャッチアップ!できるものを目指します

    あなたへのおすすめ