《计算复杂性：现代方法》是一本系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果的书籍。通过本书，读者可以了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。这本书对于从事计算复杂性理论及相关领域的研究人员来说，是一本必不可少的参考书。它提供了全面且深入的内容，使得读者可以深入了解复杂性理论的基本概念和原理，并且对于最新的研究成果有所了解。无论是初学者还是专业人士，都可以通过本书来提高自己在计算复杂性领域的知识和技能。《计算复杂性：现代方法》是一本内容全面、权威可靠的书籍。
计算复杂性：现代方法 电子书封面
读者评价
书是好书，但不是很好读，需要花费时间精力啃。
经典佳作，专业性强。
打算进入计算理论这个领域，对我来说是全新的东西。这本书在美亚上评价还不错，我买回来其实还没来得及看。粗翻翻感觉还可以，翻译的也算不错。
内容很有深度，需要慢慢消化，但都是精髓。
内容介绍
《计算复杂性：现代方法》系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分为三部分。*部分（第1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。
本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参考书，非常适合作为打算进入该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作为博士生相关讨论班的素材。
内容节选
什么是“计算复杂性”呢？
从信息论的角度来看，信息的简单还是复杂要通过表达该信息的符号串的复杂程度来描述。表达简单的非复杂系统的符号串序列很简短，其计算复杂性的程度不是很高。例如，所有项相加起来就得到这些项的和，描述这种非复杂的系统的符号串序列的程序或指令是非常简单的，只要把有关的项相加就行了。因此，计算复杂性可以定义为寻找最小的程序或指令集来描述给定符号串序列的复杂程度的操作过程。这个程序的大小与符号串序列的大小的相关程度就可以用来度量其计算复杂性。
例如，符号串序列“111111…”是均匀的，它的计算复杂性不高。描述这个符号串序列的程序很简单，只要在每一个符号1的后面续写一个1就行了。这个程序使得这个符号串序列得以无限地延续。
符号串序列“110110110110…”的计算复杂性要高一些，但仍然很容易写出描述这个符号串序列的程序：在两个1后面续写一个0，并重复进行。
符号串序列“110110100110110100…”也可以用很短的程序来描述；在两个1后面续写一个0并重复第二次；在第三次重复时将第二个1代之以0。
这样的符号串序列的结构都是可定义的，我们可以通过对应的程序来描述它们。
再看下面的符号串序列“11010010110111010010…”，这个符号串序列不再是一个可识别的结构，编写程序的时候必须将符号串序列全部列出，一个一个地加以枚举。
为了解决这些关于如何认识复杂性增长和判别复杂性程序的问题，科学家们定义了多种用于描述计算复杂性概念。
自然语言比上述的符号串都复杂，如何描述和处理自然语言的计算复杂性，是语言学理论中的一个困难问题。
目录
- 第一部分 基本复杂性类
- 第1章 计算模型——为什么模型选择无关紧要6
- 第2章 NP和NP完全性29
- 第3章 对角线方法53
- 第4章 空间复杂性61
- 第5章 多项式分层和交错75
- 第6章 布尔线路83
- 第7章 随机计算96
- 第8章 交互式证明113
- 第9章 密码学137
- 第10章 量子计算161
- 第11章 PCP定理和近似难度简介192
- 第二部分 具体计算模型的下界
- 第12章 判定树210
- 第13章 通信复杂性219
- 第14章 线路下界：复杂性理论的滑铁卢232
- 第15章 证明复杂性251
- 第16章 代数计算模型260
- 第三部分 高级专题
- 第17章 计数复杂性278
- 第18章 平均复杂性:勒维定理295
- 第19章 难度放大和纠错码305
- 第20章 去随机化330
- 第21章 伪随机构造:扩张图和提取器345
- 第22章 PCP定理的证明和傅里叶变换技术378
- 第23章 为什么线路下界如此困难411
有人说数学有多美。有人说复杂度理论有多美。我亲眼见过有人眯着眼睛告诉我，数学是多么的美。 虚伪做作。哗众取宠。道听途说。 他们或者并不知道数学是否美。但他们听过其他人说这个的观点，那些自某些大牛口中流传下来的观点，被廉价的唾液复制上千遍，于是他也要拿来复制一遍的观点。仿佛这句话是一个证书，一种魔法，你若承认，便有了天才的智慧。 得了。那不过是皇帝的新装和G. Hardy大人嚼剩下的残羹。 又或者，他们体会到了些许的美。但他们拒绝抬起头，向高处张望。不过是到了半山腰，便自鸣得意的说：啊，是啊，那座山美啊。 可他并不知道再往高处走，便全是走不下去的死路，伴着偶尔袭来的暴风。 Arora和Barak的这本Computational Complexity会让你忘记所有关于美的描述。这不是一本愉悦的书，无法畅快的阅读。太多细节被省略，有些原本20几页的证明，被AB二人在几段话之内简述。 会有人觉得这样的阅读体验和学习过程是美的。我从小就相信天才的存在，并因此自暴自弃二十年。只是这种美，是我这辈子都无法体会的。是我永远看不到也看不懂的风景。 那这本书为什么值5颗星？因为虽然没有见到美，但我体会到了恶和欲望。每当遇到那些难以理解的，被作者过分简述的证明，都意味着长时间的上下求索，推导，有时是几个小时，然后那么一瞬间，想通了，便是自大脑到全身的愉悦。如同，嗯，如同高潮。再之后，是长久的回味。我甚至会强迫我们实验室的人听我给他们讲解那些他们不关心的理论，只是为了回味那个瞬间。并在晚上回家以后，无法自拔继续研读这本跟我的方向毫无关联的糟书，等待着下一个被作者忽略的难懂的细节和下一次高潮，并美其名曰“求推dao”。 这不是美。是赤裸裸的欲望。