This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.

lgli/计算机复杂性：现代方法.pdf

lgrsnf/计算机复杂性：现代方法.pdf

计算复杂性 : 现代方法 = Computational complexity Ji suan fu za xing : Xian dai fang fa = Computational complexity

Modern methods: computational complexity(Chinese Edition)

(美)桑杰夫. 阿罗拉(Sanjeev Arora), (美)博阿兹. 巴拉克(Boaz Barak)著 ; 骆吉洲译; 阿罗拉; 巴拉克; 骆吉洲

[ MEI ] SANG JIE FU A LUO LA ZHU

Arora, Sanjeev; Barak, Boaz

阿罗拉 (Arora, Sanjeev)

Cambridge University Press (Virtual Publishing)

机械工业出版社 Ji xie gong ye chu ban she

Machinery Industry Press

China Machine Press

Cambridge eText

北京:机械工业出版社

Ji suan ji ke xue cong shu, Di 1 ban, 北京 Beijing, 2016

Cambridge University Press, Cambridge, 2009

Ji suan ji ke xue cong shu, Bei jing, 2016

United Kingdom and Ireland, United Kingdom

Cambridge, New York, England, 2009

China, People's Republic, China

Illustrated, 1, PT, 2009

1, 2015

{"isbns":["0521424267","7111518990","7111518993","9780521424264","9787111518990"],"publisher":"iBooker it-ebooks","series":"it-ebooks-extra"}

Includes bibliographical references and index.

Bookmarks: p1 (p1): 第0章 记号约定
p1-1 (p1): 0.1 对象的字符串表示
p1-2 (p2): O.2 判定问题／语言
p1-3 (p2): 0.3 大O记号
p1-4 (p3): 习题
p2 (p6): 第一部分 基本复杂性类
p2-1 (p6): 第1章 计算模型——为什么模型选择无关紧要
p2-1-1 (p6): 1.1 计算的建模：你真正需要了解的内容
p2-1-2 (p7): 1.2 图灵机
p2-1-2-1 (p10): 1.2.1 图灵机的表达能力
p2-1-3 (p11): 1.3 效率和运行时间
p2-1-3-1 (p11): 1.3.1 定义的健壮性
p2-1-4 (p14): 1.4 机器的位串表示和通用图灵机
p2-1-4-1 (p14): 1.4.1 通用图灵机
p2-1-5 (p15): 1.5 不可计算性简介
p2-1-5-1 (p16): 1.5.1 停机问题
p2-1-5-2 (p17): 1.5.2 哥德尔定理
p2-1-6 (p18): 1.6 类P
p2-1-6-1 (p19): 1.6.1 为什么模型选择无关紧要
p2-1-6-2 (p19): 1.6.2 P的哲学意义
p2-1-6-3 (p20): 1.6.3 P的争议和解决争议的一些努力
p2-1-6-4 (p21): 1.6.4 埃德蒙兹的引言
p2-1-7 (p21): 1.7 定理1.9 的证明：O（TlogT）时间的通用模拟
p2-1-8 (p24): 本章学习内容
p2-1-9 (p24): 本章注记和历史
p2-1-10 (p26): 习题
p2-2 (p29): 第2章 NP和NP完全性
p2-2-1 (p29): 2.1 类NP
p2-2-1-1 (p31): 2.1.1 P和NP的关系
p2-2-1-2 (p31): 2.1.2 非确定型图灵机
p2-2-2 (p32): 2.2 归约和NP完全性
p2-2-3 (p34): 2.3 库克－勒维定理：计算的局部性
p2-2-3-1 (p34): 2.3.1 布尔公式、合取范式和SAT问题
p2-2-3-2 (p34): 2.3.2 库克－勒维定理
p2-2-3-3 (p35): 2.3.3 准备工作：布尔公式的表达能力
p2-2-3-4 (p35): 2.3.4 引理2.1 1的证明
p2-2-3-5 (p38): 2.3.5 将SAT归约到3SAT
p2-2-3-6 (p38): 2.3.6 深入理解库克－勒维定理
p2-2-4 (p39): 2.4 归约网络
p2-2-5 (p42): 2.5 判定与搜索
p2-2-6 (p43): 2.6 coNP、EXP和NEXP
p2-2-6-1 (p43): 2.6.1 coNP
p2-2-6-2 (p44): 2.6.2 EXP和NEXP
p2-2-7 (p45): 2.7 深入理解P、NP及其他复杂性类
p2-2-7-1 (p45): 2.7.1 NP的哲学意义
p2-2-7-2 (p45): 2.7.2 NP与数学证明
p2-2-7-3 (p45): 2.7.3 如果P=NP会怎样
p2-2-7-4 (p46): 2.7.4 如果NP=coNP会怎样
p2-2-7-5 (p47): 2.7.5 NP和NP完全之间存在其他复杂性类吗
p2-2-7-6 (p47): 2.7.6 NP难的处理
p2-2-7-7 (p48): 2.7.7 更精细的时间复杂性
p2-2-8 (p48): 本章学习内容
p2-2-9 (p48): 本章注记和历史
p2-2-10 (p49): 习题
p2-3 (p53): 第3章 对角线方法
p2-3-1 (p53): 3.1 时间分层定理
p2-3-2 (p54): 3.2 非确定型时间分层定理
p2-3-3 (p55): 3.3 拉德纳尔定理：NP非完全问题的存在性
p2-3-4 (p57): 3.4 神喻机器和对角线方法的局限性
p2-3-4-1 (p59): 3.4.1 逻辑独立与相对
p2-3-5 (p59): 本章学习内容
p2-3-6 (p59): 本章注记和历史
p2-3-7 (p60): 习题
p2-4 (p61): 第4章 空间复杂性
p2-4-1 (p61): 4.1 空间受限计算的定义
p2-4-1-1 (p62): 4.1.1 格局图
p2-4-1-2 (p63): 4.1.2 一些空间复杂性类
p2-4-1-3 (p64): 4.1.3 空间分层定理
p2-4-2 (p64): 4.2 PSPACE完全性
p2-4-2-1 (p67): 4.2.1 塞维奇定理
p2-4-2-2 (p67): 4.2.2 PSPACE的本质：最佳博弈策略
p2-4-3 (p68): 4.3 NL完全性
p2-4-3-1 (p70): 4.3.1 基于证明的NL定义：仅能读一次的证明
p2-4-3-2 (p71): 4.3.2 NL=coNL
p2-4-4 (p72): 本章学习内容
p2-4-5 (p73): 本章注记和历史
p2-4-6 (p73): 习题
p2-5 (p75): 第5章 多项式分层和交错
p2-5-1 (p75): 5.1 类∑p2
p2-5-2 (p76): 5.2 多项式分层
p2-5-2-1 (p76): 5.2.1 多项式分层的性质
p2-5-2-2 (p77): 5.2.2 PH各层的完全问题
p2-5-3 (p78): 5.3 交错图灵机
p2-5-3-1 (p79): 5.3.1 无限次交错
p2-5-4 (p79): 5.4 时间与交错：SAT的时空平衡
p2-5-5 (p80): 5.5 用神喻图灵机定义多项式分层
p2-5-6 (p81): 本章学习内容
p2-5-7 (p81): 本章注记和历史
p2-5-8 (p82): 习题
p2-6 (p83): 第6章 布尔线路
p2-6-1 (p83): 6.1 布尔线路和P/poly
p2-6-1-1 (p85): 6.1.1 P/poly和P之间的关系
p2-6-1-2 (p86): 6.1.2 线路的可满足性和库克－勒维定理的另一种证明
p2-6-2 (p87): 6.2 一致线路
p2-6-2-1 (p87): 6.2.1 对数空间一致线路族
p2-6-3 (p88): 6.3 纳言图灵机
p2-6-4 (p88): 6.4 P/poly和NP
p2-6-5 (p89): 6.5 线路下界
p2-6-6 (p90): 6.6 非一致分层定理
p2-6-7 (p91): 6.7 线路复杂性类的精细分层
p2-6-7-1 (p92): 6.7.1 类NC和类AC
p2-6-7-2 (p92): 6.7.2 P完全性
p2-6-8 (p93): 6.8 指数规模的线路
p2-6-9 (p93): 本章学习内容
p2-6-10 (p94): 本章注记和历史
p2-6-11 (p94): 习题
p2-7 (p96): 第7章 随机计算
p2-7-1 (p97): 7.1 概率型图灵机
p2-7-2 (p98): 7.2 概率型图灵机示例
p2-7-2-1 (p99): 7.2.1 寻找中位数
p2-7-2-2 (p100): 7.2.2 概率型素性测试
p2-7-2-3 (p101): 7.2.3 多项式恒等测试
p2-7-2-4 (p102): 7.2.4 二分图的完美匹配测试
p2-7-3 (p103): 7.3 单面错误和“零面”错误：RP、coRP、ZPP
p2-7-4 (p103): 7.4 定义的健壮性
p2-7-4-1 (p104): 7.4.1 准确度常数的作用：错率归约
p2-7-4-2 (p105): 7.4.2 期望运行时间与最坏运行时间
p2-7-4-3 (p106): 7.4.3 使用比均匀硬币投掷更具一般性的随机选择
p2-7-5 (p106): 7.5 BPP同其他复杂性类之间的关系
p2-7-5-1 (p107): 7.5.1 BPP？P/poly
p2-7-5-2 (p107): 7.5.2 BPP？PH
p2-7-5-3 (p108): 7.5.3 分层定理与完全问题
p2-7-6 (p109): 7.6 随机归约
p2-7-7 (p109): 7.7 空间受限的随机计算
p2-7-8 (p110): 本章学习内容
p2-7-9 (p110): 本章注记和历史
p2-7-10 (p111): 习题
p2-8 (p113): 第8章 交互式证明
p2-8-1 (p113): 8.1 交互式证明及其变形
p2-8-1-1 (p113): 8.1.1 准备工作：验证者和证明者均为确定型的交互式证明
p2-8-1-2 (p115): 8.1.2 类IP：概率型验证者
p2-8-1-3 (p116): 8.1.3 图不同构的交互式证明
p2-8-2 (p118): 8.2 公用随机源和类AM
p2-8-2-1 (p119): 8.2.1 私有随机源的模拟
p2-8-2-2 (p120): 8.2.2 集合下界协议
p2-8-2-3 (p123): 8.2.3 定理8.1 2的证明概要
p2-8-2-4 (p123): 8.2.4 GI能是NP－完全的吗
p2-8-3 (p124): 8.3 IP=PSPACE
p2-8-3-1 (p125): 8.3.1 算术化
p2-8-3-2 (p125): 8.3.2 ＃SATD的交互式协议
p2-8-3-3 (p127): 8.3.3 TQBF的协议：定理8.19的证明
p2-8-4 (p128): 8.4 证明者的能力
p2-8-5 (p129): 8.5 多证明者交互式证明
p2-8-6 (p130): 8.6 程序检验
p2-8-6-1 (p131): 8.6.1 具有验证程序的语言
p2-8-6-2 (p131): 8.6.2 随机自归约与积和式
p2-8-7 (p132): 8.7 积和式的交互式证明
p2-8-7-1 (p133): 8.7.1 协议
p2-8-8 (p134): 本章学习内容
p2-8-9 (p134): 本章注记和历史
p2-8-10 (p135): 习题
p2-9 (p137): 第9章 密码学
p2-9-1 (p138): 9.1 完全保密及其局限性
p2-9-2 (p139): 9.2 计算安全、单向函数和伪随机数产生器
p2-9-2-1 (p141): 9.2.1 单向函数：定义和实例
p2-9-2-2 (p142): 9.2.2 用单向函数实现加密
p2-9-2-3 (p143): 9.2.3 伪随机数产生器
p2-9-3 (p144): 9.3 用单向置换构造伪随机数产生器
p2-9-3-1 (p144): 9.3.1 不可预测性蕴含伪随机性
p2-9-3-2 (p145): 9.3.2 引理9.10的证明：戈德赖希－勒维定理
p2-9-4 (p149): 9.4 零知识
p2-9-5 (p151): 9.5 应用
p2-9-5-1 (p151): 9.5.1 伪随机函数及其应用
p2-9-5-2 (p153): 9.5.2 去随机化
p2-9-5-3 (p154): 9.5.3 电话投币和比特承诺
p2-9-5-4 (p154): 9.5.4 安全的多方计算
p2-9-5-5 (p155): 9.5.5 机器学习的下界
p2-9-6 (p155): 本章学习内容
p2-9-7 (p155): 本章注记和历史
p2-9-8 (p158): 习题
p2-10 (p161): 第10章 量子计算
p2-10-1 (p162): 10.1 量子怪相：双缝实验
p2-10-2 (p163): 10.2 量子叠加和量子位
p2-10-2-1 (p165): 10.2.1 EPR悖论
p2-10-3 (p168): 10.3 量子计算的定义和BQP
p2-10-3-1 (p168): 10.3.1 线性代数预备知识
p2-10-3-2 (p168): 10.3.2 量子寄存器及其状态向量
p2-10-3-3 (p169): 10.3.3 量子操作
p2-10-3-4 (p169): 10.3.4 量子操作实例
p2-10-3-5 (p171): 10.3.5 量子计算与BQP
p2-10-3-6 (p172): 10.3.6 量子线路
p2-10-3-7 (p173): 10.3.7 传统计算是量子计算的特例
p2-10-3-8 (p173): 10.3.8 通用操作
p2-10-4 (p174): 10.4 格罗弗搜索算法
p2-10-5 (p177): 10.5 西蒙算法
p2-10-5-1 (p177): 10.5.1 定理10.14的证明
p2-10-6 (p178): 10.6 肖尔算法：用量子计算机实现整数分解
p2-10-6-1 (p179): 10.6.1 ZM上的傅里叶变换
p2-10-6-2 (p180): 10.6.2 ZM上的量子傅里叶变换
p2-10-6-3 (p181): 10.6.3 肖尔的阶发现算法
p2-10-6-4 (p184): 10.6.4 因数分解归约为阶发现
p2-10-6-5 (p185): 10.6.5 实数的有理数近似
p2-10-7 (p186): 10.7 BQP和经典复杂性类
p2-10-7-1 (p187): 10.7.1 量子计算中类似于NP和AM的复杂性类
p2-10-8 (p187): 本章学习内容
p2-10-9 (p188): 本章注记和历史
p2-10-10 (p190): 习题
p2-11 (p192): 第11章 PCP定理和近似难度简介
p2-11-1 (p193): 11.1 动机：近似求解NP难的优化问题
p2-11-1-1 (p194): 11.2 用两种观点理解PCP定理
p2-11-1-2 (p194): 11.2.1 PCP定理与局部可验证明
p2-11-1-3 (p197): 11.2.2 PCP定理与近似难度
p2-11-2 (p197): 11.3 两种观点的等价性
p2-11-2-1 (p198): 11.3.1 定理11.5与定理11.9的等价性
p2-11-2-2 (p199): 11.3.2 重新审视PCP的两种理解
p2-11-3 (p200): 11.4 顶点覆盖问题和独立集问题的近似难度
p2-11-4 (p202): 11.5 NP？PCP（poly（n），1）：由沃尔什－哈达玛编码得到的PCP
p2-11-4-1 (p202): 11.5.1 线性测试与沃尔什－哈达玛编码
p2-11-4-2 (p203): 11.5.2 定理11.19的证明
p2-11-5 (p206): 本章学习内容
p2-11-6 (p206): 本章注记和历史
p2-11-7 (p207): 习题
p3 (p210): 第二部分 具体计算模型的下界
p3-1 (p210): 第12章 判定树
p3-1-1 (p210): 12.1 判定树和判定树复杂性
p3-1-2 (p212): 12.2 证明复杂性
p3-1-3 (p213): 12.3 随机判定树
p3-1-4 (p214): 12.4 证明判定树下界的一些技术
p3-1-4-1 (p214): 12.4.1 随机复杂性的下界
p3-1-4-2 (p215): 12.4.2 敏感性
p3-1-4-3 (p216): 12.4.3 次数方法
p3-1-5 (p217): 本章学习内容
p3-1-6 (p217): 本章注记和历史
p3-1-7 (p218): 习题
p3-2 (p219): 第13章 通信复杂性
p3-2-1 (p219): 13.1 双方通信复杂性的定义
p3-2-2 (p220): 13.2 下界方法
p3-2-2-1 (p220): 13.2.1 诈集方法
p3-2-2-2 (p221): 13.2.2 铺砌方法
p3-2-2-3 (p222): 13.2.3 秩方法
p3-2-2-4 (p223): 13.2.4 差异方法
p3-2-2-5 (p223): 13.2.5 证明差异上界的一种技术
p3-2-2-6 (p224): 13.2.6 各种下界方法的比较
p3-2-3 (p225): 13.3 多方通信复杂性
p3-2-4 (p227): 13.4 其他通信复杂性模型概述
p3-2-5 (p228): 本章学习内容
p3-2-6 (p228): 本章注记和历史
p3-2-7 (p229): 习题
p3-3 (p232): 第14章 线路下界：复杂性理论的滑铁卢
p3-3-1 (p232): 14.1 AC0和哈斯塔德开关引理
p3-3-1-1 (p233): 14.1.1 哈斯塔德开关引理
p3-3-1-2 (p234): 14.1.2 开关引理的证明
p3-3-2 (p236): 14.2 带“计数器”的线路：ACC
p3-3-3 (p239): 14.3 单调线路的下界
p3-3-3-1 (p239): 14.3.1 定理14.7的证明
p3-3-4 (p242): 14.4 线路复杂性的前沿
p3-3-4-1 (p242): 14.4.1 用对角线方法证明线路下界
p3-3-4-2 (p243): 14.4.2 ACC Vs P的研究现状
p3-3-4-3 (p244): 14.4.3 具有对数深度的线性线路
p3-3-4-4 (p244): 14.4.4 线路图
p3-3-5 (p245): 14.5 通信复杂性方法
p3-3-5-1 (p245): 14.5.1 与ACC0线路之间的联系
p3-3-5-2 (p246): 14.5.2 与线性规模对数深度的线路之间的联系
p3-3-5-3 (p246): 14.5.3 与线路图之间的联系
p3-3-5-4 (p246): 14.5.4 卡奇梅尔－维格德尔森通信游戏与深度下界
p3-3-6 (p248): 本章学习内容
p3-3-7 (p249): 本章注记和历史
p3-3-8 (p249): 习题
p3-4 (p251): 第15章 证明复杂性
p3-4-1 (p251): 15.1 几个例子
p3-4-2 (p252): 15.2 命题演算与归结
p3-4-2-1 (p253): 15.2.1 用瓶颈法证明下界
p3-4-2-2 (p254): 15.2.2 插值定理和归结的指数下界
p3-4-3 (p256): 15.3 其他证明系统概述
p3-4-4 (p258): 15.4 元数学的思考
p3-4-5 (p258): 本章学习内容
p3-4-6 (p258): 本章注记和历史
p3-4-7 (p259): 习题
p3-5 (p260): 第16章 代数计算模型
p3-5-1 (p261): 16.1 代数直线程序和代数线路
p3-5-1-1 (p261): 16.1.1 代数直线程序
p3-5-1-2 (p262): 16.1.2 例子
p3-5-1-3 (p263): 16.1.3 代数线路
p3-5-1-4 (p264): 16.1.4 代数线路中类似于P、NP的复杂性类
p3-5-2 (p266): 16.2 代数计算树
p3-5-2-1 (p268): 16.2.1 下界的拓扑方法
p3-5-3 (p270): 16.3 布卢姆－舒布－斯梅尔模型
p3-5-3-1 (p271): 16.3.1 复数上的复杂性类
p3-5-3-2 (p271): 16.3.2 完全问题和希尔伯特零点定理
p3-5-3-3 (p272): 16.3.3 判定性问题——曼德勃罗集
p3-5-4 (p272): 本章学习内容
p3-5-5 (p273): 本章注记和历史
p3-5-6 (p274): 习题
p4 (p278): 第三部分 高级专题
p4-1 (p278): 第17章 计数复杂性
p4-1-1 (p278): 17.1 计数问题举例
p4-1-1-1 (p279): 17.1.1 计数问题与概率估计
p4-1-1-2 (p279): 17.1.2 计数可能难于判定
p4-1-2 (p280): 17.2 复杂性类＃P
p4-1-2-1 (p281): 17.2.1 复杂性类PP：类似于＃P的判定问题
p4-1-3 (p281): 17.3 ＃P完全性
p4-1-3-1 (p282): 17.3.1 积和式和瓦利安特定理
p4-1-3-2 (p286): 17.3.2 ＃P问题的近似解
p4-1-4 (p287): 17.4 户田定理：PH？P＃SAT
p4-1-4-1 (p288): 17.4.1 过渡：具有唯一解的布尔满足性问题
p4-1-4-2 (p289): 17.4.2 ？的性质和对NP、coNP证明引理17.17
p4-1-4-3 (p290): 17.4.3 引理17.1 7的证明：一般情形
p4-1-4-4 (p291): 17.4.4 第二步：转换为确定型归约
p4-1-5 (p292): 17.5 待决问题
p4-1-6 (p293): 本章学习内容
p4-1-7 (p293): 本章注记和历史
p4-1-8 (p293): 习题
p4-2 (p295): 第18章 平均复杂性：勒维定理
p4-2-1 (p296): 18.1 分布问题与distP
p4-2-2 (p298): 18.2 “实际分布”的形式化定义
p4-2-3 (p298): 18.3 distNP及其完全问题
p4-2-3-1 (p300): 18.3.1 distNP的一个完全问题
p4-2-3-2 (p301): 18.3.2 P－可抽样的分布
p4-2-4 (p301): 18.4 哲学意义和实践意义
p4-2-5 (p303): 本章学习内容
p4-2-6 (p303): 本章注记和历史
p4-2-7 (p303): 习题
p4-3 (p305): 第19章 难度放大和纠错码
p4-3-1 (p306): 19.1 从温和难度到强难度：姚期智XOR引理
p4-3-1-1 (p307): 19.1.1 用因帕利亚佐难度核引理证明姚期智XOR引理
p4-3-1-2 (p309): 19.1.2 因帕利亚佐难度核引理的证明
p4-3-2 (p310): 19.2 工具：纠错码
p4-3-2-1 (p312): 19.2.1 显式纠错码
p4-3-2-2 (p312): 19.2.2 沃尔什－哈达玛纠错码
p4-3-2-3 (p313): 19.2.3 里德－所罗门纠错码
p4-3-2-4 (p313): 19.2.4 里德－穆勒纠错码
p4-3-2-5 (p314): 19.2.5 拼接纠错码
p4-3-3 (p315): 19.3 高效解码
p4-3-3-1 (p315): 19.3.1 里德－所罗门解码
p4-3-3-2 (p316): 19.3.2 拼接解码
p4-3-4 (p316): 19.4 局部解码与难度放大
p4-3-4-1 (p318): 19.4.1 沃尔什－哈达玛纠错码的局部解码算法
p4-3-4-2 (p318): 19.4.2 里德－穆勒纠错码的局部解码算法
p4-3-4-3 (p319): 19.4.3 拼接纠错码的局部解码算法
p4-3-4-4 (p320): 19.4.4 局部解码算法综合运用于难度放大
p4-3-5 (p321): 19.5 列表解码
p4-3-5-1 (p322): 19.5.1 里德－所罗门纠错码的列表解码
p4-3-6 (p323): 19.6 局部列表解码：接近BPP=P
p4-3-6-1 (p323): 19.6.1 沃尔什－哈达玛纠错码的局部列表解码
p4-3-6-2 (p323): 19.6.2 里德－穆勒纠错码的局部列表解码
p4-3-6-3 (p325): 19.6.3 拼接纠错码的局部列表解码
p4-3-6-4 (p325): 19.6.4 局部列表解码算法综合运用于难度放大
p4-3-7 (p326): 本章学习内容
p4-3-8 (p327): 本章注记和历史
p4-3-9 (p328): 习题
p4-4 (p330): 第20章 去随机化
p4-4-1 (p331): 20.1 伪随机数产生器和去随机化
p4-4-1-1 (p331): 20.1.1 用伪随机数产生器实现去随机化
p4-4-1-2 (p333): 20.1.2 难度与去随机化
p4-4-2 (p334): 20.2 定理20.6 的证明：尼散－维格德尔森构造
p4-4-2-1 (p334): 20.2.1 两个示意性例子
p4-4-2-2 (p336): 20.2.2 尼散－维格德尔森构造
p4-4-3 (p339): 20.3 一致假设下的去随机化
p4-4-4 (p340): 20.4 去随机化需要线路下界
p4-4-5 (p343): 本章学习内容
p4-4-6 (p343): 本章注记和历史
p4-4-7 (p344): 习题
p4-5 (p345): 第21章 伪随机构造：扩张图和提取器
p4-5-1 (p346): 21.1 随机游走和特征值
p4-5-1-1 (p346): 21.1.1 分布向量和参数λ（G）
p4-5-1-2 (p349): 21.1.2 无向连通性问题的随机算法的分析
p4-5-2 (p349): 21.2 扩张图
p4-5-2-1 (p350): 21.2.1 代数定义
p4-5-2-2 (p350): 21.2.2 组合扩张和扩张图的存在性
p4-5-2-3 (p351): 21.2.3 代数扩张图蕴含组合扩张图
p4-5-2-4 (p352): 21.2.4 组合扩张图蕴含代数扩张图
p4-5-2-5 (p353): 21.2.5 用扩张图设计纠错码
p4-5-3 (p355): 21.3 扩张图的显式构造
p4-5-3-1 (p356): 21.3.1 旋转映射
p4-5-3-2 (p356): 21.3.2 矩阵乘积和路径乘积
p4-5-3-3 (p356): 21.3.3 张量积
p4-5-3-4 (p357): 21.3.4 替换乘积
p4-5-3-5 (p359): 21.3.5 显式构造
p4-5-4 (p361): 21.4 无向连通性问题的确定型对数空间算法
p4-5-4-1 (p361): 21.4.1 连通性问题的对数空间算法（定理21.21的证明）
p4-5-5 (p362): 21.5 弱随机源和提取器
p4-5-5-1 (p363): 21.5.1 最小熵
p4-5-5-2 (p364): 21.5.2 统计距离
p4-5-5-3 (p364): 21.5.3 随机性提取器的定义
p4-5-5-4 (p364): 21.5.4 提取器的存在性证明
p4-5-5-5 (p365): 21.5.5 基于哈希函数构造提取器
p4-5-5-6 (p366): 21.5.6 基于扩张图的随机游走构造提取器
p4-5-5-7 (p366): 21.5.7 由伪随机数产生器构造提取器
p4-5-6 (p368): 21.6 空间受限计算的伪随机数产生器
p4-5-7 (p372): 本章学习内容
p4-5-8 (p372): 本章注记和历史
p4-5-9 (p374): 习题
p4-6 (p378): 第22章 PCP定理的证明和傅里叶变换技术
p4-6-1 (p378): 22.1 非二进制字母表上的约束满足问题
p4-6-2 (p379): 22.2 PCP定理的证明
p4-6-2-1 (p379): 22.2.1 PCP定理的证明思路
p4-6-2-2 (p380): 22.2.2 迪纳尔鸿沟放大：引理22.5 的证明
p4-6-2-3 (p381): 22.2.3 扩张图、随机游走和INDSET的近似难度
p4-6-2-4 (p382): 22.2.4 迪纳尔鸿沟放大
p4-6-2-5 (p387): 22.2.5 字母表削减：引理22.6 的证明
p4-6-3 (p389): 22.3 2CSPw的难度：鸿沟和字母表大小之间的平衡
p4-6-3-1 (p389): 22.3.1 莱斯的证明思想：并行重复
p4-6-4 (p390): 22.4 哈斯塔德3位PCP定理和MAX-3SAT的难度
p4-6-4-1 (p390): 22.4.1 MAX-3SAT的近似难度
p4-6-5 (p391): 22.5 工具：傅里叶变换
p4-6-5-1 (p391): 22.5.1 GF（2）n上的傅里叶变换
p4-6-5-2 (p393): 22.5.2 从较高层面看傅里叶变换和PCP之间的联系
p4-6-5-3 (p393): 22.5.3 GF（2）上线性测试的分析
p4-6-6 (p395): 22.6 坐标函数、长编码及其测试
p4-6-7 (p396): 22.7 定理22.1 6的证明
p4-6-8 (p400): 22.8 SET-COVER的近似难度
p4-6-9 (p402): 22.9 其他PCP定理概述
p4-6-9-1 (p402): 22.9.1 具有亚常数可靠性参数的PCP定理
p4-6-9-2 (p402): 22.9.2 平摊的查验复杂度
p4-6-9-3 (p403): 22.9.3 2位测试和高效傅里叶分析
p4-6-9-4 (p404): 22.9.4 唯一性游戏和阈值结果
p4-6-9-5 (p404): 22.9.5 与等周问题和度量空间嵌入之间的联系
p4-6-10 (p405): 22.A 将qCSP实例转换成“精细”实例
p4-6-11 (p406): 本章学习内容
p4-6-12 (p407): 本章注记和历史
p4-6-13 (p408): 习题
p4-7 (p411): 第23章 为什么线路下界如此困难
p4-7-1 (p411): 23.1 自然证明的定义
p4-7-2 (p412): 23.2 为什么自然证明是自然的
p4-7-2-1 (p413): 23.2.1 为什么要求可构造性
p4-7-2-2 (p413): 23.2.2 为什么要求广泛性
p4-7-2-3 (p414): 23.2.3 用复杂性测度看自然证明
p4-7-3 (p415): 23.3 定理23.1的证明
p4-7-4 (p416): 23.4 一个“不自然的”下界
p4-7-5 (p417): 23.5 哲学观点
p4-7-6 (p417): 本章注记和历史
p4-7-7 (p418): 习题
p5 (p419): 附录A数学基础
p6 (p438): 部分习题的提示
p7 (p447): 参考文献
p8 (p472): 术语索引
p9 (p478): 复杂性类索引

Notational Conventions -- The Computational Model, And Why It Doesn't Matter -- Np And Np Completeness -- Diagonalization -- Space Complexity -- The Polynomial Hierarchy And Alternations -- Boolean Circuits -- Randomized Computation -- Interactive Proofs -- Cryptography -- Quantum Computation -- Pcp Theorem And Hardness Of Approximation : An Introduction -- Decision Trees -- Communication Complexity -- Circuit Lower Bounds : Complexity Theory's Waterloo -- Proof Complexity -- Algebraic Computation Models -- Complexity Of Counting -- Average Case Complexity : Levin's Theory -- Hardness Amplification And Error-correcting Codes -- Derandomization -- Pseudorandom Constructions : Expanders And Extractors -- Proofs Of Pcp Theorems And The Fourier Transform Technique -- Why Are Circuit Lower Bounds So Difficult? Sanjeev Arora, Boaz Barak. Includes Bibliographical References (p. 549-573) And Indexes.

Describes recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation. It can be used as a reference, for self-study, or as a beginning graduate textbook. More than 300 exercises are included.

本书分为三部分.第一部分介绍了复杂性理论, 包括复杂性理论的经典结果和一些现代专题.第二部分讨论了各种具体计算模型上的计算复杂性下界.第三部分主要是1980年以后人们在复杂性理论方面获得的进展, 内容包括计数复杂性, 平均复杂性, 难度放大, 去随机化和伪随机性, PCP定理的证明以及自然证明

2023-10-03