多面的アプローチの統合による計算限界の解明
平成24年度～平成28年度
渡辺 治（東京工業大学・大学院情報理工学研究科・教授）
本領域では、計算の限界を解明する強力な解析理論の構築を目指す。P≠NP 予想への新たなステップとなる理論を作り出していく。
計算限界の研究：計算の理解のために
「数学」は科学の言葉と言われてきた。さらに現代では、それが「計算」に汎化し、生活や社会に関する記述も含め、広い意味で「計算」が科学の言葉の役割を担っている。
しかし、我々は計算とは何かがよくわかってはいない。計算限界はその最も顕著な例である。たとえばアルゴリズム（計算方法）の計算効率の限界である。同じ問題を処理するにも、様々なアルゴリズムが設計可能であり、より計算効率のよい、すなわち、計算速度の速いアルゴリズム設計が望まれる。しかし、アルゴリズムの効率化にも限度があるはずだ。それが（処理したい問題に対する）計算限界である。残念ながら今のところ、ほとんどの問題に対し、このような計算限界を明らかにできていない。その顕著な例がP≠NP 予想である。こうした計算限界を部分的にでも明らかにすること、それにより、人類の計算への理解を前進させることが、本領域の目標である。
数理科学における21世紀の7大未解決問題であるP≠NP予想は、計算の限界に関する予想である。本領域では、この予想解決への新たなステップとなる強力な計算限界解析手法を構築し、解決へ向かう研究の道筋を提唱することを目指す。それは情報科学技術の核となるアルゴリズム設計に欠かせない「計算の理解」の基礎理論となるものである。
今やコンピュータは、科学技術から日常生活まで、人々にとって欠かせない道具である。そのコンピュータの利用において、スパコンを最大限活かし、大量のデータに秘められた情報を最大限利用するために鍵となるのが、性能の良いアルゴリズムの設計である。これまでにも、数多くの革新的アルゴリズムが発見され、それがコンピュータの利用価値を高めてきたが、まだまだ多くの革新的アルゴリズムが発見される余地がある。そうした発見の基礎となるのが、計算限界に対する理解である。どのような計算であれば、どこまで効率良くできるのか、また、計算の困難さはどこにあるのか？こうした点の解明が、良いアルゴリズムを導き出す基礎になる。本領域では。これまで研ぎ澄まされてきた計算限界解明技法を、さらに強化し体系立てる研究を進める。それにより、P≠NP予想の解決への道を開くとともに、計算を真に理解し、革新的アルゴリズムの発見に結び付く計算限界解明の基礎理論を築くことが本領域の目指すところである。
P≠NP予想解決までの道のりは長く、計算限界に関する様々な予測を解明する必要がある。しかも、現時点では、その道筋も不明確である。この状況を打破するため、具体的な計算問題において、計算効率に関する我々の直観を厳密に示すことを目指す。その中から、強力な計算限界解析手法を数多く生み出し、それらの統合として、P≠NP予想解明への道筋を示す戦略である。また、P≠NP予想は、計算についての制約が何もない中での計算限界を予想したものだが、本領域では、まずは、適切な制約下で、着実に、計算に対する新たな理解を得ることを技術目標とした。その中で、新たな一歩と呼べるような成果も得られている。その1つが、「計算の途中結果を再利用することが計算の効率化に必須である」という直観の厳密証明である。この非常に自然で基本的な直観に対し（深さ限定回路と呼ばれる制限付きの計算モデルの上ではあるが）計算量理論の50年の歴史の中で、初めてとなる厳密証明を与えることに成功した。一方、「定数個のデータを見るだけは、大した計算はできない」という我々の直観に反し、データ量がどのように多くなっても、定数個のデータを見るだけで検査ができる性質の特徴付けにも成功し、そのような検査が可能な非自明な性質を明らかにすることができた。これは、今後、革新的アルゴリズムへと発展する可能性もある。以上のような結果の背景には、強力な計算限界解析技法の開拓がある。今後、こうした技法を理論立てて行くことで、P≠NP予想のへの大きな一歩が築けると期待している。
A－（研究領域の設定目的に照らして、概ね期待どおりの進展が認められるが、一部に遅れが認められる）
本研究領域は、P≠NP予想をはじめとする重要な未解決問題の解決に向けて、新たな計算限界解析理論の構築を目指すものである。周辺の計算理論分野で長期的な課題であったいくつかの問題に、厳密な証明、完全解、解決に向けた道筋をつけるなど幾つかの重要な研究成果を得ており、評価できる。多くの会議を通じて研究領域間の連携や融合が起きており、領域代表者の構想はうまく機能している。一方、本領域における研究成果が他の分野にどのように応用されるのか、その波及効果と学理としての進歩性をより明らかにすべく、領域運営に一層の工夫を期待する。
「深さ限定回路の解析」では50年来の問題に厳密な証明を与え、「定数回質問検査の特徴付け」では20年来の未解決問題に完全解を得、「LP定式化の枠組みの下でのNPの困難さの解明」では拡張定式化サイズの超多項式を示す解析技法を開発している。一方、本領域としての研究期間内での最終目標がわかりにくいため、今後それを示し、総括班がリーダーシップをとり研究計画組織間で連携して目標に向かい運営していく必要がある。
「深さ限定回路の解析」では50年来の問題に厳密な証明を与え、「定数回質問検査の特徴付け」では20年来の未解決問題に完全解を得、「LP定式化の枠組みの下でのNPの困難さの解明」では拡張定式化サイズの超多項式を示す解析技法を開発しており、少なからぬ研究成果を得ている。最終的な課題解決に至るまでに生まれる数学技法やアルゴリズムはさまざまな分野に影響を与える可能性があり、研究成果の応用先を今後具体的に示していく必要がある。
国際交流や研究計画組織間の交流は盛んで、それによって新たな発想に基づく各課題の展開が開けてきており、有機的な連携がとられているとみられ問題はない。公募研究との融合もうまく進んでおり、若手研究者の育成も活発に行われている。招聘した外国人研究者による他研究計画組織への波及効果が大きいことも評価できる。
特に問題点はなかった。
多くの会議を通じて研究計画組織間の連携や融合が起きており、総括班はうまく機能していると評価できる。しかしながらP≠NP問題のような真の難問に立ち向かう戦略としては、分散した個々の成果の集積に留まらずに、新学術領域としての新たな展開を総括班によって方向付けすべきであろう。例えば、情報処理に関する今日的な社会的なインパクトを持つ課題に対する波及効果を示していくことを検討するなど、工夫の余地はある。
各計画研究において順調に成果があがっており、今後の研究計画・方法も意欲的かつ妥当であることから、継続に係る審査の必要はない。研究経費も適切に形状されており、問題はない。
研究振興局学術研究助成課
-- 登録：平成26年11月 --