理論計算機科学特論

岡本 吉央

テーマ：計算複雑性の基礎

注意：テーマは毎年変わる可能性があります

ショートカット： 講義資料 | コメント | レポート課題 | 公式シラバス | スケジュール | 参考文献 | 関連リンク | 過去の講義

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いません．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

• 講義動画の再生リスト
• 4/7 (1) 計算理論の復習
  • スライド
  • 講義動画

• 4/7 (1) 計算理論の復習

• 評価は毎回のクイズと2回のレポート課題により行う予定でいます．
• 毎回のクイズはGoogle Classroomのフォームで行います．

• こちらをご覧ください

• 4/7 (1) 計算理論の復習
• 4/14 (2) 時間複雑性：P, NP, coNP
• 4/21 (3) 還元と完全性：NP完全
• 4/28 (4) 領域複雑性：L，NL，PSPACE
• 5/5 休み（祝日）
• 5/12 (5) 時間と領域の関係：P⊆PSPACE⊆EXPTIME
• 5/19 (6) 階層定理：P≠EXPTIME
• 5/26 (7) Ladnerの定理：P≠NP => NP-P≠NPC
• 6/2 (8) Savitchの定理：PSPACE=NPSPACE
• 6/9 (9) Immerman-Szelepcsényiの定理：NL = coNL
• 6/16 (10) 多項式階層：P=NP => P=PH
• 6/23 (11) 交代性計算：AP=PSPACE
• 6/30 (12) 確率的計算：BPP⊆PP, NP⊆PP
• 7/7 (13) 対話証明系 (1)：MA，AM，NP⊆MA⊆AM
• 7/14 (14) 対話証明系 (2)：IP⊆PSPACE
• 7/21 (15) 対話証明系 (3)：PSPACE⊆IP (オンデマンドの予定)
• 7/28 休み（授業のない日）KWCG

• Michael Sipser, Introduction to the Theory of Computation.
• Sanjeev Arora and Boaz Barak, Computational Complexity Theory: A Modern Approach.

• Complexity Zoo