- Anthropicのモデル Claude Opus 4.6 が、Donald Knuthが数週間にわたって研究していた 有向ハミルトン巡回分解問題 を解決
- 問題は、(m^3) 個の頂点を持つ有向グラフの 3つのハミルトン巡回への分解 を見つけることであり、Claudeはこれを 奇数の m について完全に解決
- Claudeは 「ファイバー分解」、3D蛇行型 (serpentine) パターン、深さ優先探索 (DFS)、シミュレーテッドアニーリング など、さまざまな探索戦略を段階的に実行
- 最終的に Pythonプログラムの形の一般解 を導き出し、Filip Stappersが m=3から101までの奇数 m について検証して完全な分解を確認
- Knuthはこの結果を 自動推論と創造的問題解決における画期的な進展 と評価し、偶数 m の場合はいまだ未解決 であることを明記
問題の背景と定義
- 研究テーマは 有向ハミルトン巡回 (directed Hamiltonian cycles) に関するもので、Knuthの著書 The Art of Computer Programming の今後の巻に収録予定
- グラフは (m^3) 個の頂点 (ijk) から構成され、各頂点には3本の辺が存在: (i+jk), (ij+k), (ijk+)
- 目標は、すべての (m>2) について、これらの辺を 3つの有向 (m^3)-巡回に分解 する一般解を見つけること
Claudeの探索過程
- Claude Opus 4.6はAnthropicの ハイブリッド推論 (hybrid reasoning) モデルで、Filip Stappersが問題を提示し、進行過程を文書化するよう指示
- 初期段階でClaudeは問題を 関数グラフと順列割り当て問題 として再定義し、線形および二次関数型アプローチを試みたが失敗
- その後、DFS探索、2D蛇行型パターン分析、3D Grayコードベースのパターン などを順に試行
- ファイバー分解 アプローチを導入し、(s = (i+j+k) \mod m) を基準とする層状構造を分析し、シミュレーテッドアニーリング (SA) によって部分解を発見
解法の発見と検証
- 探索31段階目でClaudeは、ファイバーごとの単一座標依存ルール を用いたPythonプログラムを生成
- このプログラムは m=3,5,7,9,11 で完全な3つのハミルトン巡回を生成
- Filip Stappersはこれを m=3〜101のすべての奇数 m についてテストし、完全な分解を確認
- KnuthはこれをCコードに簡略化して提示し、各巡回が実際に 長さ (m^3) であることを数学的に証明
一般化と数学的分析
- (m=3) のハミルトン巡回の一部が すべての奇数 m に対して一般化可能 であることを確認
- (m=3) では11,502個の巡回のうち1,012個が (m=5) に一般化され、996個は (m=7) まで一般化
- この996個は すべての奇数 m>1 に対して一般化可能
- Claude-like 分解は、i, j, s の境界値 (0 または m−1) のみに依存する単純なルールとして定義
- 定理: Claude-like 分解がすべての奇数 m>1 で有効であるためには、m=3 における3つの巡回が一般化可能なハミルトン巡回 でなければならない
- 計算の結果、760個の Claude-like 分解 がすべての奇数 m で有効
偶数 m の未解決性と結論
- 偶数 m の場合は依然として 未解決 (open) の状態
- (m=2) は不可能であることが既存研究で証明済み
- Claudeは (m=4,6,8) で部分解を見つけたが一般化には失敗
- Claudeは偶数 m の探索中にエラーや異常動作を示し、探索は中断
- Knuthはこれを AIベースの自動推論における歴史的成果 と評価し、Claude Shannonの名にふさわしい進歩 だと言及
付録: 他の2つの巡回のルール
- 2番目の巡回 (c=1):
- (s=0) なら j を増加、(0<s<m−1) なら i を増加、(s=m−1) のとき i>0 なら k を増加、i=0 なら j を増加
- 3番目の巡回 (c=2):
- (s=0) で j<m−1 なら i を増加、j=m−1 なら k を増加
- (0<s<m−1) で i<m−1 なら k を増加、i=m−1 なら j を増加
- (s=m−1) なら i を増加
- 各巡回の s=0 における頂点順序 が明示されており、これによって巡回全体の構造を証明可能
1件のコメント
Hacker Newsのコメント
RLのスケーラビリティが適用可能な問題領域を考えると興味深い
以前は人間の認知に依存するしかなかったが、今ではこうしたパターンが確率分布の中に溶け込んでいて、誰でもアクセス可能になっている
ただ、科学の境界が拡張し続けるとき、モデルがそれに追いつけるのかは疑問
2030年にAnthropicがClaudeを最新の状態に保つには、(a) 固定モデルの継続学習か (b) 継続訓練が必要になるだろうが、どちらも簡単ではない
知識カットオフ時点以降は、その時点に永遠にとどまることになる
研究者に無料推論を提供する代わりに、その思考過程(trace) を学習データとして使うモデルも想像できる
Qwen3-next、Qwen3.5、Nemotron 3 Nanoのようなモデルは、ハイブリッドアテンションでメモリコストを抑えつつ、100万トークンウィンドウをサポートしている
人間の検証、コード実行、検索によるリアルタイムのフィードバックループがモデル学習信号として機能している
半分冗談だが、まったくありえない話でもない
昔あったWolframとKnuthのGPT-4対話を思い出す
Knuthは当時は懐疑的だったが、最近のOpus 4.6のようなモデルを見て態度が和らいだようだ
新しい証拠に応じて考えを変える姿勢は素晴らしい
関連する対話はこちらで見られる
科学的思考の核心でもある
Knuthの文章の導入部にはやや誤解を招く余地があると感じる
まるでClaudeが問題を直接解いたように見えるが、実際にはClaudeが例を作り、Knuthがそれを一般化して証明にしたという形
LLMは方向設定には弱いが、いったん方向が与えられると深い探索は得意
放っておくと見当違いな方向へ行くが、人がリードすれば素晴らしいパートナーになる
Claudeは問題の核心に切り込む役割を果たしていて、人間はそれを磨き上げただけだ
証明の整理は副次的な作業にすぎない
Claudeが偶数ケースで止まったという部分が興味深い
おそらくclaude.aiかclaude codeのどちらかを使ったのだろうが、コンテキスト超過(dumb zone) に入ったようだ
Copilotのようにコンテキスト使用率グラフを表示して、ユーザーが認識できるようにすれば有用そう
Arthur C. Clarkeが有名にしたペントミノパズルをClaudeに解かせてみた
64ビット整数でボードとピースを表現するようC#プログラムを作らせたところ、素早く解けたが、20x3ケースでは誤ったマッピングにより誤答を出した
人間がしそうなミスで興味深い
要するに、Knuthが問題を提示し、友人がClaudeで30回あまり探索を行った
Claudeが奇数ケースを解くPythonプログラムを作り、Knuthがそのアプローチを証明した
偶数ケースは依然として未解決問題のまま残っている
実際にはClaudeがしばしば止まったり誤りを出したりするので、人間がときどきリマインドしてやる程度だった
核心となるアイデアが誰から出たのかははっきりしない
今は未解決問題を扱うのが本当に楽しい時代
10年前の研究をClaudeと一緒に再探究してみたくなる
LLMの強みは3つあるように見える: 膨大な知識、接続する能力、疲れを知らない試行錯誤
この3つが合わさると、ときどき驚くような結果が出る
もしかするとP≠NPの証明も、人間が見落としているかすかなつながりの中にあるのかもしれない
LLMはその中の一つの構成要素にすぎない
他の条件が同じなら、これが決定的な差になる
完全に新しいつながりを作るのはまだ難しい
「LLMは次の単語を予測する機械にすぎない」という言い方が本当に正しいのか疑問
だとすれば、こうした問題解決はどう説明できるのだろうか。これが「思考」なのか?
「最も確率の高い単語」という表現は、あまりに単純化された説明だ
結局のところ「次に起こることをうまく予測する能力」そのものが、知能の定義なのかもしれない
RLHFのおかげで、単なる予測ではなく役に立つ回答をするよう報酬が与えられる
その結果、「delve」のような表現が過剰に頻出する
関連内容はAI SIGNS文書を参照
LLMはその分布を学習している
それを単純化して揶揄するのは、技術の本質を見落とす態度だ
Knuth本人の報告書とは興味深い
LLMの助けなしで自分で読んで理解する時間だ