― 組合せ遷移分野における15年来の未解決問題を肯定的に解決 ―
広告 ｜2024年6月13日
株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）と大学共同利用機関法人 情報・システム研究機構 国立情報学研究所（NII(エヌアイアイ)、所長：黒橋禎夫、東京都千代田区）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人および国立情報学研究所の平原秀一准教授による主著論文「Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems」が、理論計算機科学分野のトップカンファレンス「56th ACM Symposium on Theory of Computing (STOC 2024)」※1に採択されたことをお知らせいたします。
「ACM Symposium on Theory of Computing (STOC)」は世界中の研究者達によって開催される国際会議で、「IEEE Symposium on Foundations of Computer Science (FOCS)」※2と並ぶ、理論計算機科学における最高峰の国際会議です。STOCは1969年から開催される歴史ある国際会議で、1971年開催のSTOCでは有名な「P≠NP予想」がStephen A. Cookにより定式化されたことをはじめ、現代の理論計算機科学の基礎を築く概念や定理が数多く提唱・証明されてきました。このたび採択された論文は、理論計算機科学の中の「組合せ遷移」※3 と呼ばれる領域に関する15年来の未解決問題を肯定的に解決したもので、2024年6月にカナダのバンクーバーで開催される「STOC 2024」で発表される予定です。
論文名：Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
著者：平原秀一（国立情報学研究所）・大坂直人（サイバーエージェント AI Lab）
■研究背景
「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、本論文の内容は理論計算機科学の中の「組合せ遷移」※3 と呼ばれる領域の基礎研究に該当しています。
組合せ遷移問題とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ことが求められる課題において、目標状態への到達可能性を判定する問題です。このような問題の中には、目標状態へ到達するために必要な手数が非常に大きくなり、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか、また難しくする要因は何かを計算複雑性理論の観点から解明するために、PSPACE困難性※4の証明をはじめとする様々な研究が行われてきました。
■論文の概要
この度採択された論文では、組合せ遷移問題における「近似可能性」を扱っています。「近似」とは、厳密に判定するまたは厳密解を求めることが困難な問題に対し、その条件などを緩和することで得られる問題を考え、解決の糸口を探し出すための手段です。また近似可能性とは、厳密な解を得ることが難しい問題に対して、近似が可能な度合いを示すものです。組合せ遷移問題に対する近似(不)可能性は、これまで少数の結果しか知られておらず、特に、「組合せ遷移問題の近似がPSPACE困難であるか」という疑問は15年間に渡り未解決問題として残されてきました。※5
こうした背景のもと、過去にAI Labから国際会議「STACS 2023」および「SODA 2024」で発表した論文※6では、仮説「Reconfiguration Inapproximability Hypothesis」※7を提唱し、仮説の下では幅広い組合せ遷移問題を近似的に解くことがPSPACE困難であることを証明してきました。しかしこの方針で上記の未解決問題を解くためには、提案した仮説を証明（または反証）する必要がありました。本研究では、Reconfiguration Inapproximability Hypothesisを証明することに成功し、組合せ遷移分野における15年来の未解決問題を肯定的に解決しました。トップカンファレンスであるSTOCに組合せ遷移分野の論文が採択されるのは本研究が初めての快挙です。
■今後
本研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、当社内に限らず組合せ遷移問題の社会応用を促進することが期待されます。今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。
※1 http://acm-stoc.org/stoc2024/
※2 http://ieee-focs.org/
※3 組合せ遷移＠学術変革領域研究(B) ：https://core.dais.is.tohoku.ac.jp/
※4 PSPACE困難性：多項式量のメモリを使って解ける任意の問題と比べて、少なくとも同等以上に難しいという性質
※5 T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. “On the Complexity of Reconfiguration Problems.” In ISAAC. 2008, pp. 28–39. (https://doi.org/10.1007/978-3-540-92182-0_6) および T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. “On the Complexity of Reconfiguration Problems.” Theor. Comput. Sci. 412.12–14 (2011), pp. 1054–1065. (https://doi.org/10.1016/j.tcs.2010.12.005)
※6 https://www.cyberagent.co.jp/news/detail/id=28556およびhttps://www.cyberagent.co.jp/news/detail/id=29653
※7 Reconfiguration Inapproximability Hypothesis：制約充足問題の入力Πとその充足割当2つAとBが与えられた時に、「AからBへΠを充足したまま遷移可能」か「どのような遷移も必ず定数割合の制約を充足できなくなる」かを判定するのがPSPACE困難であるという仮説。
Tweet
