计算理论讨论计算硬件、软件和相关应用其中的基本数学特性。在这一领域的研究中，我们致力于研究哪些问题可以判定，哪些问题不能，还有在不同的计算模型上计算这些问题所需的时间、空间。对于可判定的问题，计算复杂性关注计算问题时所需要的资源。基于对计算所需资源的分析，计算复杂性研究哪些算法是“可行的”，以及难解问题的分类。（以上参考各书引言。）阅读： Introduction to the Theory of Computation - Michael Sipser Computational Complexity - Sanjeev Arora & Boaz Barak 课程视频资源：【2022新年放送-中英字幕MIT 18.404J 计算理论 Theory of computation，2020Fall】（扫了一眼分集标题，应当对应Sipser的书。）【油管】CSS.203.1 Computational Complexity (2021-I) - STCS TIFR （使用Arora&Barak的书。）【【计算理论】加州戴维斯 Theory of Computation (Phillip Rogaway)】【Theory of Computation & Automata Theory】计划：大概一到两周完成阅读《Computational Complexity》的一章，欢迎线上讨论交流。附上书籍前六章目录：

计算复杂性讨论帖

计算理论讨论计算硬件、软件和相关应用其中的基本数学特性。在这一领域的研究中，我们致力于研究哪些问题可以判定，哪些问题不能，还有在不同的计算模型上计算这些问题所需的时间、空间。

对于可判定的问题，计算复杂性关注计算问题时所需要的资源。基于对计算所需资源的分析，计算复杂性研究哪些算法是“可行的”，以及难解问题的分类。

（以上参考各书引言。）

阅读：

课程视频资源：

计划：
大概一到两周完成阅读《Computational Complexity》的一章，欢迎线上讨论交流。

附上书籍前六章目录：

其实帖子推荐的这两本书分别跑在不同的跑道上。相对而言，ITOC非常友好（你不能因为自己感觉它很难就忘记了这只是相对而言的友好），而AB07的CC则深度、广度、难度都大很多，适合有一定计算理论和复杂性理论基础的人阅读。

能啃下来AB07，当然好了，那你就是Boaz Barak的好朋友，成为可以向STOC、FOCS进军的学者。