计算复杂性 pdf下载

　　复杂性理论是计算科学理论基础的核心它主要研究计算任务的固有复杂性，即在有限的时间内（和/或其他有限的计算资源内）可以完成何种任务，《计算复杂性》从概念的角度讨论复杂性理论主要目的是使高年级本科生和研究生理解复杂性理论，或提供一本自学使用的教科书，《计算复杂性》还可供专业人士参考，因为其中阐述了复杂性理论的各种子领域，如困难放大、伪随机性以及概率证明系统作者在阐述各个子领域时，从该领域的直观问题着手，然后讨论这些问题的实际定义，为得到问题答案所使用的方法，以及答案中体现的思想
　　OdedGoldreich是魏茨曼科学研究所的计算机教授，也是现任的Meye W. Weisgal教授他还是SIAM Journal on Computing，Journal of Cryptology以及Computation Complexity的编辑，出版了《现代密码学、概率证明与伪随机数》一书，以及两卷本的《密码学基础》。

第1章 引言及预备知识
1.1 引言
1.1.1 复杂性理论概述
1.1.2 复杂性理论的特征
1.1.3 本书内容概要
1.1.4 写作方法与风格
1.1.5 标准符号及习惯性用法
1.2 计算任务及模型
1.2.1 表达方式
1.2.2 计算任务
1.2.3 一致性模型（算法）
1.2.4 非一致性计算模型（电路及建议）
1.2.5 复杂性类
本章注释

第2章 P-NP和NP-完全性
2.1 P-vs-NP问题
2.1.1 搜索版本：求解与检验
2.1.2 判定版本：证明与验证
2.1.3 两种表示的等价性
2.1.4 对NP的两个技术性说明
2.1.5 NP的传统定义
2.1.6 对P不同于NP的支持
2.1.7 哲学思考
2.2 多项式时间归约
2.2.1 归约的一般概念
2.2.2 优化问题到搜索问题的归约
2.2.3 搜索问题的自归约性
2.2.4 总结及一般性观点
2.3 NP-完全性
2.3.1 定义
2.3.2 NP-完全问题的存在性
2.3.3 一些常见的NP-完全问题
2，3.4 既不属于P也非NP-完全的NP集
2.3.5 对完全问题的思考
2.4 三个前沿性问题
2.4.1 承诺问题
2.4.2 NP问题的最优搜索算法
2.4.3 coNP类及其与NP的交集
本章注释
习题

第3章 P与NP的变形
3.1 非一致的多项式时间
3.1.1 布尔电路
3.1.2 接受建议的机器
3.2 多项式时间层级
3.2.1 量词的转换
3.2.2 非确定型预言机
3.2.3 P/poly-vs-NP问题及PH类
本章注释
习题

第4章 资源越多功能就越强大吗？
4.1 非一致的复杂性层级
4.2 时间层级及缝隙
4.2.1 时间层级
4.2.2 时间缝隙及加速
4.3 空间层级和缝隙
本章注释
习题

第5章 空间复杂性
5.1 预备知识及相关问题
5.1.1 几个重要的习惯性表达
5.1.2 有用的最少计算空间
5.1.3 时间与空间
5.1.4 电路求值
……

第6章 随机性与计数
第7章 困难性的用途
第8章 伪随机数发生器
第9章 概率证明系统
第10章 对复杂性要求的弱化

附录A 复杂性类汇总
附录B 寻求下限
附录C 现代密码学基础
附录D 概率论基础及随机性中的前沿问题
附录E 明确的构造
附录F 一些省略的证明
附录G 一些计算问题

参考文献
后记

　　在人类的长期实践经验中，由于资源（如时间）的匮乏，对效率的追求是一个传统而普遍性的做法。因此，什么样的计算任务可以被高效解决一直是人们考虑的核心问题之一。
　　为了系统化地解决上述问题，一个关键步骤是要对计算任务及解决任务的程序给出严格定义。20世纪30年代出现的可计算理论（Computability Theory）提供了这些定义。可计算理论主要关注具体的计算任务，并研究解决这些任务的自动化程序（即计算设备及算法），它为我们研究算法所需的计算资源（如时间）打下了基础。当研究的重点转向解决某个特定任务（或某种特定类型的任务）的任意算法所需的计算资源时，就形成了计算复杂性理论（也称复杂性理论）研究。
　　复杂性理论是计算机科学基础理论的核心领域，它主要研究计算任务的固有复杂性（Intrinsic Complexity）。换句话说，典型的复杂性理论研究主要针对着解决某个（或某类）计算任务而非某个具体算法所需的计算资源。事实上，复杂性理论倾向于从计算资源出发并主要关注计算资源本身，研究对可以解决的计算任务类所需资源进行限制而造成的影响。因此，复杂性理论研究的是在有限时间（和／或其他有限的计算资源）内能完成何种任务。
　　半个世纪以来，复杂性理论形成了两个主要的研究方向。一个方向是通过分析计算过程的演化，为计算问题的复杂性建立具体下界。因此，在某种意义上，这个方向的核心是对计算过程的“低层次（Low-level）”研究，电路复杂性及证明复杂性中的大部分研究属于这个分支。与此相反，第二个方向的研究目标是当无法定义个别计算问题或概念时，在问题及概念间建立联系。这一方向可以看作是对计算的“高层次（High-level）”分析。NP完全性理论、对近似性的研究、概率证明系统、伪随机性以及密码学都属于这个分支。
　　本书重点介绍第二个分支，原因如下：首先，这个研究分支中的许多已知结论显然在概念上非常重要，也就是说，这些已知结论提供了非常吸引人的概念，令该领域之外的人士也能理解。其次，这些概念解释起来并不需要过多的技术细节，因此，“高层次”的研究分支更适于本书讲述。
　　书末说明一下本书的性质。我们认为计算复杂性理论具有极其丰富的概念性内容，针对这些内容应该专门开设相关的讲座或课程。编写一部相应的教科书正是我们写作本书的动机和理念。
　　本书从概念的角度介绍复杂性理论，既可作为教科书，也可供自学使用。事实上，本书是针对想要学习复杂性理论的学生及将要从事复杂性理论教学的教师而写的，然而，我们希望本书对专业人士也能提供帮助，特别是当复杂性理论某个研究分支的专家想要了解其他研究分支时。
　　我们还希望本书能引起读者对复杂性理论的兴趣，并使具备充分背景知识（能轻松理解抽象的讨论、定义及证明）的读者了解该领域。然而，真心期望大多数读者具备算法方面的基础知识，至少应熟知算法的概念。
　　本书讲述的重点是复杂性理论的几个子领域（见以下的内容组织及章节概要）。每一部分都从该领域中的一些直观问题开始，其中体现了相关概念。我们将讨论这些问题的重要性、对问题及概念定义方法的选择、问题的求解方法以及答案中体现的思想。我们认为，上述这些方面构成了每个子领域的核心内容。
　　我们注意到，在某些情况下，复杂性理论的基本概念有助于简化技术细节，事实上，本书中的许多结论其证明过程比标准的证明更简单而易于理解。