MIT 6.045 可计算性与复杂性理论

课程名称： 6.1400[J] Computability and Complexity Theory (6.045)
课程官网地址： 2020年
先修课程： MIT 6.042 计算机科学中的数学
重要程度：
课程评点：

课程说明

计算理论的数学导论。严格探索计算机可以通过有限自动机、电路、图灵机和通信复杂性有效解决哪些类型的任务，向学生介绍数学中的一些主要开放问题。培养根据计算任务的难度对计算任务进行分类的技能。讨论计算中的其他基本问题，包括停止问题、丘奇图灵论、P 与 NP 问题以及随机性的力量。