计算复杂性

图书标准信息

• 作者 [以色列]Oded、Goldreich 著；张薇、韩益亮、杨晓元 译
• 出版社 国防工业出版社
• 出版时间 2015-11
• 版次 1
• ISBN 9787118103878
• 定价 129.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 486页
• 字数 780千字
• 正文语种 简体中文

【内容简介】

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

【目录】

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

第3章P与NP的变形
3.1非一致的多项式时间
3.1.1布尔电路
3.1.2接受建议的机器
3.2多项式时间层级
3.2.1量词的转换
3.2.2非确定型预言机
3.2.3P/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一些计算问题

参考文献
后记