【普林斯顿Sanjeev Arora教授干货书】计算复杂度，一种现代方法，489页pdf

计算复杂度理论在过去的三十年里发展迅速。自1990年以来所证明的一系列令人惊讶和基本的结果足以写一本书:这些结果包括经典复杂性类(IP = PSPACE和PCP定理)的新概率定义及其对近似算法领域的影响;使用量子计算机分解整数的肖尔算法;理解为什么目前对著名的P对NP的方法不会成功;基于计算硬度的去随机化和伪随机理论还有伪随机对象的漂亮构造，比如提取器和扩展器。这本书旨在描述在经典结果的背景下复杂性理论的这些最近的成就。它的目的是作为一本教科书，作为自学的参考。这意味着它必须同时迎合许多观众，并且是精心设计的。在本书中，我们解释了特定概念在什么情况下是有用的，以及为什么事物以某种方式被定义。，里面有相关的辅助材料。这包括关于自动机和可计算性理论的网页章节，基于本书的课程的详细教学计划，书中所有章节的草稿，以及涉及相关主题的其他在线资源的链接。

第一部分:基本复杂度类。本卷提供了对该领域的广泛介绍。从图灵机的定义和可计算性理论的基本概念开始，这卷涵盖了基本的时间和空间复杂度类，也包括一些更现代的主题，如概率算法，交互式证明和密码学。

第二部分:具体计算模型的下界。本部分描述了在具体模型(如电路、决策树等)上求解算法任务所需资源的下界。乍一看，这些模型似乎与图灵机非常不同，但深入观察，就会发现有趣的相互联系。

第三部分:高级主题。这部分主要介绍1980年代后期以来的发展情况。它包括平均情况复杂度、去随机化和伪随机化、PCP定理和逼近困难、证明复杂度和量子计算。