伯克利 CS172 可计算性和复杂性

课程名称： Computability and Complexity
课程官网地址：CS172课程官网
先修课程： CS170 高效算法和棘手问题
重要程度： ※※※※※
课程评点：

课程说明

有限自动机、图灵机和 RAM。不可判定、指数和多项式时间问题。所有合理的计算模型的多项式时间等价性。非确定性图灵机。NP完全性理论：库克定理，基本问题的NP完全性。语言理论、复杂性和随机性的选题。