AIが30年越しのグラフ理論予想の反例を発見

AIが長年のグラフ理論の主張に挑戦

30年にわたって未解決だったグラフ理論の予想が、AIシステムが数時間で反例を生成したことで崩れたと報じられている。New Scientistによれば、AIスタートアップAutokernelの共同創業者であるDmitry Rybinは、ChatGPT 5.6 Proを使って、Dinitz-Garg-Goemans予想に対する構造的な反例を探した。この予想は、組合せ論と最適化における未解決問題として数十年にわたり残っていた。

同誌の報道では、Rybinが使ったプロンプトは合計4回、60語未満で、モデルは約5.5時間探索したのち、この予想が偽であることを示す構成を返したという。もしこの反例が専門家の精査に耐えれば、この出来事は急速に進む流れの中でのもう一つの注目すべき瞬間となる。AIシステムは、ルーチンな証明作業や記号操作を助けるだけでなく、既知の数学的問題の地位を変える新しい対象を次々と見つけ始めている。

この変化が重要なのは、反例が数学の中で特別な位置を占めるからだ。定理は多くの特殊例で何年も検証に耐えうるが、たった一つの有効な例外があれば一般主張は崩れる。小さな例におけるパターンから直観が築かれている分野では、規則を破る最初の対象を見つけるのは驚くほど難しいことがある。まさに、大規模な自動探索が強みを発揮しうるタイプの探索問題だ。

その予想は何を言おうとしていたのか

Dinitz-Garg-Goemans予想は、頂点と辺からなるネットワークを研究するグラフ理論に属する。New Scientistはこの主張を物流の比喩で説明している。倉庫から複数の配送先へ荷物が出ていく場面を考えてほしい。ある問題の形では、荷物はより小さな部分に分けて独立に経路設定できる。この予想は、この柔軟な設定を、荷物を分割できない別の配置に変換しても、総コストを増やさずに済むはずだと提案していた。

この種の主張が魅力的なのは、現実世界の厄介な最適化問題が、より明快で解析しやすい形に還元できる場合があることを示唆するからだ。もし真であれば、この予想は分割可能な流れと分割不可能な流れの間に信頼できる橋を与えていたはずだ。だが、報告された反例は、その橋が常に存在するわけではないことを示している。これらのネットワーク構造のどこかに、分割を禁じることで経済性が実際に変わるケースがあり、予想はそれを否定していた。

専門家にとって、これは分野全体が崩壊するという意味ではない。むしろ、最前線がより鮮明になるということだ。研究者は今や、予想がどこで破綻するのか、制限付きの版本はなお成り立つのか、どの種類のグラフが望ましい性質を保つのかを問える。誤った予想は、広いが不正確な原理をより正確な地図に置き換えさせるため、真の予想と同じくらい生産的な仕事を生み出すことが多い。

なぜこの件が注目されるのか

反応の一因は、プロンプトの見かけ上の単純さにある。RybinはNew Scientistが引用したX上の発言で、自分でもこの問題を何週間も考え続けていたと述べている。しかし記事で説明されたプロンプトは非常に最小限だった。最初に画期的な反例を見つけるよう指示し、その後は探索を続けるよう繰り返し求めただけだった。この対比が物語の中心になっている。注目されているのはAIが関与したことだけではなく、ユーザー向けの見た目はごく普通なのに、背後の計算探索は非自明なことをしていたかもしれない点だ。

この区別は重要だ。短いプロンプトだからといって、推論過程が単純だったことにはならない。むしろ、密度の高い形式的ワークフローを手作業で組まなくても、有用な探索へシステムを向かわせられたということを意味する。AIツールが進化するにつれ、ボトルネックは各手順を細かく指定することから、適切な数学的目標を定め、出力を厳密に検証し、機械が生み出した対象を研究コミュニティが確認し発展させられる形に翻訳することへ移っていくかもしれない。

New Scientistはまた、AIが長年の予想を覆したとされるのは1週間で2回目だと指摘している。記事は今回のグラフ理論の結果を、以前のAI生成によるJacobian予想の反例と並べ、さらにOpenAIのモデルが5月にPaul Erdosによる数十年越しの予想を打ち破ったとされる件にも触れている。こうした出来事を総合すると、今の時代は一過性の珍事ではなく、機械支援数学の広範な加速の一部だと示唆される。

なぜグラフ理論は特に驚きに弱いのか

ヨーク大学のChris Bowman-ScargillはNew Scientistに対し、数学には「グラフ理論の予想はすべて偽だ」というお決まりの冗談があると語った。このユーモアは、実際の構造的な難しさを反映している。グラフ理論では、小さな例で安定して見える振る舞いが、頂点を1つか2つ加えただけで急変することがある。そのため、低次元の例がより大きな構造を忠実に映しやすい分野に比べると、非公式なパターン認識の信頼性は低い。

この環境では、自動化システムは自然に有用だ。人間が気軽に目視する範囲を超えて、ケースを大規模に列挙し、一見して直感的ではない奇妙な構成を探せる。数学者はある主張が真であるべき理由について優れた概念的感覚を持っているかもしれないが、機械はその直観が、より奇妙な空間の隅々でも生き残るかどうかを容赦なく試せる。

おそらく教訓は、数学者が不要になるということではない。むしろ役割が変わるのだ。どの問題が重要かを決め、構成の意義を評価し、それが機能する構造的理由を見つけ、生の計算出力を堅牢な数学的物語へと変えるのは、今でも人間だ。しかし探索の風景は変わりつつある。機械が決定的な例をより速く、より頻繁に提示できるようになれば、予想を立てる行為そのものがより規律的で、より対抗的になり、研究者はアイデアの初期段階からより厳しい機械検証を想定するようになるだろう。

これから何が起きるか

当面の焦点は検証だ。主張された反例が、専門家によってその対象が正確な形式条件のもとで本当に予想に反していると確認されて初めて、数学的記録は変わる。New Scientistはこの結果を大きな進展として示しているが、長期的な重要性は、学界がそれをどう検証し、解釈し、拡張するかにかかっている。

もし結果が維持されれば、多くの研究者がすでに吸収しようと苦心している流れを強めることになる。AIは、特に探索空間が大きく、成功条件が明確な領域で、助手から発見の協働者へと移行している。数学は、出力を原理的に精密に検証できるため、特に目に見えやすい試金石だ。そのため、他の多くの知的分野よりも、誇張と実質を切り分けやすい。

それでも社会的な影響は、単一の予想を超えて大きいかもしれない。数学者の一世代は今、自然言語で指示され、何時間も動き、人間が構成を思いつかなかった対象を返すシステムから、価値ある洞察が生まれる可能性に向き合っている。それが不安を生むにせよ、高揚を生むにせよ、その両方であれ、発見がどのように起こるかに関する重要な変化を示している。

この記事はNew Scientistの報道に基づいています。元記事を読む。