2024 年（令和 6 年）6 月 13 日

組合せ遷移分野における 15 年来の未解決問題を肯定的に解決～理論計算機科学分野のトップカンファレンス「STOC 2024」にて
NII の平原秀一准教授らの論文採択～
エヌアイアイ

くろはしさだお大学共同利用機関法人 情報・システム研究機構 国立情報学研究所（ N I I 、所長：黒橋 禎夫、ふじたすすむ

東京都千代田区）と株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田 晋 、ひらはら しゅういち

東証プライム市場：証券コード 4751）は、情報学プリンシプル研究系の平原 秀 一 准教授とサイおおさか

なおと

バーエージェントの人工知能技術の研究開発組織「AI Lab」に所属する大坂 直人 研究員による主著 論 文 「 Probabilistically Checkable Reconfiguration Proofs and Inapproximability ofReconfiguration 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月にカナダのバンクーバーで開催される「STOC2024」で発表される予定です。
【論文タイトルと著者】
論 文 名 ： Probabilistically Checkable Reconfiguration Proofs and Inapproximability ofReconfiguration Problems
著

者：平原 秀一（国立情報学研究所）、大坂 直人（サイバーエージェント AI Lab）

大学共同利用機関法人 情報・システム研究機構
国立情報学研究所
株式会社 サイバーエージェント

【研究背景】
組合せ遷移問題とは、ルービックキューブや 15 パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ことが求められる課題において、目標状態への到達可能性を判定する問題です。このような問題の中には、目標状態へ到達するために必要な手数が非常に大きくなり、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか、また難しくする要因は何かを計算複雑性理論の観点から解明するために、PSPACE 困難性※4 の証明をはじめとする様々な研究が行われてきました。
【論文の概要】
この度採択された論文では、組合せ遷移問題における「近似可能性」を扱っています。
「近似」とは、厳密に判定するまたは厳密解を求めることが困難な問題に対し、その条件などを緩和することで得られる問題を考え、解決の糸口を探し出すための手段です。また近似可能性とは、厳密な解を得ることが難しい問題に対して、近似が可能な度合いを示すものです。組合せ遷移問題に対する近似(不)可能性は、これまで少数の結果しか知られておらず、特に、「組合せ遷移問題の近似が PSPACE困難であるか」という疑問は 15 年間に渡り未解決問題として残されてきました。※5
こうした背景のもと、サイバーエージェント AI Lab から国際会議「STACS 2023」および「SODA2024」で発表した論文※6 では、仮説「Reconfiguration Inapproximability Hypothesis」※7 を提唱し、仮説の下では幅広い組合せ遷移問題を近似的に解くことが PSPACE 困難であることを証明していました。しかしこの方針で上記の未解決問題を解くためには、提案した仮説を証明（または反証）する必要がありました。本研究では、Reconfiguration Inapproximability Hypothesis を証明することに成功し、組合せ遷移分野における 15 年来の未解決問題を肯定的に解決しました。ト
ップカンファレンスである STOC に組合せ遷移分野の論文が採択されるのは本研究が初めての快挙です。
平原 秀一 准教授のコメント：「組合せ最適化の分野では、PCP 定理と呼ばれる重要かつ基礎的な定理に基づいて、様々な組合せ最適化問題の近似不可能性が解明されてきました。本研究では、組合せ遷移版の PCP 定理を確立することに成功しました。今後は、この定理に基づいて様々な組合せ遷移問題の近似不可能性を解明することが可能になる、と期待しています。」

大学共同利用機関法人 情報・システム研究機構 国立情報学研究所
株式会社 サイバーエージェント

〈メディアの皆様からのお問い合わせ先〉
大学共同利用機関法人 情報・システム研究機構 国立情報学研究所
総務部企画課 広報チーム
TEL：03-4212-2164

E-mail：media@nii.ac.jp

株式会社 サイバーエージェント
AI 事業本部 広報
E-mail：cyberagent.ai_pub@cyberagent.co.jp※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 困難であるという仮説。

大学共同利用機関法人 情報・システム研究機構 国立情報学研究所
株式会社 サイバーエージェント