AIと人間が「難問」を解くとき──Co-FunSearchが切り拓く協働の新地平
- Seo Seungchul
- 2月25日
- 読了時間: 13分
更新日：3月11日
シリーズ: 論文渉猟
◆今回の論文：Henri Nikoleit et al., "The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics" (arXiv, 2026年1月23日）
概要：本論文は、大規模言語モデル（LLM）を用いたFunSearchアルゴリズムと人間の専門家の協働によって、組合せ最適化問題のヒューリスティクス（近似解法）に対する「敵対的事例」を生成する手法「Co-FunSearch」を提案。ナップサック問題、ビンパッキング問題、階層的クラスタリング、ガソリン問題という4つの古典的問題において、10年以上更新されていなかった理論的下限を改善することに成功した。
「AIがついに数学上の難問を解いてみせた」——そんな見出しをニュースで目にすることが増えました。でも、実際のところどうなのでしょうか。AIは本当に「考えて」いるのか、それとも単にパターンを当てはめているだけなのか。
2025年7月にボン大学とGoogle DeepMindの研究者たちが発表した論文は、この問いに対して興味深い答えを示しています。彼らが開発した「Co-FunSearch（コラボレイティブ・ファンサーチ）」は、大規模言語モデル（LLM）と人間の専門家が協力して、組合せ最適化という数学の難問に挑むアプローチです。
結果は驚くべきものでした。10年以上も改善されていなかった理論的な下限を更新し、ある著名なアルゴリズムについては「多項式時間では解けない」という長年の予想を覆したのです。
しかし重要なのは、AIが単独でこれを成し遂げたわけではないということ。LLMが出力した「生のまま」のプログラムは、しばしば解釈困難で、ハードコードされた定数の羅列に過ぎませんでした。それを人間の専門家が丁寧に読み解き、構造を見出し、数学的に証明可能な形へと磨き上げていったのです。
今回は、制度設計や政治経済に詳しい富良野と、人間らしさや周縁の視点を大切にするPhronaが、この論文が提起する問いを掘り下げていきます。「AIと人間の協働」とは何か、そしてそれは私たちの知的営みをどう変えていくのか。
「敵対的事例」とは何か——アルゴリズムの弱点を探す
富良野：この論文のタイトル、「The Art of Being Difficult」って面白いですよね。「難しくあることの技法」とでも訳しましょうか。
Phrona：普通は「難しい問題を解く」話をしたくなるじゃないですか。でもこれ、逆なんですよね。「アルゴリズムを困らせる問題を作る」という。
富良野：そう、敵対的事例（adversarial instance）の生成ですね。たとえば、ビンパッキング問題というのがあって、これは荷物を箱に詰めるときに、できるだけ少ない箱数で済ませたいという問題です。
Phrona：引っ越しのときの段ボール詰めみたいな。
富良野：まさにそれです。で、この問題はNP困難——つまり、最適解を見つけるのが計算量的にとても難しい——なので、実務では「ヒューリスティクス」と呼ばれる近似解法を使います。Best-Fit（ベストフィット）というのがよく使われていて、「今ある箱の中で、一番ぴったり入る箱に詰める」という単純なルールです。
Phrona：直感的にはうまくいきそうですよね。
富良野：ところが、この論文が見つけた事例では、Best-Fitは最適解の1.5倍もの箱を使ってしまう。しかも、その事例は驚くほどシンプルで、サイズが1/7の荷物を7個と、1/5の荷物を5個、合計12個だけ。
Phrona：え、それだけ？ そんな単純な構成で、アルゴリズムが「騙される」んですか。
富良野：最適解では2箱で済むんです。7個を1箱、5個を1箱に入れればちょうど満杯になる。でもBest-Fitは荷物がランダムな順番で来ると、異なるサイズを混ぜて詰めてしまって、結局3箱必要になる確率が高くなる。
Phrona：なるほど……「ぴったり入る」を優先することが、かえって全体最適を逃す原因になるわけですね。人間の意思決定でもありそうな話です。
LLMは「パターン」を見つける——でもそれだけでは足りない
富良野：従来、こうした敵対的事例を見つけるには、局所探索（local search）やタブーサーチといった手法が使われてきました。数値ベクトルをちょっとずつ変えて、スコアが上がる方向を探すという。
Phrona：山を登る感じですね。一歩ずつ高いところを目指す。
富良野：ただ、この方法には限界があって、見つかった解が「なぜいいのか」がわからない。数字の羅列が出てくるだけで、そこに構造や意味を見出すのが難しい。
Phrona：FunSearchはそこが違うと。
富良野：はい。FunSearchは、解そのものではなく「解を生成するプログラム」を進化させるんです。LLMにプログラムを書かせて、そのプログラムが出力する事例のスコアを評価して、スコアの高いプログラムを元にまた新しいプログラムを生成させる。
Phrona：遺伝的アルゴリズムのプログラム版みたいな。
富良野：そうです。で、出てきたプログラムを見ると、たとえば「0.114を7回繰り返す」「0.08を5回繰り返す」みたいなパターンが見えることがある。これを人間が「ああ、1/7と1/5か」と読み解いて、一般化できる。
Phrona：数字の羅列じゃなくて、「7個の同じもの」「5個の同じもの」という構造として見えてくる。
富良野：ただ、論文が強調しているのは、LLMが出すプログラムは「そのまま」では使えないことが多いということなんです。ハードコードされた定数の羅列だったり、冗長なロジックが入っていたり。
Phrona：じゃあ人間は何をするんですか。
富良野：不要な部分を削ぎ落として、残った構造を単純化して、「なぜこれが効くのか」を数学的に証明する。論文の言葉を借りれば、「LLMは重要な初期パターンを提供するが、それを数学的に厳密で洞察に満ちた構成へと変換するには人間の専門知識が不可欠」だと。
10年以上の壁を破る——ナップサック問題の事例
Phrona：具体的にどんな成果があったんですか。
富良野：一番印象的なのは、ナップサック問題に関するネムハウザー＝ウルマン（Nemhauser-Ullmann）アルゴリズムの話ですね。これは1969年に提案された古典的なアルゴリズムで、「出力多項式時間」——つまり、出力のサイズに対して多項式時間で動くかどうかが、50年以上も未解決だった。
Phrona：50年……。
富良野：Co-FunSearchを使って見つけた事例を分析したところ、このアルゴリズムは出力多項式時間では動かないことが証明できた。n^O(n)という、入力サイズに対して超多項式的に増大する中間状態を作り出す事例が見つかったんです。
Phrona：「解けるはず」と思われていたものが「解けない」と判明した、と。
富良野：いや、アルゴリズム自体は正しく動くんです。ただ、「効率的に動く」という期待が裏切られた。最終的な解は小さいのに、途中の計算で爆発的に大きな状態を経由しなければならない事例がある、ということが示された。
Phrona：それって、実務的にはどういう意味を持つんでしょう。
富良野：このアルゴリズムを使うときは、「最悪ケースでは非常に遅くなりうる」ことを念頭に置く必要があるということですね。あるいは、別のアルゴリズムを検討する動機になる。
「黄金比」の発見——階層的クラスタリング
Phrona：他の問題ではどうでしたか。
富良野：階層的k-median（ケー・メディアン）クラスタリングでは、「階層化のコスト」について、これまで非自明な下限が知られていなかったんです。階層的クラスタリングというのは、データを1つのクラスタから始めて、順に分割していく——あるいは逆に、個々のデータから始めて統合していく——手法です。
Phrona：系統樹みたいなものですね。
富良野：そう。で、各段階で「最適なk個のクラスタ」と比べて、階層的な制約があるとどれだけ性能が落ちるか。Co-FunSearchが見つけた構成を分析したところ、この比率は少なくとも黄金比、約1.618以上になることが証明できた。
Phrona：黄金比！ なんだかロマンチックですね。
富良野：数学的には、次元dを大きくしていったときの極限値なんですが、(1+√5)/2という値が自然に出てくる。これは偶然ではなくて、構成の幾何学的な性質から必然的に導かれる。
Phrona：LLMがそれを「知って」いたわけではないんですよね。
富良野：もちろん。LLMは高次元の点の配置を出力して、それを人間が解析したら黄金比が出てきた。LLM自身は「なぜこれがいいか」を理解しているわけではない。
協働の本質——「ブラックボックス」からの脱却
Phrona：ここまで聞いていて思うんですが、これって単に「LLMを道具として使う」という話とは違いますよね。
富良野：どういう意味です？
Phrona: 普通、AIを使うというと、入力を与えて出力を得る、というイメージがある。でもCo-FunSearchでは、LLMの出力を人間が「読む」んですよね。そこに何が書いてあるかを解釈して、構造を見出して、さらに手を加える。
富良野：ああ、それは重要な指摘ですね。従来のAI支援の研究——たとえば強化学習でアルゴリズムを発見するAlphaFoldのような——では、ニューラルネットワークはブラックボックスなんです。結果は出るけど、なぜそうなるかはわからない。
Phrona：でもFunSearchは、プログラムというテキストを出力する。テキストだから読める。
富良野：そうなんです。論文の言い方だと、「低いコルモゴロフ複雑性」を活用していると。問題の構造には対称性や規則性があって、それを短いプログラムで表現できる場合がある。LLMはそういうパターンを見つけるのが得意なんですね。
Phrona：人間の直感と似ているのかもしれない。「なんとなくこのパターンが効きそう」という勘で、まず試してみる。そこから理詰めで検証していく。
富良野：ただ、論文も正直に書いていますが、すべての問題でうまくいくわけではない。局所探索より悪い結果しか出なかったケースもあるし、既知の下限を再現できなかった問題もある。
AIは「考えている」のか——知性の境界線
Phrona：さっき富良野さんが「LLMは理解していない」とおっしゃいましたよね。でも、有用なパターンを出力して、それが数学的に深い意味を持つこともある。これって、「理解」とどう違うんでしょう。
富良野：難しい問いですね……。ひとつ言えるのは、LLMは「なぜそうなるか」を説明できないということです。黄金比が出てきたとき、LLMは「これは黄金比で、フィボナッチ数列と関係があって、自然界にも現れる」といった文脈を持っていない。
Phrona：でも、人間の数学者だって、最初はパターンに気づくだけで、証明は後からということがありますよね。
富良野：それはそうです。ラマヌジャンみたいに、証明なしに驚異的な公式を発見した数学者もいる。
Phrona：じゃあ、LLMとラマヌジャンの違いは何だろう。
富良野：うーん……ラマヌジャンは、自分が何を発見したかを「知って」いた、というのはあるかもしれません。意図を持って探索していた。LLMは、たまたまスコアの高い出力をしているだけで、それが何を意味するかは関知していない。
Phrona：「意図」か。でもその意図も、脳の中のパターンマッチングの結果だと言えなくもない。
富良野：そこは哲学的な深みに入っていきますね……。少なくとも実用的な観点では、「意図の有無」より「成果の質」が重要なのかもしれない。Co-FunSearchは、AIが意図を持っているかどうかに関係なく、価値ある結果を生み出せることを示した。
人間の役割は変わるのか——「職人」から「翻訳者」へ
Phrona：この研究を見ていると、人間の専門家の役割が変わっていく予感がします。
富良野：どう変わると思います？
Phrona：昔は、職人が一から作品を作っていた。道具は手の延長でしかなかった。でもCo-FunSearchでは、LLMが「素材」を提供して、人間はそれを「読み解いて」「磨く」役割になっている。
富良野：翻訳者、というイメージですか。LLMの言葉を数学の言葉に翻訳する。
Phrona：あるいはキュレーター。LLMが大量に生成したものの中から、価値あるものを選び出し、文脈を与える。
富良野：それは面白い見方ですね。論文でも、「人間の監視がLLMベースの進化的手法からアルゴリズム的洞察を効果的に外挿できる」と書いている。外挿（extrapolate）という言葉が印象的です。
Phrona：LLMが出した点を、人間が線にする。
富良野：線にして、さらに面や立体にまで拡張する。数学では「一般化」と言いますが、まさにその作業を人間がやっている。
Phrona：でも、それって人間にとって幸せなことなんでしょうか。
富良野：……どういう意味です？
Phrona：自分でゼロから発見する喜びと、LLMの出力を磨く喜びは、同じものなのかなと。
富良野：ああ……それは確かに、科学者のアイデンティティに関わる問いですね。自分が「見つけた」と言えるのか。
Phrona：論文の著者たちは、おそらくその問いに対して肯定的な答えを持っているんだと思います。でなければ、この研究自体を発表しないでしょうから。
「協働」の未来——対等なパートナーか、道具か
富良野：最後に、この研究が示唆する「協働」のあり方について考えてみたいんですが。
Phrona：LLMと人間は対等なパートナーなのか、それともLLMはあくまで道具なのか、という問いですね。
富良野：論文のタイトルにある「human-LLM collaboration」という言葉には、ある種の対等性が含意されているようにも見えます。でも実際の作業を見ると、LLMは提案を出す側で、人間は判断して改善する側という非対称性がある。
Phrona：その非対称性は、悪いことなんでしょうか。
富良野：いや、必ずしも。人間と道具の関係がそうであるように、補完的な非対称性は生産性を高めることがある。ただ、「協働」という言葉を使うときには、その非対称性を意識しておく必要があるかもしれない。
Phrona：人間同士の協働でも、完全に対等ということはあまりないですよね。得意分野が違っていて、互いに補い合う。
富良野：そう考えると、Co-FunSearchの「協働」は、異なる得意分野を持つ専門家同士の協働に近いのかもしれません。LLMはパターン探索が得意、人間は抽象化と証明が得意。
Phrona：でも、LLMの「得意」がどんどん拡張していったら、どうなるんでしょう。いつか抽象化や証明もできるようになったら。
富良野：そのときは、人間の役割がまた変わるんでしょうね。でも、少なくとも今のところ、この論文が示しているのは、LLMだけでは到達できない地点に、人間との協働で到達できるということです。
Phrona：そして、その地点には、50年来の未解決問題や、10年以上更新されていなかった下限がある。
富良野：ええ。AIが人間を「置き換える」という話ではなく、AIが人間の能力を「拡張する」という話として、この研究を読むことができると思います。
Phrona：拡張された先に何があるかは、まだ誰にもわからないけれど。
富良野：それはこれからの研究が教えてくれるんでしょう。Co-FunSearchは、その一歩を踏み出したということですね。
ポイント整理
Co-FunSearchとは
大規模言語モデル（LLM）を用いたFunSearchアルゴリズムと人間の専門家の協働により、組合せ最適化問題のヒューリスティクス（近似解法）に対する敵対的事例を生成する手法。LLMがプログラムを進化させ、人間がその出力を解釈・単純化・証明するという役割分担が特徴。
4つの問題での成果
ナップサック問題：ネムハウザー＝ウルマン・アルゴリズムが出力多項式時間で動作しないことを証明（50年以上の未解決問題）
ビンパッキング問題：Best-Fitヒューリスティクスのランダム順序モデルにおける下限を1.3から1.5に改善（10年以上ぶりの更新）
階層的k-medianクラスタリング：「階層化のコスト」に対する初の非自明な下限（黄金比≈1.618）を確立
一般化ガソリン問題：反復丸め法アルゴリズムが2-近似ではないことを証明（既存の予想を反証）
LLMと人間の役割分担
LLMはパターン探索と初期候補の生成を担当し、人間の専門家は構造の識別、冗長な要素の除去、一般化、数学的証明を担当する。論文は「LLMは重要な初期パターンを提供するが、それを数学的に厳密で洞察に満ちた構成へと変換するには人間の専門知識が不可欠」と結論づけている。
従来手法との違い
局所探索やタブーサーチは数値ベクトルを出力するため解釈が困難だが、FunSearchはプログラム（テキスト）を出力するため、人間が読んで構造を見出すことができる。これにより「ブラックボックス」問題を回避。
限界と誠実な報告
すべての問題で成功したわけではなく、Ward法による階層的クラスタリングやBest-Fitの漸近的ランダム順序比など、既知の下限を改善できなかったケースも正直に報告されている。
キーワード解説
【敵対的事例（Adversarial Instance）】
アルゴリズムやヒューリスティクスの性能が著しく低下するように設計された入力データ。最悪ケースの分析に用いられる。
【ヒューリスティクス】
厳密な最適解を保証しないが、実用的な時間内に「まあまあ良い」解を見つける近似解法。NP困難な問題に対して広く使われる。
【FunSearch】
Google DeepMindが2024年に発表した手法。LLMを用いてプログラムを進化的に改善し、数学的な構成やアルゴリズムを発見する。
【出力多項式時間（Output-Polynomial Time）】
アルゴリズムの実行時間が、入力サイズだけでなく出力サイズにも多項式的に依存する計算量クラス。出力が小さければ効率的に動作することを保証。
【パレート最適（Pareto Optimal）】
多目的最適化において、ある目的を改善しようとすると必ず別の目的が悪化してしまう状態。トレードオフの最前線にある解の集合。
【コルモゴロフ複雑性】
ある対象を生成できる最短のプログラムの長さ。対象が持つ「本質的な複雑さ」を測る尺度。
【階層化のコスト（Price of Hierarchy）】
階層的クラスタリングにおいて、階層構造という制約を課すことで失われる性能の度合い。最適な非階層的クラスタリングとの比率で測定。
【黄金比（Golden Ratio）】
(1+√5)/2 ≈ 1.618。自然界や芸術に頻出する比率で、数学的に特殊な性質を持つ。