计算复杂性：现代方法

作者: [美] 桑杰夫·阿罗拉著 , 骆吉洲· 译

出版社: 机械工业出版社

出版时间: 2015-11

版次: 1

ISBN: 9787111518990

定价: 129.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 477页

字数: 400千字

丛书: 计算机科学丛书

分类: 计算机与互联网

59人买过

　　《计算复杂性：现代方法》系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分为三部分。*部分（第1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参考书，非常适合作为打算进入该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作为博士生相关讨论班的素材。　　克里斯特斯 H. 帕帕季米特里乌（Christos H. Papadimitriou），是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位，现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。出版者的话译者序译者简介前言致谢引言第0章　记号约定10.1　对象的字符串表示10.2　判定问题/语言20.3　大O记号2习题3第一部分　基本复杂性类第1章　计算模型——为什么模型选择无关紧要61.1　计算的建模：你真正需要了解的内容61.2　图灵机71.2.1　图灵机的表达能力101.3　效率和运行时间111.3.1　定义的健壮性111.4　机器的位串表示和通用图灵机141.4.1　通用图灵机141.5　不可计算性简介151.5.1　停机问题161.5.2　哥德尔定理171.6　类P181.6.1　为什么模型选择无关紧要191.6.2　P的哲学意义191.6.3　P的争议和解决争议的一些努力201.6.4　埃德蒙兹的引言211.7　定理1.9的证明：O(TlogT)时间的通用模拟21本章学习内容24本章注记和历史24习题26第2章　NP和NP完全性292.1　类NP292.1.1　P和NP的关系312.1.2　非确定型图灵机312.2　归约和NP完全性322.3　库克勒维定理：计算的局部性342.3.1　布尔公式、合取范式和SAT问题342.3.2　库克勒维定理342.3.3　准备工作：布尔公式的表达能力352.3.4　引理2.11的证明352.3.5　将SAT归约到3SAT382.3.6　深入理解库克勒维定理382.4　归约网络392.5　判定与搜索422.6　coNP、EXP和NEXP432.6.1　coNP432.6.2　EXP和NEXP442.7　深入理解P、NP及其他复杂性类452.7.1　NP的哲学意义452.7.2　NP与数学证明452.7.3　如果P=NP会怎样452.7.4　如果NP=coNP会怎样462.7.5　NP和NP完全之间存在其他复杂性类吗472.7.6　NP难的处理472.7.7　更精细的时间复杂性48本章学习内容48本章注记和历史48习题49第3章　对角线方法533.1　时间分层定理533.2　非确定型时间分层定理543.3　拉德纳尔定理:NP非完全问题的存在性553.4　神喻机器和对角线方法的局限性573.4.1　逻辑独立与相对59本章学习内容59本章注记和历史59习题60第4章　空间复杂性614.1　空间受限计算的定义614.1.1　格局图624.1.2　一些空间复杂性类634.1.3　空间分层定理644.2　PSPACE完全性644.2.1　塞维奇定理674.2.2　PSPACE的本质：*佳博弈策略674.3　NL完全性684.3.1　基于证明的NL定义:仅能读一次的证明704.3.2　NL=coNL71本章学习内容72本章注记和历史73习题73第5章　多项式分层和交错755.1　类Σp2755.2　多项式分层765.2.1　多项式分层的性质765.2.2　PH各层的完全问题775.3　交错图灵机785.3.1　无限次交错795.4　时间与交错：SAT的时空平衡795.5　用神喻图灵机定义多项式分层80本章学习内容81本章注记和历史81习题82第6章　布尔线路836.1　布尔线路和P/poly836.1.1　P/poly和P之间的关系856.1.2　线路的可满足性和库克勒维定理的另一种证明866.2　一致线路876.2.1　对数空间一致线路族876.3　纳言图灵机886.4　P/poly和NP886.5　线路下界896.6　非一致分层定理906.7　线路复杂性类的精细分层916.7.1　类NC和类AC926.7.2　P完全性926.8　指数规模的线路93本章学习内容93本章注记和历史94习题94第7章　随机计算967.1　概率型图灵机977.2　概率型图灵机示例987.2.1　寻找中位数997.2.2　概率型素性测试1007.2.3　多项式恒等测试1017.2.4　二分图的完美匹配测试1027.3　单面错误和“零面”错误：RP、coRP、ZPP1037.4　定义的健壮性1037.4.1　准确度常数的作用：错率归约1047.4.2　期望运行时间与*坏运行时间1057.4.3　使用比均匀硬币投掷更具一般性的随机选择1067.5　BPP同其他复杂性类之间的关系1067.5.1　BPPP/poly1077.5.2　BPPPH1077.5.3　分层定理与完全问题1087.6　随机归约1097.7　空间受限的随机计算109本章学习内容110本章注记和历史110习题111第8章　交互式证明1138.1　交互式证明及其变形1138.1.1　准备工作：验证者和证明者均为确定型的交互式证明1138.1.2　类IP：概率型验证者1158.1.3　图不同构的交互式证明1168.2　公用随机源和类AM1188.2.1　私有随机源的模拟1198.2.2　集合下界协议1208.2.3　定理8.12的证明概要1238.2.4　GI能是NP完全的吗1238.3　IP=PSPACE1248.3.1　算术化1258.3.2　#SATD的交互式协议1258.3.3　TQBF的协议：定理8.19的证明1278.4　证明者的能力1288.5　多证明者交互式证明1298.6　程序检验1308.6.1　具有验证程序的语言1318.6.2　随机自归约与积和式1318.7　积和式的交互式证明1328.7.1　协议133本章学习内容134本章注记和历史134习题135第9章　密码学1379.1　完全保密及其局限性1389.2　计算安全、单向函数和伪随机数产生器1399.2.1　单向函数：定义和实例1419.2.2　用单向函数实现加密1429.2.3　伪随机数产生器1439.3　用单向置换构造伪随机数产生器1449.3.1　不可预测性蕴含伪随机性1449.3.2　引理9.10的证明：戈德赖希勒维定理1459.4　零知识1499.5　应用1519.5.1　伪随机函数及其应用1519.5.2　去随机化1539.5.3　电话投币和比特承诺1549.5.4　安全的多方计算1549.5.5　机器学习的下界155本章学习内容155本章注记和历史155习题158第10章　量子计算16110.1　量子怪相：双缝实验16210.2　量子叠加和量子位16310.2.1　EPR悖论16510.3　量子计算的定义和BQP16810.3.1　线性代数预备知识16810.3.2　量子寄存器及其状态向量16810.3.3　量子操作16910.3.4　量子操作实例16910.3.5　量子计算与BQP17110.3.6　量子线路17210.3.7　传统计算是量子计算的特例17310.3.8　通用操作17310.4　格罗弗搜索算法17410.5　西蒙算法17710.5.1　定理10.14的证明17710.6　肖尔算法:用量子计算机实现整数分解17810.6.1　ZM上的傅里叶变换17910.6.2　ZM上的量子傅里叶变换18010.6.3　肖尔的阶发现算法18110.6.4　因数分解归约为阶发现18410.6.5　实数的有理数近似18510.7　BQP和经典复杂性类18610.7.1　量子计算中类似于NP和AM的复杂性类187本章学习内容187本章注记和历史188习题190第11章　PCP定理和近似难度简介19211.1　动机：近似求解NP难的优化问题19311.2　用两种观点理解PCP定理19411.2.1　PCP定理与局部可验证明19411.2.2　PCP定理与近似难度19711.3　两种观点的等价性19711.3.1　定理11.5与定理11.9的等价性19811.3.2　重新审视PCP的两种理解19911.4　顶点覆盖问题和独立集问题的近似难度20011.5　NPPCP(poly(n),1):由沃尔什哈达玛编码得到的PCP20211.5.1　线性测试与沃尔什哈达玛编码20211.5.2　定理11.19的证明203本章学习内容206本章注记和历史206习题207第二部分　具体计算模型的下界第12章　判定树21012.1　判定树和判定树复杂性21012.2　证明复杂性21212.3　随机判定树21312.4　证明判定树下界的一些技术21412.4.1　随机复杂性的下界21412.4.2　敏感性21512.4.3　次数方法216本章学习内容217本章注记和历史217习题218第13章　通信复杂性21913.1　双方通信复杂性的定义21913.2　下界方法22013.2.1　诈集方法22013.2.2　铺砌方法22113.2.3　秩方法22213.2.4　差异方法22313.2.5　证明差异上界的一种技术22313.2.6　各种下界方法的比较22413.3　多方通信复杂性22513.4　其他通信复杂性模型概述227本章学习内容228本章注记和历史228习题229第14章　线路下界：复杂性理论的滑铁卢23214.1　AC0和哈斯塔德开关引理23214.1.1　哈斯塔德开关引理23314.1.2　开关引理的证明23414.2　带“计数器”的线路:ACC23614.3　单调线路的下界23914.3.1　定理14.7的证明23914.4　线路复杂性的前沿24214.4.1　用对角线方法证明线路下界24214.4.2　ACC Vs P的研究现状24314.4.3　具有对数深度的线性线路24414.4.4　线路图24414.5　通信复杂性方法24514.5.1　与ACC0线路之间的联系24514.5.2　与线性规模对数深度的线路之间的联系24614.5.3　与线路图之间的联系24614.5.4　卡奇梅尔维格德尔森通信游戏与深度下界246本章学习内容248本章注记和历史249习题249第15章　证明复杂性25115.1　几个例子25115.2　命题演算与归结25215.2.1　用瓶颈法证明下界25315.2.2　插值定理和归结的指数下界25415.3　其他证明系统概述25615.4　元数学的思考258本章学习内容258本章注记和历史258习题259第16章　代数计算模型26016.1　代数直线程序和代数线路26116.1.1　代数直线程序26116.1.2　例子26216.1.3　代数线路26316.1.4　代数线路中类似于P、NP的复杂性类26416.2　代数计算树26616.2.1　下界的拓扑方法26816.3　布卢姆舒布斯梅尔模型27016.3.1　复数上的复杂性类27116.3.2　完全问题和希尔伯特零点定理27116.3.3　判定性问题——曼德勃罗集272本章学习内容272本章注记和历史273习题274第三部分　高级专题第17章　计数复杂性27817.1　计数问题举例27817.1.1　计数问题与概率估计27917.1.2　计数可能难于判定27917.2　复杂性类#P28017.2.1　复杂性类PP：类似于#P的判定问题28117.3　#P完全性28117.3.1　积和式和瓦利安特定理28217.3.2　#P问题的近似解28617.4　户田定理：PHP#SAT28717.4.1　过渡：具有唯一解的布尔满足性问题28817.4.2　?的性质和对NP、coNP证明引理17.1728917.4.3　引理17.17的证明：一般情形29017.4.4　第二步：转换为确定型归约29117.5　待决问题292本章学习内容293本章注记和历史293习题293第18章　平均复杂性:勒维定理29518.1　分布问题与distP29618.2　“实际分布”的形式化定义29818.3　distNP及其完全问题29818.3.1　distNP的一个完全问题30018.3.2　P可抽样的分布30118.4　哲学意义和实践意义301本章学习内容303本章注记和历史303习题303第19章　难度放大和纠错码30519.1　从温和难度到强难度：姚期智XOR引理30619.1.1　用因帕利亚佐难度核引理证明姚期智XOR引理30719.1.2　因帕利亚佐难度核引理的证明30919.2　工具：纠错码31019.2.1　显式纠错码31219.2.2　沃尔什哈达玛纠错码31219.2.3　里德所罗门纠错码31319.2.4　里德穆勒纠错码31319.2.5　拼接纠错码31419.3　高效解码31519.3.1　里德所罗门解码31519.3.2　拼接解码31619.4　局部解码与难度放大31619.4.1　沃尔什哈达玛纠错码的局部解码算法31819.4.2　里德穆勒纠错码的局部解码算法31819.4.3　拼接纠错码的局部解码算法31919.4.4　局部解码算法综合运用于难度放大32019.5　列表解码32119.5.1　里德所罗门纠错码的列表解码32219.6　局部列表解码：接近BPP=P32319.6.1　沃尔什哈达玛纠错码的局部列表解码32319.6.2　里德穆勒纠错码的局部列表解码32319.6.3　拼接纠错码的局部列表解码32519.6.4　局部列表解码算法综合运用于难度放大325本章学习内容326本章注记和历史327习题328第20章　去随机化33020.1　伪随机数产生器和去随机化33120.1.1　用伪随机数产生器实现去随机化33120.1.2　难度与去随机化33320.2　定理20.6的证明：尼散维格德尔森构造33420.2.1　两个示意性例子33420.2.2　尼散维格德尔森构造33620.3　一致假设下的去随机化33920.4　去随机化需要线路下界340本章学习内容343本章注记和历史343习题344第21章　伪随机构造:扩张图和提取器34521.1　随机游走和特征值34621.1.1　分布向量和参数λ(G)34621.1.2　无向连通性问题的随机算法的分析34921.2　扩张图34921.2.1　代数定义35021.2.2　组合扩张和扩张图的存在性35021.2.3　代数扩张图蕴含组合扩张图35121.2.4　组合扩张图蕴含代数扩张图35221.2.5　用扩张图设计纠错码35321.3　扩张图的显式构造35521.3.1　旋转映射35621.3.2　矩阵乘积和路径乘积35621.3.3　张量积35621.3.4　替换乘积35721.3.5　显式构造35921.4　无向连通性问题的确定型对数空间算法36121.4.1　连通性问题的对数空间算法（定理21.21的证明）36121.5　弱随机源和提取器36221.5.1　*小熵36321.5.2　统计距离36421.5.3　随机性提取器的定义36421.5.4　提取器的存在性证明36421.5.5　基于哈希函数构造提取器36521.5.6　基于扩张图的随机游走构造提取器36621.5.7　由伪随机数产生器构造提取器36621.6　空间受限计算的伪随机数产生器368本章学习内容372本章注记和历史372习题374第22章　PCP定理的证明和傅里叶变换技术37822.1　非二进制字母表上的约束满足问题37822.2　PCP定理的证明37922.2.1　PCP定理的证明思路37922.2.2　迪纳尔鸿沟放大：引理22.5的证明38022.2.3　扩张图、随机游走和INDSET的近似难度38122.2.4　迪纳尔鸿沟放大38222.2.5　字母表削减：引理22.6的证明38722.3　2CSPW的难度：鸿沟和字母表大小之间的平衡38922.3.1　莱斯的证明思想：并行重复38922.4　哈斯塔德3位PCP定理和MAX3SAT的难度39022.4.1　MAX3SAT的近似难度39022.5　工具：傅里叶变换39122.5.1　GF(2)n上的傅里叶变换39122.5.2　从较高层面看傅里叶变换和PCP之间的联系39322.5.3　GF(2)上线性测试的分析39322.6　坐标函数、长编码及其测试39522.7　定理22.16的证明39622.8　SETCOVER的近似难度40022.9　其他PCP定理概述40222.9.1　具有亚常数可靠性参数的PCP定理40222.9.2　平摊的查验复杂度40222.9.3　2位测试和高效傅里叶分析40322.9.4　唯一性游戏和阈值结果40422.9.5　与等周问题和度量空间嵌入之间的联系40422.A　将qCSP实例转换成“精细”实例405本章学习内容406本章注记和历史407习题408第23章　为什么线路下界如此困难41123.1　自然证明的定义41123.2　为什么自然证明是自然的41223.2.1　为什么要求可构造性41323.2.2　为什么要求广泛性41323.2.3　用复杂性测度看自然证明41423.3　定理23.1的证明41523.4　一个“不自然的”下界41623.5　哲学观点417本章注记和历史417习题418附录A　数学基础419部分习题的提示438参考文献447术语索引472复杂性类索引478
内容简介:
　　《计算复杂性：现代方法》系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分为三部分。*部分（第1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参考书，非常适合作为打算进入该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作为博士生相关讨论班的素材。
作者简介:
　　克里斯特斯 H. 帕帕季米特里乌（Christos H. Papadimitriou），是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位，现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。
目录:
出版者的话译者序译者简介前言致谢引言第0章　记号约定10.1　对象的字符串表示10.2　判定问题/语言20.3　大O记号2习题3第一部分　基本复杂性类第1章　计算模型——为什么模型选择无关紧要61.1　计算的建模：你真正需要了解的内容61.2　图灵机71.2.1　图灵机的表达能力101.3　效率和运行时间111.3.1　定义的健壮性111.4　机器的位串表示和通用图灵机141.4.1　通用图灵机141.5　不可计算性简介151.5.1　停机问题161.5.2　哥德尔定理171.6　类P181.6.1　为什么模型选择无关紧要191.6.2　P的哲学意义191.6.3　P的争议和解决争议的一些努力201.6.4　埃德蒙兹的引言211.7　定理1.9的证明：O(TlogT)时间的通用模拟21本章学习内容24本章注记和历史24习题26第2章　NP和NP完全性292.1　类NP292.1.1　P和NP的关系312.1.2　非确定型图灵机312.2　归约和NP完全性322.3　库克勒维定理：计算的局部性342.3.1　布尔公式、合取范式和SAT问题342.3.2　库克勒维定理342.3.3　准备工作：布尔公式的表达能力352.3.4　引理2.11的证明352.3.5　将SAT归约到3SAT382.3.6　深入理解库克勒维定理382.4　归约网络392.5　判定与搜索422.6　coNP、EXP和NEXP432.6.1　coNP432.6.2　EXP和NEXP442.7　深入理解P、NP及其他复杂性类452.7.1　NP的哲学意义452.7.2　NP与数学证明452.7.3　如果P=NP会怎样452.7.4　如果NP=coNP会怎样462.7.5　NP和NP完全之间存在其他复杂性类吗472.7.6　NP难的处理472.7.7　更精细的时间复杂性48本章学习内容48本章注记和历史48习题49第3章　对角线方法533.1　时间分层定理533.2　非确定型时间分层定理543.3　拉德纳尔定理:NP非完全问题的存在性553.4　神喻机器和对角线方法的局限性573.4.1　逻辑独立与相对59本章学习内容59本章注记和历史59习题60第4章　空间复杂性614.1　空间受限计算的定义614.1.1　格局图624.1.2　一些空间复杂性类634.1.3　空间分层定理644.2　PSPACE完全性644.2.1　塞维奇定理674.2.2　PSPACE的本质：*佳博弈策略674.3　NL完全性684.3.1　基于证明的NL定义:仅能读一次的证明704.3.2　NL=coNL71本章学习内容72本章注记和历史73习题73第5章　多项式分层和交错755.1　类Σp2755.2　多项式分层765.2.1　多项式分层的性质765.2.2　PH各层的完全问题775.3　交错图灵机785.3.1　无限次交错795.4　时间与交错：SAT的时空平衡795.5　用神喻图灵机定义多项式分层80本章学习内容81本章注记和历史81习题82第6章　布尔线路836.1　布尔线路和P/poly836.1.1　P/poly和P之间的关系856.1.2　线路的可满足性和库克勒维定理的另一种证明866.2　一致线路876.2.1　对数空间一致线路族876.3　纳言图灵机886.4　P/poly和NP886.5　线路下界896.6　非一致分层定理906.7　线路复杂性类的精细分层916.7.1　类NC和类AC926.7.2　P完全性926.8　指数规模的线路93本章学习内容93本章注记和历史94习题94第7章　随机计算967.1　概率型图灵机977.2　概率型图灵机示例987.2.1　寻找中位数997.2.2　概率型素性测试1007.2.3　多项式恒等测试1017.2.4　二分图的完美匹配测试1027.3　单面错误和“零面”错误：RP、coRP、ZPP1037.4　定义的健壮性1037.4.1　准确度常数的作用：错率归约1047.4.2　期望运行时间与*坏运行时间1057.4.3　使用比均匀硬币投掷更具一般性的随机选择1067.5　BPP同其他复杂性类之间的关系1067.5.1　BPPP/poly1077.5.2　BPPPH1077.5.3　分层定理与完全问题1087.6　随机归约1097.7　空间受限的随机计算109本章学习内容110本章注记和历史110习题111第8章　交互式证明1138.1　交互式证明及其变形1138.1.1　准备工作：验证者和证明者均为确定型的交互式证明1138.1.2　类IP：概率型验证者1158.1.3　图不同构的交互式证明1168.2　公用随机源和类AM1188.2.1　私有随机源的模拟1198.2.2　集合下界协议1208.2.3　定理8.12的证明概要1238.2.4　GI能是NP完全的吗1238.3　IP=PSPACE1248.3.1　算术化1258.3.2　#SATD的交互式协议1258.3.3　TQBF的协议：定理8.19的证明1278.4　证明者的能力1288.5　多证明者交互式证明1298.6　程序检验1308.6.1　具有验证程序的语言1318.6.2　随机自归约与积和式1318.7　积和式的交互式证明1328.7.1　协议133本章学习内容134本章注记和历史134习题135第9章　密码学1379.1　完全保密及其局限性1389.2　计算安全、单向函数和伪随机数产生器1399.2.1　单向函数：定义和实例1419.2.2　用单向函数实现加密1429.2.3　伪随机数产生器1439.3　用单向置换构造伪随机数产生器1449.3.1　不可预测性蕴含伪随机性1449.3.2　引理9.10的证明：戈德赖希勒维定理1459.4　零知识1499.5　应用1519.5.1　伪随机函数及其应用1519.5.2　去随机化1539.5.3　电话投币和比特承诺1549.5.4　安全的多方计算1549.5.5　机器学习的下界155本章学习内容155本章注记和历史155习题158第10章　量子计算16110.1　量子怪相：双缝实验16210.2　量子叠加和量子位16310.2.1　EPR悖论16510.3　量子计算的定义和BQP16810.3.1　线性代数预备知识16810.3.2　量子寄存器及其状态向量16810.3.3　量子操作16910.3.4　量子操作实例16910.3.5　量子计算与BQP17110.3.6　量子线路17210.3.7　传统计算是量子计算的特例17310.3.8　通用操作17310.4　格罗弗搜索算法17410.5　西蒙算法17710.5.1　定理10.14的证明17710.6　肖尔算法:用量子计算机实现整数分解17810.6.1　ZM上的傅里叶变换17910.6.2　ZM上的量子傅里叶变换18010.6.3　肖尔的阶发现算法18110.6.4　因数分解归约为阶发现18410.6.5　实数的有理数近似18510.7　BQP和经典复杂性类18610.7.1　量子计算中类似于NP和AM的复杂性类187本章学习内容187本章注记和历史188习题190第11章　PCP定理和近似难度简介19211.1　动机：近似求解NP难的优化问题19311.2　用两种观点理解PCP定理19411.2.1　PCP定理与局部可验证明19411.2.2　PCP定理与近似难度19711.3　两种观点的等价性19711.3.1　定理11.5与定理11.9的等价性19811.3.2　重新审视PCP的两种理解19911.4　顶点覆盖问题和独立集问题的近似难度20011.5　NPPCP(poly(n),1):由沃尔什哈达玛编码得到的PCP20211.5.1　线性测试与沃尔什哈达玛编码20211.5.2　定理11.19的证明203本章学习内容206本章注记和历史206习题207第二部分　具体计算模型的下界第12章　判定树21012.1　判定树和判定树复杂性21012.2　证明复杂性21212.3　随机判定树21312.4　证明判定树下界的一些技术21412.4.1　随机复杂性的下界21412.4.2　敏感性21512.4.3　次数方法216本章学习内容217本章注记和历史217习题218第13章　通信复杂性21913.1　双方通信复杂性的定义21913.2　下界方法22013.2.1　诈集方法22013.2.2　铺砌方法22113.2.3　秩方法22213.2.4　差异方法22313.2.5　证明差异上界的一种技术22313.2.6　各种下界方法的比较22413.3　多方通信复杂性22513.4　其他通信复杂性模型概述227本章学习内容228本章注记和历史228习题229第14章　线路下界：复杂性理论的滑铁卢23214.1　AC0和哈斯塔德开关引理23214.1.1　哈斯塔德开关引理23314.1.2　开关引理的证明23414.2　带“计数器”的线路:ACC23614.3　单调线路的下界23914.3.1　定理14.7的证明23914.4　线路复杂性的前沿24214.4.1　用对角线方法证明线路下界24214.4.2　ACC Vs P的研究现状24314.4.3　具有对数深度的线性线路24414.4.4　线路图24414.5　通信复杂性方法24514.5.1　与ACC0线路之间的联系24514.5.2　与线性规模对数深度的线路之间的联系24614.5.3　与线路图之间的联系24614.5.4　卡奇梅尔维格德尔森通信游戏与深度下界246本章学习内容248本章注记和历史249习题249第15章　证明复杂性25115.1　几个例子25115.2　命题演算与归结25215.2.1　用瓶颈法证明下界25315.2.2　插值定理和归结的指数下界25415.3　其他证明系统概述25615.4　元数学的思考258本章学习内容258本章注记和历史258习题259第16章　代数计算模型26016.1　代数直线程序和代数线路26116.1.1　代数直线程序26116.1.2　例子26216.1.3　代数线路26316.1.4　代数线路中类似于P、NP的复杂性类26416.2　代数计算树26616.2.1　下界的拓扑方法26816.3　布卢姆舒布斯梅尔模型27016.3.1　复数上的复杂性类27116.3.2　完全问题和希尔伯特零点定理27116.3.3　判定性问题——曼德勃罗集272本章学习内容272本章注记和历史273习题274第三部分　高级专题第17章　计数复杂性27817.1　计数问题举例27817.1.1　计数问题与概率估计27917.1.2　计数可能难于判定27917.2　复杂性类#P28017.2.1　复杂性类PP：类似于#P的判定问题28117.3　#P完全性28117.3.1　积和式和瓦利安特定理28217.3.2　#P问题的近似解28617.4　户田定理：PHP#SAT28717.4.1　过渡：具有唯一解的布尔满足性问题28817.4.2　?的性质和对NP、coNP证明引理17.1728917.4.3　引理17.17的证明：一般情形29017.4.4　第二步：转换为确定型归约29117.5　待决问题292本章学习内容293本章注记和历史293习题293第18章　平均复杂性:勒维定理29518.1　分布问题与distP29618.2　“实际分布”的形式化定义29818.3　distNP及其完全问题29818.3.1　distNP的一个完全问题30018.3.2　P可抽样的分布30118.4　哲学意义和实践意义301本章学习内容303本章注记和历史303习题303第19章　难度放大和纠错码30519.1　从温和难度到强难度：姚期智XOR引理30619.1.1　用因帕利亚佐难度核引理证明姚期智XOR引理30719.1.2　因帕利亚佐难度核引理的证明30919.2　工具：纠错码31019.2.1　显式纠错码31219.2.2　沃尔什哈达玛纠错码31219.2.3　里德所罗门纠错码31319.2.4　里德穆勒纠错码31319.2.5　拼接纠错码31419.3　高效解码31519.3.1　里德所罗门解码31519.3.2　拼接解码31619.4　局部解码与难度放大31619.4.1　沃尔什哈达玛纠错码的局部解码算法31819.4.2　里德穆勒纠错码的局部解码算法31819.4.3　拼接纠错码的局部解码算法31919.4.4　局部解码算法综合运用于难度放大32019.5　列表解码32119.5.1　里德所罗门纠错码的列表解码32219.6　局部列表解码：接近BPP=P32319.6.1　沃尔什哈达玛纠错码的局部列表解码32319.6.2　里德穆勒纠错码的局部列表解码32319.6.3　拼接纠错码的局部列表解码32519.6.4　局部列表解码算法综合运用于难度放大325本章学习内容326本章注记和历史327习题328第20章　去随机化33020.1　伪随机数产生器和去随机化33120.1.1　用伪随机数产生器实现去随机化33120.1.2　难度与去随机化33320.2　定理20.6的证明：尼散维格德尔森构造33420.2.1　两个示意性例子33420.2.2　尼散维格德尔森构造33620.3　一致假设下的去随机化33920.4　去随机化需要线路下界340本章学习内容343本章注记和历史343习题344第21章　伪随机构造:扩张图和提取器34521.1　随机游走和特征值34621.1.1　分布向量和参数λ(G)34621.1.2　无向连通性问题的随机算法的分析34921.2　扩张图34921.2.1　代数定义35021.2.2　组合扩张和扩张图的存在性35021.2.3　代数扩张图蕴含组合扩张图35121.2.4　组合扩张图蕴含代数扩张图35221.2.5　用扩张图设计纠错码35321.3　扩张图的显式构造35521.3.1　旋转映射35621.3.2　矩阵乘积和路径乘积35621.3.3　张量积35621.3.4　替换乘积35721.3.5　显式构造35921.4　无向连通性问题的确定型对数空间算法36121.4.1　连通性问题的对数空间算法（定理21.21的证明）36121.5　弱随机源和提取器36221.5.1　*小熵36321.5.2　统计距离36421.5.3　随机性提取器的定义36421.5.4　提取器的存在性证明36421.5.5　基于哈希函数构造提取器36521.5.6　基于扩张图的随机游走构造提取器36621.5.7　由伪随机数产生器构造提取器36621.6　空间受限计算的伪随机数产生器368本章学习内容372本章注记和历史372习题374第22章　PCP定理的证明和傅里叶变换技术37822.1　非二进制字母表上的约束满足问题37822.2　PCP定理的证明37922.2.1　PCP定理的证明思路37922.2.2　迪纳尔鸿沟放大：引理22.5的证明38022.2.3　扩张图、随机游走和INDSET的近似难度38122.2.4　迪纳尔鸿沟放大38222.2.5　字母表削减：引理22.6的证明38722.3　2CSPW的难度：鸿沟和字母表大小之间的平衡38922.3.1　莱斯的证明思想：并行重复38922.4　哈斯塔德3位PCP定理和MAX3SAT的难度39022.4.1　MAX3SAT的近似难度39022.5　工具：傅里叶变换39122.5.1　GF(2)n上的傅里叶变换39122.5.2　从较高层面看傅里叶变换和PCP之间的联系39322.5.3　GF(2)上线性测试的分析39322.6　坐标函数、长编码及其测试39522.7　定理22.16的证明39622.8　SETCOVER的近似难度40022.9　其他PCP定理概述40222.9.1　具有亚常数可靠性参数的PCP定理40222.9.2　平摊的查验复杂度40222.9.3　2位测试和高效傅里叶分析40322.9.4　唯一性游戏和阈值结果40422.9.5　与等周问题和度量空间嵌入之间的联系40422.A　将qCSP实例转换成“精细”实例405本章学习内容406本章注记和历史407习题408第23章　为什么线路下界如此困难41123.1　自然证明的定义41123.2　为什么自然证明是自然的41223.2.1　为什么要求可构造性41323.2.2　为什么要求广泛性41323.2.3　用复杂性测度看自然证明41423.3　定理23.1的证明41523.4　一个“不自然的”下界41623.5　哲学观点417本章注记和历史417习题418附录A　数学基础419部分习题的提示438参考文献447术语索引472复杂性类索引478

查看详情

计算复杂性：现代方法

内容简介:

作者简介:

目录: