复杂性理论是计算机科学的理论基础的核心。本书是普林斯顿大学Sanjeev Arora和Boaz Barak的力作，目前在princeton，yale等很多学校采用，我国复旦大学等重点教材也有采用。书中全面分析了复杂性理论的经典原理和现代主题，适合作为“非密码专业方向”的计算机、信息安全等相关专业的研究生教材。

计算复杂性理论是理论计算机科学研究的核心。本书基本上包含了计算复杂性领域近30年来所有令人兴奋的成果，是对此领域感兴趣的读者的必读书籍。
—— 阿维·维德森（Avi Wigderson），普林斯顿大学数学学院高级研究所教授
本书综述了复杂性理论的所有重大成果，对学生和研究者来说是非常有用的资源。
—— 迈克尔·西普塞（Michael Sipser），麻省理工学院数学系教授

本书既描述了计算复杂性理论最近取得的成果，也描述了其经典结果。具体内容包括：图灵机的定义和基本的时间、空间复杂性类，概率型算法，交互式证明，密码学，量子计算，具体的计算模型的下界（判定树、通信复杂度、恒定的深度、代数和单调线路、证明复杂度），平均复杂度和难度放大，去随机化和伪随机数产生器，以及PCP定理。
本书仅要求读者有完备的数学知识，可以作为任何对计算复杂性感兴趣的读者的自学参考书，包括物理学家、数学家和其他科学家，也可以作为各种课程和研讨会的教科书。

作者简介
桑杰夫·阿罗拉（Sanjeev Arora）　普林斯顿大学计算机科学系教授，在概率可验证明和NP-难问题的可近似性方面取得了基础性的研究成果。他发起创办了“计算难解性问题中心”，该项目由国家科学基金资助。
博阿兹·巴拉克（Boaz Barak）　现为哈佛大学计算机科学系教授，哈佛大学工学院计算理论研究组成员，同时还是微软新英格兰研究院首席研究员，之前是普林斯顿大学计算机科学系副教授。他在计算复杂性和密码学方面，特别是“非黑盒”技术方面，取得了基础性的研究成果。

计算复杂性理论在过去三十多年中发展迅速。自1990年以来取得的出人意料的结果和基础性的结果本身就可以写出一部书。这些结果涉及的领域非常广泛，包括：经典复杂性类的概率型新定义（IP=PSPACE和各种PCP定理）以及它们在近似算法中的应用，肖尔（Shor）为量子计算机设计的整数因数分解算法，对人们目前处理著名的P =NP问题　译文用“P =NP”来表示原文中的“P versus NP”。——译者注的各种方法为什么未能获得成功的理解，去随机化理论和基于计算难度的伪随机性，以及随机性提取器和扩张图等伪随机对象的优美构造。
本书的目标就是为了在介绍复杂性理论经典结果的同时阐述近年来取得的新成果。写作本书的出发点是让它既可以作为教科书使用，也可以作为自学的参考书使用。这意味着我们在写作本书时必须兼顾广泛的读者。为实现这一目标，我们对全书进行了精心的设计。我们实际上还假设读者不具备关于计算的任何背景而且只具备附录A中概述的最少数学背景。我们为本书提供了一个网站http://www.cs.princeton.edu/theory/complexity。网站上列出了相关的辅助材料，包括用本书作为教材时的详细教学计划、全书各个章节的草稿，以及涵盖相关主题的其他资源的超链接。全书始终强调各个概念在何种场合下是有用的，以及为什么这些概念要这样定义。在一些关键的定义上，我们还用一些例子进行了阐释。为了使行文流畅，我们力争尽可能少地引用参考文献。参考文献的引用有两种情况，其一是当前的结果用到了文献中的标准术语，其二是我们觉得为特定的结果提供一些历史信息将有助于阐明其动机和适用的场合。每章末尾有一个单独的注记小节，它简明扼要地讨论了更多的相关工作。当一个概念有多种定义时，我们会选择相对简单的定义；当一个结果有多种证明时，我们会选择能证得更具一般性的结论或者最优结论的证明。
全书分为三个部分。
第一部分：基本复杂性类。这个部分是对复杂性理论的广泛介绍。从图灵机的定义和可计算理论的基本概念开始，这个部分涵盖了各种基本的时间复杂性类和空间复杂性类，还包含了更现代的一些专题，包括概率算法、交互式证明、密码学、量子计算机和PCP定理及其应用。
第二部分：具体计算模型的下界。这个部分讨论在线路和判定树等具体计算模型上用算法求解各种计算任务所需的计算资源的下界。这些计算模型初看起来与图灵机有很大的区别，但更深入研究将得到它们与图灵机之间的有趣的相互联系。
第三部分：高级专题。这个部分主要是1980年以后人们在复杂性理论方面获得的进展。内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。
本书的每一章几乎都可以单独进行阅读，但是第1章、第2章和第7章不能跳过。正是这种设计，使得本书可以适用于下面各种不同的读者。
物理学家、数学家和其他科学家。这个读者群对计算复杂性理论越来越感兴趣，他们特别感兴趣的是那些高调的研究结果，例如肖尔算法(Shor algorithm)和最近取得的确定型素性测试算法。这个读者群的知识储备丰富，他们可以快速通读第一部分，然后迅速进入第二部分和第三部分，也可以单独阅读各个章节并找到理解当前研究结果所需的每个知识点。
本身不从事计算复杂性理论研究的计算机科学家。他们既可以用本书来自学，也可以将本书作为参考书，还可以用本书来讲授本科生或研究生的计算理论或计算复杂性理论课程。
从事计算复杂性理论研究或者打算从事这种研究的任何人，包括教授和学生。本书讲解最新研究结果和高级专题的详细程度可以让打算从事复杂性理论和相关领域研究的读者具有充足的知识储备。
本书可以作为如下几类课程的教科书。
本科生的计算理论课程。很多计算机科学系都用西普赛尔(Sipser)的书［Sip96］来为本科生开设计算复杂性理论这门课。本书可以用作对西普赛尔的教材在一些更现代的专题上的补充，这些专题包括概率算法、密码学和量子计算。相比于自动机理论和可计算理论的精细划分，本科生可能会发现这些专题更能令人耳目一新。所需的数学背景是能够比较自然地阅读数学证明以及离散数学知识，这些知识通常涵盖于“离散数学”或“计算机数学”等课程中，而目前多数计算机系都已经开设了这样的课程。
为高年级本科生和新入学的研究生开设的计算复杂性导论课程。本书还可以用来为计算机科学专业的高年级本科生和新入学的研究生开设计算复杂性导论课程，以替代1994年帕帕迪米特里奥(Papadimitriou)撰写的教材［Pap94］（该书未包含很多最近的研究成果）。这门课程可以讲授第一部分的多数专题，再零星地讲授第二部分和第三部分的内容，并且假设学生具备了一定的算法知识和计算理论的知识。
研究生的计算复杂性课程。本书也可以作为研究生的计算复杂性课程的教材，以培养学生在复杂性理论或者算法和机器学习等相关领域开展研究的能力。这门课程可以用第一部分来复习基本知识，然后进入第二部分和第三部分的高级专题中。本书的内容多于一个学期的教学内容，网站上提供了这门课程的其他几种教学大纲。
研究生讨论班或高级课程。第二部分和第三部分中的各个独立章节都可以用于复杂性理论的讨论班和高级课程，比如关于去随机化、PCP定理和下界的讨论班或高级课程。
本书网站为这些课程提供了几种教学计划和素材。如果你在课程中采用了本书，我们乐意了解情况并得到你的反馈。我们要求你不要在网上发布本书习题的答案，这样其他人才可以用这些习题给学生留作业或出考题。
在写作本书的过程中，我们清醒地意识到我们不得不舍弃对一些重要结果的讲述。我们希望本书对其他教材的大量引用有助于读者的进一步阅读。同时，我们还计划对本书的网站进行周期性的更新，以帮助读者了解和浏览他们感兴趣的新结果。
最重要的是，我们希望通过本书将计算复杂性中激动人心的研究结果以及它们对其他学科的深刻影响传递给读者。
让我们一起为彻底解决P =NP问题而努力吧！

计算机

计算复杂性理论是理论计算机科学研究的核心。本书基本上包含了计算复杂性领域近30年来所有令人兴奋的成果，对此领域感兴趣的读者的必读书籍。
——阿维•维德森（Avi Wigderson），普林斯顿大学高级研究所教授

本书综述了复杂性理论的所有重大成果，对学生和研究者来说是非常有用的资源。
——迈克尔•西普塞（Michael Sipser），麻省理工学院数学系主任，《计算理论导引》

本书既描述了计算复杂性理论最近取得的成果，也描述了其经典结果。具体内容包括：图灵机的定义和基本的时间、空间复杂性类，概率型算法，交互式证明，密码学，量子计算，具体的计算模型的下界（判定树、通信复杂度、恒定的深度、代数和单调线路、证明复杂度），平均复杂度和难度放大，去随机化和伪随机数产生器，以及PCP定理。
本书仅要求读者有完备的数学知识，可以作为任何对计算复杂性感兴趣的读者的自学参考书，包括物理学家、数学家和其他科学家，也可以作为各种课程和研讨会的教科书。

[美] 桑杰夫·阿罗拉（Sanjeev Arora） 博阿兹·巴拉克（Boaz Barak） 著：桑杰夫·阿罗拉(Sanjeev Arora)是普林斯顿大学计算机科学系教授，在概率可验证明和NP-难问题的可近似性方面取得了基础性的研究成果。他发起创办了“计算难解性问题中心”，该项目由国家科学基金资助。
博阿兹·巴拉克(Boaz Barak）是普林斯顿大学计算机科学系副教授，在计算复杂性和密码学方面，特别是“非黑盒”技术方面，取得了基础性的研究成果。

骆吉洲 译：暂无简介

阿兰·图灵(Alan Turing)等人对计算的精确定义导致了现代电子计算机的诞生。如今，计算机早已融入社会管理、经济活动、工程实践、军事活动、休闲娱乐等现代生活的方方面面，各种计算机软件精彩纷呈、层出不穷。可以说，计算无时无刻地发生在我们的周围。对各种计算问题的计算过程所消耗的时间/空间等资源数量的多少进行量化，进而对各种计算问题进行分类，并研究各类计算问题之间的相互联系，研究近似求解无法精确求解的问题的难度，力争最终解决计算中最核心的问题，围绕这些任务逐渐发展和形成的理论、技术和方法，形成了理论计算机科学中的一门基础性学科——计算复杂性理论。它是为各种计算问题合理地选择算法、配置资源并进行软件开发活动的基础。
计算复杂性理论形成于20世纪五六十年代。1960年，哈特马尼斯(Hartmanis)和斯特恩斯(Stearns)在他们的开创性论文“On the computational complexity of algorithms”中引入了时间复杂性类并利用对角线方法证明了时间分层定理，由此奠定了计算复杂性理论的基础。在其后的三十年中，人们逐渐得到了各种基本复杂性类、NP完全理论等经典结论，并提出了计算复杂性理论中最核心的问题P?=NP。在过去三十多年中，计算复杂性理论发展迅速。自1990年以来，人们取得了大量出人意料的结果和基础性的结果，这些结果涉及的领域非常广泛，包括：经典复杂性类的概率型新定义（IP=PSPACE和各种PCP定理）以及它们在近似算法中的应用，肖尔（Shor）为量子计算机设计的整数因数分解算法，对人们目前处理著名的P?=NP问题的各种方法为什么未能获得成功的理解，去随机化理论和基于计算难度的伪随机性，以及随机性提取器和扩张图等伪随机对象的优美构造。
作为计算机科学与技术相关专业的学生，全面系统地学习计算复杂性中的概念、基本结果、思维方法和重要工具并了解一些悬而未决的问题是十分必要的。本书正是适合于上述目标的一部优秀教科书。
本书作者桑杰夫·阿罗拉(Sanjeev Arora)和博阿兹·巴拉克(Boaz Barak)都是在普林斯顿大学计算机科学系一直从事复杂性理论研究的著名教授。桑杰夫·阿罗拉在概率可验证明NP难问题的可近似性方面取得了基础性的研究成果。博阿兹·巴拉克在计算复杂性理论和密码学方面，特别是“非黑盒”技术方面，也取得了基础性的研究成果。本书已经逐步成为国内外计算复杂性理论课程的标准教材，其翻译和出版对国内读者学习和应用复杂性理论具有重要的意义。有幸承担该书的翻译工作，我们感到十分荣幸。
本书旨在介绍计算复杂性理论的基本概念、经典结果、近年来取得的有用的结果，帮助读者理解和掌握计算复杂性理论中的思维方法、主要工具和研究前沿。基础概念和经典结果可以帮助读者建立计算复杂性理论的知识框架，掌握复杂性理论的思维方法和证明技巧。高级专题是经典结果的有益补充和延伸，而最新的研究成果和悬而未决的问题则可以帮助读者接触计算复杂性理论研究的最前沿。此外，本书还涉及了一些学术界尚存的争论,这些深入分析和深刻见解也是本书的精髓所在。全书特别强调计算复杂性理论的各种概念的直观含义，阐述它们在何种场合下是有用的，以及为什么这些概念要这样定义。全书围绕两条主要线索进行组织：其一是人们所尝试的用于处理P?=NP问题的各种方法以及对这些方法的局限性的阐释；其二是逐步准备证明PCP定理所需的各种素材，最终完成PCP定理的证明。这种组织使得本书内容丰富，结构灵活，可供不同层次的读者使用。
译者翻译时在深刻理解全书内容的基础上力求准确，对于发现的多处笔误和印刷错误进行了更正。在本书的翻译过程中，译者得到了多位同事、朋友和家人的支持和帮助，他们对译稿提出了很多中肯的意见和建议，使译者受益匪浅。在此一并向他们表示感谢！
限于译者水平，译文中疏漏和错误难免，敬请读者批评指正。如有任何建议,请发送邮件至luojizhou@hit.edu.cn。

译者
2015年10月

出版者的话
译者序
译者简介
前言
致谢
引言
第0章　记号约定1
0.1　对象的字符串表示1
0.2　判定问题/语言2
0.3　大O记号2
习题3
第一部分　基本复杂性类
第1章　计算模型——为什么模型选择无关紧要6
1.1　计算的建模：你真正需要了解的内容6
1.2　图灵机7
　1.2.1　图灵机的表达能力10
1.3　效率和运行时间11
　1.3.1　定义的健壮性11
1.4　机器的位串表示和通用图灵机14
　1.4.1　通用图灵机14
1.5　不可计算性简介15
　1.5.1　停机问题16
　1.5.2　哥德尔定理17
1.6　类P18
　1.6.1　为什么模型选择无关紧要19
　1.6.2　P的哲学意义19
　1.6.3　P的争议和解决争议的一些努力20
　1.6.4　埃德蒙兹的引言21
1.7　定理1.9的证明：O(TlogT)时间的通用模拟21
本章学习内容24
本章注记和历史24
习题26
第2章　NP和NP完全性29
2.1　类NP29
　2.1.1　P和NP的关系31
　2.1.2　非确定型图灵机31
2.2　归约和NP完全性32
2.3　库克勒维定理：计算的局部性34
　2.3.1　布尔公式、合取范式和SAT问题34
　2.3.2　库克勒维定理34
　2.3.3　准备工作：布尔公式的表达能力35
　2.3.4　引理2.11的证明35
　2.3.5　将SAT归约到3SAT38
　2.3.6　深入理解库克勒维定理38
2.4　归约网络39
2.5　判定与搜索42
2.6　coNP、EXP和NEXP43
　2.6.1　coNP43
　2.6.2　EXP和NEXP44
2.7　深入理解P、NP及其他复杂性类45
　2.7.1　NP的哲学意义45
　2.7.2　NP与数学证明45
　2.7.3　如果P=NP会怎样45
　2.7.4　如果NP=coNP会怎样46
　2.7.5　NP和NP完全之间存在其他复杂性类吗47
　2.7.6　NP难的处理47
　2.7.7　更精细的时间复杂性48
本章学习内容48
本章注记和历史48
习题49
第3章　对角线方法53
3.1　时间分层定理53
3.2　非确定型时间分层定理54
3.3　拉德纳尔定理:NP非完全问题的存在性55
3.4　神喻机器和对角线方法的局限性57
　3.4.1　逻辑独立与相对59
本章学习内容59
本章注记和历史59
习题60
第4章　空间复杂性61
4.1　空间受限计算的定义61
　4.1.1　格局图62
　4.1.2　一些空间复杂性类63
　4.1.3　空间分层定理64
4.2　PSPACE完全性64
　4.2.1　塞维奇定理67
　4.2.2　PSPACE的本质：最佳博弈策略67
4.3　NL完全性68
　4.3.1　基于证明的NL定义:仅能读一次的证明70
　4.3.2　NL=coNL71
本章学习内容72
本章注记和历史73
习题73
第5章　多项式分层和交错75
5.1　类Σp275
5.2　多项式分层76
　5.2.1　多项式分层的性质76
　5.2.2　PH各层的完全问题77
5.3　交错图灵机78
　5.3.1　无限次交错79
5.4　时间与交错：SAT的时空平衡79
5.5　用神喻图灵机定义多项式分层80
本章学习内容81
本章注记和历史81
习题82
第6章　布尔线路83
6.1　布尔线路和P/poly83
　6.1.1　P/poly和P之间的关系85
　6.1.2　线路的可满足性和库克勒维定理的另一种证明86
6.2　一致线路87
　6.2.1　对数空间一致线路族87
6.3　纳言图灵机88
6.4　P/poly和NP88
6.5　线路下界89
6.6　非一致分层定理90
6.7　线路复杂性类的精细分层91
　6.7.1　类NC和类AC92
　6.7.2　P完全性92
6.8　指数规模的线路93
本章学习内容93
本章注记和历史94
习题94
第7章　随机计算96
7.1　概率型图灵机97
7.2　概率型图灵机示例98
　7.2.1　寻找中位数99
　7.2.2　概率型素性测试100
　7.2.3　多项式恒等测试101
　7.2.4　二分图的完美匹配测试102
7.3　单面错误和“零面”错误：RP、coRP、ZPP103
7.4　定义的健壮性103
　7.4.1　准确度常数的作用：错率归约104
　7.4.2　期望运行时间与最坏运行时间105
　7.4.3　使用比均匀硬币投掷更具一般性的随机选择106
7.5　BPP同其他复杂性类之间的关系106
　7.5.1　BPPP/poly107
　7.5.2　BPPPH107
　7.5.3　分层定理与完全问题108
7.6　随机归约109
7.7　空间受限的随机计算109
本章学习内容110
本章注记和历史110
习题111
第8章　交互式证明113
8.1　交互式证明及其变形113
　8.1.1　准备工作：验证者和证明者均为确定型的交互式证明113
　8.1.2　类IP：概率型验证者115
　8.1.3　图不同构的交互式证明116
8.2　公用随机源和类AM118
　8.2.1　私有随机源的模拟119
　8.2.2　集合下界协议120
　8.2.3　定理8.12的证明概要123
　8.2.4　GI能是NP完全的吗123
8.3　IP=PSPACE124
　8.3.1　算术化125
　8.3.2　#SATD的交互式协议125
　8.3.3　TQBF的协议：定理8.19的证明127
8.4　证明者的能力128
8.5　多证明者交互式证明129
8.6　程序检验130
　8.6.1　具有验证程序的语言131
　8.6.2　随机自归约与积和式131
8.7　积和式的交互式证明132
　8.7.1　协议133
本章学习内容134
本章注记和历史134
习题135
第9章　密码学137
9.1　完全保密及其局限性138
9.2　计算安全、单向函数和伪随机数产生器139
　9.2.1　单向函数：定义和实例141
　9.2.2　用单向函数实现加密142
　9.2.3　伪随机数产生器143
9.3　用单向置换构造伪随机数产生器144
　9.3.1　不可预测性蕴含伪随机性144
　9.3.2　引理9.10的证明：戈德赖希勒维定理145
9.4　零知识149
9.5　应用151
　9.5.1　伪随机函数及其应用151
　9.5.2　去随机化153
　9.5.3　电话投币和比特承诺154
　9.5.4　安全的多方计算154
　9.5.5　机器学习的下界155
本章学习内容155
本章注记和历史155
习题158
第10章　量子计算161
10.1　量子怪相：双缝实验162
10.2　量子叠加和量子位163
　10.2.1　EPR悖论165
10.3　量子计算的定义和BQP168
　10.3.1　线性代数预备知识168
　10.3.2　量子寄存器及其状态向量168
　10.3.3　量子操作169
　10.3.4　量子操作实例169
　10.3.5　量子计算与BQP171
　10.3.6　量子线路172
　10.3.7　传统计算是量子计算的特例173
　10.3.8　通用操作173
10.4　格罗弗搜索算法174
10.5　西蒙算法177
　10.5.1　定理10.14的证明177
10.6　肖尔算法:用量子计算机实现整数分解178
　10.6.1　ZM上的傅里叶变换179
　10.6.2　ZM上的量子傅里叶变换180
　10.6.3　肖尔的阶发现算法181
　10.6.4　因数分解归约为阶发现184
　10.6.5　实数的有理数近似185
10.7　BQP和经典复杂性类186
　10.7.1　量子计算中类似于NP和AM的复杂性类187
本章学习内容187
本章注记和历史188
习题190
第11章　PCP定理和近似难度简介192
11.1　动机：近似求解NP难的优化问题193
11.2　用两种观点理解PCP定理194
　11.2.1　PCP定理与局部可验证明194
　11.2.2　PCP定理与近似难度197
11.3　两种观点的等价性197
　11.3.1　定理11.5与定理11.9的等价性198
　11.3.2　重新审视PCP的两种理解199
11.4　顶点覆盖问题和独立集问题的近似难度200
11.5　NPPCP(poly(n),1):由沃尔什哈达玛编码得到的PCP202
　11.5.1　线性测试与沃尔什哈达玛编码202
　11.5.2　定理11.19的证明203
本章学习内容206
本章注记和历史206
习题207
第二部分　具体计算模型的下界
第12章　判定树210
12.1　判定树和判定树复杂性210
12.2　证明复杂性212
12.3　随机判定树213
12.4　证明判定树下界的一些技术214
　12.4.1　随机复杂性的下界214
　12.4.2　敏感性215
　12.4.3　次数方法216
本章学习内容217
本章注记和历史217
习题218
第13章　通信复杂性219
13.1　双方通信复杂性的定义219
13.2　下界方法220
　13.2.1　诈集方法220
　13.2.2　铺砌方法221
　13.2.3　秩方法222
　13.2.4　差异方法223
　13.2.5　证明差异上界的一种技术223
　13.2.6　各种下界方法的比较224
13.3　多方通信复杂性225
13.4　其他通信复杂性模型概述227
本章学习内容228
本章注记和历史228
习题229
第14章　线路下界：复杂性理论的滑铁卢232
14.1　AC0和哈斯塔德开关引理232
　14.1.1　哈斯塔德开关引理233
　14.1.2　开关引理的证明234
14.2　带“计数器”的线路:ACC236
14.3　单调线路的下界239
　14.3.1　定理14.7的证明239
14.4　线路复杂性的前沿242
　14.4.1　用对角线方法证明线路下界242
　14.4.2　ACC Vs P的研究现状243
　14.4.3　具有对数深度的线性线路244
　14.4.4　线路图244
14.5　通信复杂性方法245
　14.5.1　与ACC0线路之间的联系245
　14.5.2　与线性规模对数深度的线路之间的联系246
　14.5.3　与线路图之间的联系246
　14.5.4　卡奇梅尔维格德尔森通信游戏
与深度下界246
本章学习内容248
本章注记和历史249
习题249
第15章　证明复杂性251
15.1　几个例子251
15.2　命题演算与归结252
　15.2.1　用瓶颈法证明下界253
　15.2.2　插值定理和归结的指数下界254
15.3　其他证明系统概述256
15.4　元数学的思考258
本章学习内容258
本章注记和历史258
习题259
第16章　代数计算模型260
16.1　代数直线程序和代数线路261
　16.1.1　代数直线程序261
　16.1.2　例子262
　16.1.3　代数线路263
　16.1.4　代数线路中类似于P、NP的复杂性类264
16.2　代数计算树266
　16.2.1　下界的拓扑方法268
16.3　布卢姆舒布斯梅尔模型270
　16.3.1　复数上的复杂性类271
　16.3.2　完全问题和希尔伯特零点定理271
　16.3.3　判定性问题——曼德勃罗集272
本章学习内容272
本章注记和历史273
习题274
第三部分　高级专题
第17章　计数复杂性278
17.1　计数问题举例278
　17.1.1　计数问题与概率估计279
　17.1.2　计数可能难于判定279
17.2　复杂性类#P280
　17.2.1　复杂性类PP：类似于#P的判定问题281
17.3　#P完全性281
　17.3.1　积和式和瓦利安特定理282
　17.3.2　#P问题的近似解286
17.4　户田定理：PHP#SAT287
　17.4.1　过渡：具有唯一解的布尔满足性问题288
　17.4.2　⊕的性质和对NP、coNP证明引理17.17289
　17.4.3　引理17.17的证明：一般情形290
　17.4.4　第二步：转换为确定型归约291
17.5　待决问题292
本章学习内容293
本章注记和历史293
习题293
第18章　平均复杂性:勒维定理295
18.1　分布问题与distP296
18.2　“实际分布”的形式化定义298
18.3　distNP及其完全问题298
　18.3.1　distNP的一个完全问题300
　18.3.2　P可抽样的分布301
18.4　哲学意义和实践意义301
本章学习内容303
本章注记和历史303
习题303
第19章　难度放大和纠错码305
19.1　从温和难度到强难度：姚期智XOR引理306
　19.1.1　用因帕利亚佐难度核引理证明姚期智XOR引理307
　19.1.2　因帕利亚佐难度核引理的证明309
19.2　工具：纠错码310
　19.2.1　显式纠错码312
　19.2.2　沃尔什哈达玛纠错码312
　19.2.3　里德所罗门纠错码313
　19.2.4　里德穆勒纠错码313
　19.2.5　拼接纠错码314
19.3　高效解码315
　19.3.1　里德所罗门解码315
　19.3.2　拼接解码316
19.4　局部解码与难度放大316
　19.4.1　沃尔什哈达玛纠错码的局部解码算法318
　19.4.2　里德穆勒纠错码的局部解码算法318
　19.4.3　拼接纠错码的局部解码算法319
　19.4.4　局部解码算法综合运用于难度放大320
19.5　列表解码321
　19.5.1　里德所罗门纠错码的列表解码322
19.6　局部列表解码：接近BPP=P323
　19.6.1　沃尔什哈达玛纠错码的局部列表解码323
　19.6.2　里德穆勒纠错码的局部列表解码323
　19.6.3　拼接纠错码的局部列表解码325
　19.6.4　局部列表解码算法综合运用于难度放大325
本章学习内容326
本章注记和历史327
习题328
第20章　去随机化330
20.1　伪随机数产生器和去随机化331
　20.1.1　用伪随机数产生器实现去随机化331
　20.1.2　难度与去随机化333
20.2　定理20.6的证明：尼散维格德尔森构造334
　20.2.1　两个示意性例子334
　20.2.2　尼散维格德尔森构造336
20.3　一致假设下的去随机化339
20.4　去随机化需要线路下界340
本章学习内容343
本章注记和历史343
习题344
第21章　伪随机构造:扩张图和提取器345
21.1　随机游走和特征值346
　21.1.1　分布向量和参数λ(G)346
　21.1.2　无向连通性问题的随机算法的分析349
21.2　扩张图349
　21.2.1　代数定义350
　21.2.2　组合扩张和扩张图的存在性350
　21.2.3　代数扩张图蕴含组合扩张图351
　21.2.4　组合扩张图蕴含代数扩张图352
　21.2.5　用扩张图设计纠错码353
21.3　扩张图的显式构造355
　21.3.1　旋转映射356
　21.3.2　矩阵乘积和路径乘积356
　21.3.3　张量积356
　21.3.4　替换乘积357
　21.3.5　显式构造359
21.4　无向连通性问题的确定型对数空间算法361
　21.4.1　连通性问题的对数空间算法（定理21.21的证明）361
21.5　弱随机源和提取器362
　21.5.1　最小熵363
　21.5.2　统计距离364
　21.5.3　随机性提取器的定义364
　21.5.4　提取器的存在性证明364
　21.5.5　基于哈希函数构造提取器365
　21.5.6　基于扩张图的随机游走构造提取器366
　21.5.7　由伪随机数产生器构造提取器366
21.6　空间受限计算的伪随机数产生器368
本章学习内容372
本章注记和历史372
习题374
第22章　PCP定理的证明和傅里叶变换技术378
22.1　非二进制字母表上的约束满足问题378
22.2　PCP定理的证明379
　22.2.1　PCP定理的证明思路379
　22.2.2　迪纳尔鸿沟放大：引理22.5的证明380
　22.2.3　扩张图、随机游走和INDSET的近似难度381
　22.2.4　迪纳尔鸿沟放大382
　22.2.5　字母表削减：引理22.6的证明387
22.3　2CSPW的难度：鸿沟和字母表大小之间的平衡389
　22.3.1　莱斯的证明思想：并行重复389
22.4　哈斯塔德3位PCP定理和MAX3SAT的难度390
　22.4.1　MAX3SAT的近似难度390
22.5　工具：傅里叶变换391
　22.5.1　GF(2)n上的傅里叶变换391
　22.5.2　从较高层面看傅里叶变换和PCP之间的联系393
　22.5.3　GF(2)上线性测试的分析393
22.6　坐标函数、长编码及其测试395
22.7　定理22.16的证明396
22.8　SETCOVER的近似难度400
22.9　其他PCP定理概述402
　22.9.1　具有亚常数可靠性参数的PCP定理402
　22.9.2　平摊的查验复杂度402
　22.9.3　2位测试和高效傅里叶分析403
　22.9.4　唯一性游戏和阈值结果404
　22.9.5　与等周问题和度量空间嵌入之间的联系404
22.A　将qCSP实例转换成“精细”实例405
本章学习内容406
本章注记和历史407
习题408
第23章　为什么线路下界如此困难411
23.1　自然证明的定义411
23.2　为什么自然证明是自然的412
　23.2.1　为什么要求可构造性413
　23.2.2　为什么要求广泛性413
　23.2.3　用复杂性测度看自然证明414
23.3　定理23.1的证明415
23.4　一个“不自然的”下界416
23.5　哲学观点417
本章注记和历史417
习题418
附录A　数学基础419
部分习题的提示438
参考文献447
术语索引472
复杂性类索引478