2012-06-08 駆け足で読む『計算理論の基礎』第3巻:複雑さの理論 駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ 7 時間の複雑さ 7.1 複雑さの測定 7.2 クラスP 7.3 クラスNP 7.4 NP完全性 7.5 他のNP完全問題 8 領域の複雑さ 8.1 Savitch の定理 8.2 クラスPSPACE 8.3 PSPACE 完全性 8.4 クラスLとクラスNL 8.5 NL完全性 8.6 NLとcoNLの等価性 9 問題の扱いにくさ 9.1 階層定理 9.2 相対化 9.3 回路の複雑さ 10 計算の複雑さの理論における先進的な話題 10.1 近似アルゴリズム 10.2 確率的アルゴリズム 10.3 交替制 10.4 対話証明系 10.5 並列計算 10.6 暗号