平均計算量理論のお勉強

研究

平均計算量理論の研究を現在進行形でやってるわけですが，基本的な知識に抜けが多すぎるので，このサーベイ論文で勉強しなおすことにしました．

平均計算量の基本的な概念や重要な結果が分かり易くコンパクトにまとめられていてとても勉強になります．っていうかLevinは凄いなぁ．特に「平均的に効率が良い」という概念の定式化に痺れました．この内容をfull paperでたった２ページにまとめるだなんて．