本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

平均時計算量に対するメタ計算量によるアプローチ
講演者:平原秀一(国立情報学研究所)
2021年2月19日(金)15時00分〜16時30分 Zoom
平均時計算量とは、入力がランダムに生成されているときに必要な期待計算時間のことを言う。NPの平均時計算量を解明することは、暗号の安全性やヒューリスティクスの計算時間を理解するために重要である。特に重要な未解決問題として、NPの平均時計算困難性を最悪時困難性の仮定から導けるか、というものがある。この未解決問題を解くためには「ブラックボックス帰着の限界」「困難性増幅の不可能性」「相対化のバリア」という三つの証明手法の限界を同時に突破する必要がある、ということが知られている。
 本講演では、「ブラックボックス帰着の限界」および「困難性増幅の不可能性」を同時に突破し、NPの平均時計算困難性をUPの指数的最悪時困難性の仮定から導いた研究成果を中心に解説を行う。証明手法は平均時計算量を「最悪時メタ計算量」という概念で解釈しなおすことに基づいている。メタ計算量とは、「計算量を問う問題の計算量」のことを意味する。時間が許せば、メタ計算量の近年の世界的な動向についても述べる。