計算量理論

0. 計算量基礎、ソーティング計算量下限、行列乗算 1. 計算量、時間計算量、多項式時間vs.指数時間 2. Turing機械、時間計算量、クラスP、領域計算量、クラスPSPACE 3. 非決定性Turing機械、クラスNP、多項式時間還元 4. Cook-Levin定理、NP完全性 5. Karp還元、3SAT, VCのNP完全性 6. NP完全性による計算問題解析、数問題、動的計画法 7. 擬多項式時間アルゴリズム、強NP完全 8. 近似アルゴリズム、近似値比 9. ビンパッキング問題、巡回商人問題 10. ナップザック問題、PTAS、FPTAS 11. 加法的近似、近似不可能性、 12. co-NP、3典型問題、多項式階層、PSPACE完全、LOGSPACE 13. 対話証明概説 14. 計算量理論まとめ

本講義は合併科目であるため、工学部・理学部学生については、それぞれの所属学部の科目で履修登録すること。工学部・理学部以外の学生については、理学部科目として履修登録すること。

試験およびレポート課題によって評価を行う。 試験を基本とし、レポート提出がある場合はそれを加味する。

前提となる知識と項目：計算量、時間計算量、領域計算量、多項式時間、指数時間、Turing機械、クラスP、クラスNP、クラスPSPACE、クラスEXPTIME、クラスLOGSPACE、非決定性計算、Cook-Levin定理、Karp還元、NP完全、NP困難、擬多項式時間アルゴリズム、強NP完全、弱NP完全、近似アルゴリズム、近似値比、PTAS、FPTAS、加法的近似、近似不可能性、co-NP、 多項式階層PH、PSPACE完全、対話証明、行列乗算