编辑推荐

　　计算复杂性理论的研究是计算机科学重要的研究领域之一，而Chistos H. Papadimitriou是该领域知名的专家之一。

　　计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域，是理论计算机科学研究的重要内容。复杂性是计算（复杂性类）和应用（问题）之间复杂而核心的部分。

　　本书是一本全面阐述计算复杂性理论及其近年来进展的教科书，内容颇为深奥，重点介绍复杂性的计算、问题和逻辑。本书主要内容包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外（如多项式空间等）复杂性类的介绍。每章最后一节包括相关的参考文献、注解、练习和问题，很多问题涉及更深的结论和研究。

内容简介

　　《计算复杂性：现代方法》系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分为三部分。*部分（第1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参考书，非常适合作为打算进入该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作为博士生相关讨论班的素材。

作者简介

　　克里斯特斯 H. 帕帕季米特里乌（Christos H. Papadimitriou），是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位，现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。

目录

出版者的话

译者序

译者简介

前言

致谢

引言

第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�罰/poly107

7.5.2　BPP�罰H107

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�罰CP(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�罰#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

本章注记 计算复杂性：现代方法 电子书 下载 mobi epub pdf txt

¥106.40

挺好的书, 有点难, 值得拥有.

好

¥106.40

印刷真的很差劲。这种优秀的书，拿来收藏，死磕的书，这种印刷，真的让人崩溃。

给公司买的，京东的商品没得说，给快递小哥点赞

挺好的书, 有点难, 值得拥有.

翻译的作品买来看下，感觉还是挺好的。人油出的书还是挺好

价格比书店便宜，包装简陋