AI Lab、理論計算機科学分野のトップカンファレンス「FOCS 2025」にて論文採択

「E𝑘-SAT遷移問題」における漸近的に最適な近似の限界を明らかに

AI ｜2025年10月17日

株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人ならびに国立情報学研究所の平原秀一准教授による論文が、理論計算機科学分野のトップカンファレンス「66th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2025、以下FOCS）」※1にて採択されたことをお知らせいたします。

「FOCS」は世界中の研究者達によって開催される国際会議で、「ACM Symposium on Theory of Computing (STOC)」※2と並び理論計算機科学分野における最高峰の国際会議です。
1960年から開催されている歴史ある国際会議であり、現代の理論計算機科学の基礎を築く画期的な概念や定理が数多く提唱・証明されてきました。例えば1994年のFOCSではPeter Shorが素因数分解を効率的に解く量子アルゴリズムを発表し、1989年のFOCSでは戸田誠之助がゲーデル賞を受賞した「戸田の定理」を発表するなど、世界的に重要な成果発表の場となっています。

このたび採択された論文は、2025年12月にオーストラリアのシドニーで開催される「FOCS 2025」で発表予定です。

■採択された論文について

「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、今回採択された論文は、理論計算機科学分野の基礎研究に該当しています。

「Asymptotically Optimal Inapproximability of E𝑘-SAT Reconfiguration」
著者：平原秀一（国立情報学研究所）・大坂直人（サイバーエージェント AI Lab）

「組合せ遷移」は、AIや大規模システムがある「最適な状態」から別の「最適な状態」へ移行可能かどうかをアルゴリズム理論・計算量理論の観点から明らかにする研究領域です。この度採択された論文では、最も基礎的な「E𝑘-SAT遷移問題」について、どれだけ正確な答えにたどり着けるか（近似可能性）を調査しました。この問題は、過去にAI Labから国際会議「STACS 2023・STOC 2024」で発表した研究結果から、𝑘=3の時に近似のPSPACE困難性が判明していました。しかし、𝑘の値が大きくなったときの傾向、すなわち𝑘の値が無限大に近づいたときの振る舞い（漸近的な挙動）は知られていませんでした。

本研究では、E𝑘-SAT遷移問題の(1−1/(𝑘-1)−1/𝑘)-近似が多項式時間で可能な一方、(1−1/10𝑘)-近似がPSPACE困難であることを証明し、漸近的に最適な近似可能性を解明しました。この結果は、E𝑘-SAT遷移問題の「NP版」であり(1−1/2^𝑘) -近似の最適性が証明されている「E𝑘-SAT問題」と比較すると、E𝑘-SAT遷移問題の方がより近似が難しいことを意味します。このような「遷移問題がそのNP版よりも近似可能性の観点でより難しくなる」結果が証明されたのは初めてであり、これまで数十年間に渡り研究されてきた「NP問題の近似困難性」とは異なる理論的道具・技術が必要な可能性を示唆しています。
なお、理論計算機科学分野のトップカンファレンスであるFOCSにおいて、組合せ遷移を主要テーマとする論文が採択されるのは本研究が初の快挙となります。

■今後

これらの研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、当社内に限らず理論計算機科学分野における問題の社会応用を促進することが期待されます。今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。

※1 The 66th Annual Symposium on Foundations of Computer Science (FOCS 2025)
※2 ACM Symposium on Theory of Computing (STOC)