駆け足で読む『計算理論の基礎』第3巻:複雑さの理論

  • 7 時間の複雑さ
  • 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 計算の複雑さの理論における先進的な話題