最小記述量の計算困難さの解析
【研究キーワード】
最小記述量 / 最小記述量計算 / P≠NP予想 / 計算論的学習理論 / 一方向関数 / 多項式時間階層 / 平均時計算困難性 / 計算論的暗号 / PAC学習困難性 / 最小記述量計算問題 / 機械学習 / Ｐ≠ＮＰ予想 / 平均時計算量 / 平均時計算複雑度 / 学習可能性 / 情報セキュリティ / 情報セキュリティ技術 / 最小回路サイズ問題 / 回路計算量 / 質問計算量 / SAT問題 / 量子計算の基礎
【研究成果の概要】
これまでの研究の中から最小記述量計算問題の計算困難さに関連する様々な結果が出始めてきたが，本年度は，それをさらに進めて，最小記述量計算問題をコルモゴロフ記述量ならびに機械学習可能性（正確にはPAC学習複雑度）と関連付け，それにより，NP問題全般（あるいはもう少し広い多項式時間階層，クラスPH）の平均時複雑度へ関連付ける研究を進めた。その中で得られた結果のうちで主要なものを以下に述べる。
１．多項式時間階層クラスPHの平均時計算複雑度を小記述長問題の最悪時計算複雑度により特徴づけることに成功した。その結果として，PHに対する困難性増幅定理を得た。たとえば，PHの代表的な問題に対して，その1%の入力が効率的に解けることとPHのすべての問題に対して，その99%の入力が効率的に解けることが同値であることがわかった。
２．PHの最悪時計算複雑度を平均時計算複雑度に結び付ける重要な手法の一つに，PHの最悪時計算困難性をもとに計算論的暗号素（computationally secure cryptographic primitive）を作り出す手法が考えられる。しかし，そのような手法は，通常の計算論的解析（より正確には，black-box的な並列乱択還元を用いた解析）では不可能であることを示した。その証明においては，PHの構造的困難さ（より正確には密でない集合への還元可能性）について，既存の特徴づけを大幅に改良する特徴づけを与える技法を開発した。
３．従来の学習の枠組みならびに暗号の枠組みを拡張することにより，（その枠組みの上での）PAC学習困難性と計算論的暗号素の構成可能性間の同値性を示すことができた。なお，これは本研究課題でRAとして雇用している博士課程学生の独自研究である。
４．3SAT問題に対して，指数関数時間ではあるが（その時点での）世界最速の乱択アルゴリズムを得た。
【研究代表者】