課本
Computational Complexity,
C. M. Papadimitriou, Addison-Wesley, 1994.
課程投影片
第一章
Problems and algorithms
(3.03 Mb)
第二章
Turing machines
(2.89 Mb)
第三章
Computability
(69 Kb)
第七章
Ralations between complexity classes
(78 Kb)
第八章
Reductions and completeness
(271 Kb)
第九章
NP-complete problems
(418 Kb)