AI Lab、理論計算機科学の国際会議「STACS 2023」にて論文採択 ― 組合せ遷移問題の近似不可能性の新たな開拓 ―

株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人による論文が、国際会議「40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)」に採択されたことをお知らせいたします。
「STACS」は毎年開催される理論計算機科学の国際会議で、ヨーロッパにおける主要会議の1つです。本論文は、2023年3月にドイツのハンブルグにて開催されるSTACS 2023にて発表を行います。


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

組合せ遷移問題とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ようなタスクで、目的の状態に到達する事ができるかどうかを判定する問題です。
しかし、問題によっては目標状態へ到達するために必要な手数が非常に大きく、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか・また難しくする要因は何か、を計算複雑性理論の観点から解明するために、PSPACE困難性 ※2 の証明をはじめとする様々な研究が行われてきました。

※1 組合せ遷移＠学術変革領域研究(B) ：https://core.dais.is.tohoku.ac.jp/
※2 PSPACE困難性：多項式量のメモリを使って解ける任意の問題と比べて、少なくとも同等以上に難しいという性質

「Gap Preserving Reductions between Reconfiguration Problems」
Naoto Ohsaka. （CyberAgent）


本論文では、組合せ遷移問題における「近似可能性」を扱っています。「近似」とは、条件が複雑で解を出すことが困難な問題に対し、その難しい条件を緩和していくことにより、元とは違う近しい問題として扱うことで、解決の糸口を探し出すための手段です。
また近似可能性とは、このように厳密な解を得ることが難しい問題に対して、近似がどれほど可能かを示すものです。

これまで組合せ遷移という研究分野においては、「組合せ遷移問題の近似がPSPACE困難であるかどうか」は未解決の研究課題として残されてきました。

こうした背景のもと、本研究では、組合せ遷移研究において近似不可能性を示す手段として、作業仮説「Reconfiguration Inapproximability Hypothesis」を提案し、数ある組合せ遷移問題の中でどれが近似不可能となり得るかを調査しました。

その成果として、幅広い組合せ遷移問題においてその近似が提案作業仮説の下でPSPACE困難である事が証明できました。これにより今後、組合せ遷移の近似可能性理論の研究を後押しすることが期待できます。

論文詳細：Naoto Ohsaka. Gap Preserving Reductions between Reconfiguration Problems. STACS, 2023. 


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