2026.03.06

コンピューターサイエンスの父が驚愕｜AIが1時間で解いたグラフ理論の難問と垣間見えた知性

「AIは数学ができない」——そう信じていたのは、コンピューター科学の礎を築いた当の本人でした。2026年2月28日、スタンフォード大学のウェブサイトに5ページの論文が静かに公開されました。著者はドナルド・クヌース、88歳。その冒頭を飾った一文は「Shock! Shock!（衝撃！衝撃！）」[1]。数学論文らしからぬ感情的な叫びが、世界中の研究者の目を引きました。

「Shock! Shock!」——88歳の巨人が漏らした言葉

コンピューター科学の礎を築いた人物の、数週間の格闘

クヌースは1962年から大著『The Art of Computer Programming（TAOCP）』を書き続けるチューリング賞受賞者であり、現代のアルゴリズム理論の基盤を作った人物です[1]。その彼が、次に執筆する巻の中で取り上げようとしていたグラフ理論の問題に数週間行き詰まっていました。問題を平易に言えば「三次元の格子状空間で、全ての点を過不足なく一度ずつ通る三本の巨大ループを、どんなサイズの格子でも作れるか」という構成問題です。クヌース自身は最小ケース（縦横高さが3の格子）では解いており、同僚のフィリップ・スタッパースも具体的なサイズ4から16まで計算機で確認していましたが、「奇数サイズ全てに通用する一般的な作り方」は誰にも見えていませんでした[1]。

ChatGPTへの懐疑から、Claudeへの驚嘆へ

クヌースはAIに対して以前から慎重な評価を持っていました。2023年4月、ChatGPTに20の問題を与える実験を行い、その結果を「フェイクを学習するためのタスクを研究した（studying the task of how to fake it）」と評しています[1]。スティーブン・ウルフラムへの書簡でも「これは断じて私向きではない（emphatically not for me）」と述べていました。それから3年後、同じ人物が「生成AIに対する意見をそのうち改めなければならないようだ」と書いたのです。この劇的な認識の変化こそ、今回の出来事の重みを示しています。

31回の失敗が導いた、一つの答え

問題を「解く」前に「組み替える」

クヌースの同僚スタッパースが問題文をそのままAnthropic社のモデル「Claude Opus 4.6」に渡すと、約1時間・31回の探索を経て答えが出ました[1]。特筆すべきは「即座に正解を導いた」のではなく、問題の捉え方そのものを最初に組み替えていったことです。Claudeはまず問題を「群論（数の対称性を扱う数学分野）のカイリー有向グラフ」として再解釈しました。次に線形・二次の関数による簡便な解法を試みましたが失敗、続いてコンピューターによる力業の探索（深さ優先探索）も計算量が膨大になりすぎて断念します[2]。クヌースはこのプロセスを論文の中で「かなり感心した（quite admirable）」と評しています[1]。

探索25番目の自己宣言と、探索30番目の転回

その後も試行は続き、統計的最適化手法（焼きなまし法）を使って個別の解を見つけることには成功しました。しかし探索25番目の段階で、Claudeは自ら「この方法は解を見つけられるが、一般的な構成則は与えられない。純粋な数学が必要だ」と記録しています[3]。そして探索30番目、過去の焼きなまし法で得た特定の解を振り返ったとき、ある規則性に気づきます。格子空間を「合計値が同じ点の集まり（ファイバー）」に分けて観察すると、各層での選択が一つの座標だけに依存していたのです。この洞察が探索31番目での決定的な構成法につながり、奇数サイズ全てで完璧な分解を生み出すプログラムが完成しました[1]。スタッパースが奇数サイズ3から101まで全て検証し、クヌースに報告。クヌースはその後、自ら厳密な数学的証明を書き上げています。

AIが垣間見せた知性の正体

失敗を捨てない記憶という武器

今回の出来事から見えてくるのは、「瞬時に正解を出す」とは異なる知性の形です。Claudeは特別なひらめきで解いたのではなく、31回の試行それぞれを記録として保持し続け、後の探索で再利用することで答えに近づきました。探索30番目での気づきは、10回以上前の試みを振り返ることで生まれた発見であり、文脈を持続的に保持できる仕組みなしには起きえないプロセスといえます。また、Claudeが「蛇行パターン（serpentine）」と名付けた構造が、数学的に「m進法グレイコード」という既知の概念と一致していたことをクヌースは発見しており、AIが既存の数学的知識と問題構造を自律的に結びつけた点も特筆されています[1]。

「発見」と「証明」——人とAIの役割分担

ただし、今回の成果には重要な留保があります。Claudeが見つけたのはあくまで「構成法（こういう手順で作ればよいというパターン）」であり、「なぜ正しいか」を示す厳密な証明はクヌース自身が書きました[2]。また、偶数サイズの問題については行き詰まり、最終的にはプログラムを正しく動かすことさえできなくなっています[3]。さらに、セッション中にスタッパースが繰り返し「進捗を必ずメモに記録してから次へ進め」と指示し直す必要があり、ランダムなエラーによる再起動も発生しました[1]。人とAIがそれぞれ「発見」と「証明」を分担した、新しい研究の形がここにあります。

さいごに

論文の末尾でクヌースは、情報理論の祖クロード・シャノンへの追悼を重ねてこう記しています。「クロード・シャノンの精神も、彼の名が今日の進歩と関連付けられていることを誇りに思っているだろう」[1]。AIモデルの名「Claude」と伝説の科学者の名が重なる、クヌースらしい言葉遊びです。

60年以上アルゴリズムの最前線に立ち続けた人物が「意見を改めなければならない」と感じた出来事は、ビジネスの現場にも深い示唆を与えます。AIは「即答する検索エンジン」ではなく、「失敗を積み上げながら問いを組み替え続けるパートナー」として設計することで初めて真価を発揮します。あなたのチームにおけるAI活用の設計を、今一度見直すきっかけとして、この事例をぜひ参考にしてみてください。