昨日の論文と著者によるコメントテキストについて書いてみます。論文は次のプレプリントです。
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs](https://arxiv.org/html/2610.06783v1) written by Josh Alman（Columbia University）／Virginia Vassilevska Williams（MIT）arXiv:2610.06783v1、2026年10月5日公開
タイトルの意味は、「疎で非対称なグラフの三角形を利用して、3SUM問題を真に二乗時間未満で、APSP問題を真に三乗時間未満で解く方法」です。この論文は、長年破ることができなかった計算時間の壁を、わずかながら超えるアルゴリズムを提示しています。3SUM問題というのは、 与えられた n 個の整数の中に、足して「０」になる3つの数の組み合わせがあるかを判定する問題で判定に要する計算量は O(n²)（二次時間）となるアルゴリズムしか発見されていませんでした。また全対最短経路問題 (APSP)というのは、グラフ上のすべての頂点（ｎ個あるとします）間の最短距離を求める問題で計算量は O(n³)（三次時間）となるアルゴリズムしか発見できていませんでした。これらの計算量の壁は破ることができないという仮説が提唱されていたのですが、今回の論文でその予想は誤っていることが反例で示されたというのが画期的なのだそうです。それぞれO(n1.9992)や(O(n2.9995）とわずかに計算量が減るだけですが、計算量の壁が存在しないことが示されたことにより、たとえばこれまで「3SUMやAPSPがこれ以上速くならないなら、この問題も速くならない」と証明されていた数多くの関連問題（幾何学問題や文字列処理など）の限界が一斉に崩れ、新しい高速なアルゴリズム開発のドミノ倒し（研究ラッシュ）を引き起こす引き金となっているようです。
今年、Anthropic社の研究者が、暗号理論に関する数学的問題を未公開の社内用最新AIモデルClaudeに調べさせていました。本来の目的は、ある暗号方式の理論的な性質を検証し、改善することでしたが、Claudeは、途中で関連するアルゴリズムの研究に進み、結果として3SUMやAPSPに関する長年の仮説を覆す手法を発見したということです。この成果を多分論文にしようと考えたのでしょう（そこのところははっきりしません）、Anthropic社がVirginia Williamsさんに連絡をとり、彼女らがAIがあたえた証明を精査して書き直し、不要な部分を取り去り、証明の整理と改良をおこなって引用文献もつけて専門家が読める論文として公開したというのがこの研究の流れです。
このAIの論文を受け取って読んだ時、彼女は腹がたったとコメントの方に書いています。彼女らの未発表の研究ノート（2023年のもの）に記していた方針をAIがつきすすめてこの新アルゴリズムを見つけたことがわかったからです。このノートが盗み読まれたというのではありません。彼女らの研究方針をそのまますすめておれば、AIと同じ結論にAIよりはやく達していたはずだと思ったから腹がたったのです。彼女らはAIを殆ど使っておらず、最近の論文をみて使い始めたところだったそうです。もし未発表の研究のまとめの文書をAIにあたえていたら、多分1時間の公開版Claudeの使用でこの成果を自分たちが得ることができたはずだと述べています。それを確かめるため、彼女らは二種類のLLMに彼女らの未発表の研究ノートをアップロードした場合と、アップロードしなかった場合を比較するという実験を行いました。彼女らの未発表データを与えた場合にだけ、公開LLMは新アルゴリズムを発見できることが確認されました。与えない場合は、計算量の壁はこえられないという予想のほうが正しいのではないか、とAIが回答してきた場合もあるそうです。どのようなプロンプトをつかって実験したかや使ったLLMなど詳しいことは、昨日紹介した彼女のコメントのテキストファイルをご覧ください。ということで、未発表のデータや、前に試してうまくいかなかった手法やアイデアも、最新のLLMにあたえてみると、うまくいくことがあるという例が今回紹介した論文でした。
最後に、今回この論文とVirginiaさんによるコメントについてChatGPTとチャットした際の、ChatGPTの意見を以下にペースとしておきますので参考にしてください。今後のAIと研究者が協働するやりかたについてのChatGPTの意見です。また、この意見の中でChatGPTが数学研究と生命科学研究の違いについて深く理解しているのも注目すべき点だと思いました。数学や物理の人が生命科学について理路整然と説明されると、それが正しいと信じ込んでしまう場合をよくみかけます。しかし理屈がとおっていても生命はそのようになっていないことがあるというのが、生命科学をやっているものが体験的に理解している事実です。そのへんのところの警告をChatGPTが述べているのが「すごいな」と思いました。
今回の事例から考える、科学研究におけるLLMの実践的な利用
ここからは著者のコメントそのものではなく、そこから私（野村注：ChatGPTのことです）が考える研究上の教訓です。
LLMは「優秀な助手」から「研究上の仮説を探索するシステム」へ変わりつつある
これまで研究におけるLLMの典型的な用途は、論文の要約、文献検索、プログラム作成、英語の校正、統計解析の補助などでした。
今回の事例では、これらを超えた役割を果たしています。
LLM自身が、与えられた研究課題から別の問題に進み、新しいアルゴリズムを見つけたのです。
ただし、現段階では二つの使い方を区別することが重要だと思います。
知識を整理するLLM
既存の文献やデータを要約し、問題の背景を理解するために使います。情報の正確性と出典の確認が重要です。
未知の解法を探索するLLM
仮説、失敗したアプローチ、関連論文を与え、新しい解法や説明を探索します。得られた結果については、独立した検証が不可欠です。
今回のClaudeによる成果は、後者の使い方が、少なくとも一部の数学的問題において高度な研究成果に到達できることを示しています。
科学愛好家や研究者が試せる実用的な方法
今回のWilliams教授の比較実験を参考に、LLMを研究的な課題に使う場合の手順を考えてみます。
最初に、自分で問題を定義します。何を明らかにしたいのか、すでに何が分かっているのか、何が未解決なのかを具体的に記述します。次に、関連する原著論文や、自分自身のアイデア、試行錯誤の記録を与えます。
そのうえで、例えば次のように指示します。
『添付した資料に基づいて、未解決の問題に対する新しい解法または仮説を検討してください。
特に、研究ノートに記載された未完成のアイデアが、参考論文に示された方法と組み合わせられる可能性を検討してください。
以下を区別して報告してください。
- 既存の文献から確実に言えること
- 新しい推論によって得られた可能性
- 論理的な飛躍や未検証の部分
- 仮説を支持または否定するために必要な検証
資料にない研究成果を実在するものとして引用しないでください。結論が得られない場合は、どこで行き詰まったのかを具体的に説明してください。』
数学なら独立した証明や形式的検証、実験科学なら既存データによる再解析、独立したデータや実験による検証が重要になります。
さらに、今回の教授のように、研究ノートを与えた場合と与えない場合の比較も有益です。このようにすると、LLMの応答から新しいアイデアを取り出すだけでなく、その発想のどの部分が人間の研究者の知識に依存しているのかを調べることができます。
科学的な発見を目的とする場合には、利用したモデル、プロンプト、参照資料、実行条件、試行回数などを記録しておくことも重要でしょう。
数学と実験科学には重要な違いがある
最後に、今回の事例を生命科学や物理学にそのまま当てはめる場合の注意点を挙げておきます。
数学の定理であれば、正しい証明が得られれば、原則としてその結果を確立できます。
さらにLeanのような形式的証明支援システムを利用すれば、論理的な誤りの危険性を大幅に減らせます。
しかし、実験科学では状況が違います。
LLMがどれほど合理的な仮説を提示しても、それが自然界で成立するとは限りません。例えば、ある遺伝子発現変化が特定の生理現象の原因であるという説明は、既存の分子生物学の知識と完全に整合していても、実験によって否定される可能性があります。
したがって、実験科学におけるLLMの役割は、少なくとも現時点では、仮説の発見、既存の知識の統合、実験結果の解釈支援などに位置づけるのが適切でしょう。
LLMによる論理的な整合性の確認は、実験による実証の代わりにはなりません。
まとめと考察
今回の論文と著者のコメントには、二つの重要なメッセージが含まれていると思います。
第一に、LLMが、人間の研究者が長年解決できなかった数学的問題に対して、新しいアルゴリズムを発見する段階に到達したということです。
2026年6月には、ChatGPTによって最初に発見された証明を人間の研究者が検証・改良した、別の理論計算機科学の論文も発表されています。Williams教授自身、この論文に触れて、LLMを研究に利用し始めたきっかけになったと説明しています。
Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH
第二に、より重要かもしれないのは、新しい発見に至るまでの人間とAIの関係が、従来考えられていたほど単純ではないということです。
今回の成果を、単に「AIが人間より優秀だった」と理解するのは適切ではないでしょう。
同じ方向の着想は人間の研究者が何年も前に持っていました。一方、その着想を実際に数学的な成果に結びつけたのはAIでした。そして、その成果を理解できる形に整理し、他の問題への応用を明らかにしたのは人間の研究者でした。
この三つはいずれも重要な知的活動です。
Williams教授は、LLMによって科学研究がどう変わるかを断言していません。むしろ、その不確実性を率直に認めています。
特に、AIが多くの研究者の知識を取り込みながら新しい結果を発見する時代に、研究成果の功績を誰に帰属させるべきかという問いには、まだ十分な答えがありません。
私は、今回のコメントで最も重要なのは、教授が未完成の研究ノートを使った比較実験を公開した点だと思います。
人間の研究者が持っていたアイデアを与えるとAIは解けた。しかし、それを与えなければ解けなかった。この小さな実験は、科学研究における人間とLLMの協働について、非常に具体的な示唆を与えています。
これからの研究者に求められる能力は、問題を自分一人で最後まで解く能力だけではなく、重要な問題を見つけ、有望な着想を育て、LLMの探索能力を活用し、その結果の正しさと科学的意義を判断する能力へと広がっていくのかもしれません。
そして、そのような時代には、成功した研究の記録と同じくらい、未完成の着想や失敗した試行錯誤の記録も、将来の発見につながる貴重な知的資産になる可能性があります。
この論文は、計算機科学の成果であると同時に、科学における発見、理解、独創性、そして研究者の役割について考えるための、重要な事例だと思います。
Fromの部分に細工がしてあって国税庁などの語を登録しても迷惑メールフィルタをすりぬけられるようになっていました。
