ドナルド・クヌース、Claude Opus 4.6が未解決の組合せ論問題を解いた過程を論文として公開
(www-cs-faculty.stanford.edu)要点
- 『The Art of Computer Programming（TAOCP）』の著者である計算機科学者ドナルド・クヌースが、最新AIモデル「Claude Opus 4.6」が自身が数週間研究していた未解決の組合せ論問題を解いたと発表しました。
- 有向グラフのハミルトンサイクル分解を求める問題で、Claudeは31回のPythonスクリプト実行と自己フィードバックループを通じて、動作する一般化アルゴリズムの構造を発見しました。
- これまで生成AIの限界を指摘し懐疑的だったクヌースは、今回の結果を「自動推論と創造的な問題解決における劇的な進歩」と評価し、AIに対する従来の見方を改める考えを示しました。
詳細分析
解決した問題：ハミルトンサイクル分解（Hamiltonian Cycle Decomposition）
クヌースはTAOCPの次巻を執筆する中で、特定の有向グラフ（digraph）における分解問題を研究していました。頂点 $0 \le i, j, k < m$ に対して、$m^3$ 個の頂点 $ijk$ を持つグラフで、各頂点は $i+jk$、$ij+k$、$ijk+$（ただし $i+ = (i+1) \bmod m$）へ向かう3本の弧（arcs）を持ちます。目標は、$m > 2$ のすべての場合について、これらの弧を3つの有向 $m^3$-サイクルに分解する一般解（general decomposition）を見つけることでした。クヌースは $m=3$ の場合は解決していましたが、それ以上の一般化公式の導出には苦戦していました。
実装原理と技術的背景：ハイブリッド推論と自律探索ループ
クヌースの同僚であるFilip Stappersは、Anthropicの最新ハイブリッド推論モデル「Claude Opus 4.6」にこの問題を入力しました。このとき、単純な問い合わせを超えて、エージェント的なワークフローを強制する強力な制約条件をプロンプトとして与えていました。
Claudeはただちに問題を数学的に再定義し、Pythonスクリプト（exploreXX.py）を書いて仮説検証ループを開始しました。約1時間にわたり、ブルートフォース、ファイバー分解（fiber decompositions）、シミュレーテッドアニーリング（Simulated Annealing）など多様なアルゴリズムを試し、31回の探索を行いました。
問題解決の核心となった転換点
特に25回目の探索で、Claudeは「シミュレーテッドアニーリングのアルゴリズムは個別の解を見つけることはできても、一般的な数学的構成（general construction）を示すことはできないため、純粋数学的なアプローチが必要だ」と自ら限界を分析し、探索の方向を切り替えました。最終的に31回目の探索で、過去の探索に見られた構造的パターンをもとに、$m$ が奇数のときに動作する正確な一般化構造を導き出しました。クヌースはこの結果をもとに数学的証明を完成させ、これを「Claude型分解（Claude-like decompositions）」と名付けました。
主なコードとデータ
Filip StappersがClaudeに与えた中核的な制約条件（プロンプト）と、Claudeが記録した自己評価ログの一部です。
# 1. Claudeに課されたワークフロー制約（ループ制御と文書化の強制）
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. Claudeによる数学的問題の再定義（初期アプローチ）
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. 25回目の探索後のClaudeの自己評価（方向転換）
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
10件のコメント
教科書に載っている人が、また教科書にいろいろ付け加えているね……。
（認定）
まあ、その人の役割は教科書を書くことだからね（うなずき）
wwwwww これからはAIでどんどん追加されそうですね
TAOCP、まだ続いていたんだな
数学の問題を解くためにAIを使う方法をそのまま共有し、自作のTeXで論文まで執筆……めちゃくちゃイケてる。
この記事のおかげで TAOCP を初めて知ったので、一度ゆっくり読んでみようと思います。
TAOCP の次巻を執筆しているんですね
ということは、このシリーズはまだ続きそうですね、うおおおお
まだご存命だったんですか？
今でも訂正なさっている方……