ニュースリリース
2024/06/13
組合せ遷移分野における15年来の未解決問題を肯定的に解決
～理論計算機科学分野のトップカンファレンス「STOC 2024」にてNIIの平原秀一准教授らの論文採択～
大学共同利用機関法人 情報・システム研究機構 国立情報学研究所 (NIIエヌアイアイ、所長：黒橋くろはし 禎夫さだお、東京都千代田区）と、株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田ふじた 晋すすむ、東証プライム市場：証券コード4751）は、情報学プリンシプル研究系の平原ひらはら 秀一しゅういち 准教授とサイバーエージェントの人工知能技術の研究開発組織「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」で発表される予定です。
【論文タイトルと著者】
【研究背景】
組合せ遷移問題とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ことが求められる課題において、目標状態への到達可能性を判定する問題です。このような問題の中には、目標状態へ到達するために必要な手数が非常に大きくなり、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか、また難しくする要因は何かを計算複雑性理論の観点から解明するために、PSPACE困難性※4の証明をはじめとする様々な研究が行われてきました。
【論文の概要】
この度採択された論文では、組合せ遷移問題における「近似可能性」を扱っています。「近似」とは、厳密に判定するまたは厳密解を求めることが困難な問題に対し、その条件などを緩和することで得られる問題を考え、解決の糸口を探し出すための手段です。また近似可能性とは、厳密な解を得ることが難しい問題に対して、近似が可能な度合いを示すものです。組合せ遷移問題に対する近似(不)可能性は、これまで少数の結果しか知られておらず、特に、「組合せ遷移問題の近似がPSPACE困難であるか」という疑問は15年間に渡り未解決問題として残されてきました。※5
こうした背景のもと、サイバーエージェントAI Labから国際会議「STACS 2023」および「SODA 2024」で発表した論文※6では、仮説「Reconfiguration Inapproximability Hypothesis」※7を提唱し、仮説の下では幅広い組合せ遷移問題を近似的に解くことがPSPACE困難であることを証明していました。しかしこの方針で上記の未解決問題を解くためには、提案した仮説を証明（または反証）する必要がありました。本研究では、Reconfiguration Inapproximability Hypothesisを証明することに成功し、組合せ遷移分野における15年来の未解決問題を肯定的に解決しました。トップカンファレンスであるSTOCに組合せ遷移分野の論文が採択されるのは本研究が初めての快挙です。
平原 秀一 准教授のコメント：
組合せ最適化の分野では、PCP定理と呼ばれる重要かつ基礎的な定理に基づいて、様々な組合せ最適化問題の近似不可能性が解明されてきました。本研究では、組合せ遷移版のPCP定理を確立することに成功しました。今後は、この定理に基づいて様々な組合せ遷移問題の近似不可能性を解明することが可能になる、と期待しています。
関連リンク
News Release: PDF
組合せ遷移分野における15年来の未解決問題を肯定的に解決
～理論計算機科学分野のトップカンファレンス「STOC 2024」にてNIIの平原秀一准教授らの論文採択～
※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困難であるという仮説。
6423
