计算复杂性戈德里克　著,张薇,韩益亮,杨晓元　译国防工业

基本信息

书名:计算复杂性

定价：129元

作者:(以)戈德里克　著,张薇,韩益亮,杨晓元　译

出版社：国防工业出版社

出版日期：2015-11-01

ISBN：9787118103878

字数：780000

页码：486

版次：

装帧：平装

开本：16开

商品重量：

内容提要

《计算复杂性》全面介绍了复杂性理论的研究内容，内容涵盖了NP完全性、空间复杂性、伪性生成器等内容，对许多子领域，如难度放大、伪性及概率证明系统等都有介绍，并在附录中介绍了与复杂性相关的现代密码学基础理论。

目录

章 引言及预备知识 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 定义……第3章 P与NP的变形第4章 资源越多功能就越强大？第5章 空间复杂性第6章 性与计数第7章 困难性的用途第8章 伪数发生器第9章 概率证明系统0章 对复杂性要求的弱化附录A 复杂性类汇总附录B 寻求下限附录C 现代密码学基础附录D 概率论基础及性中的前言问题附录E 明确的构造附录F 一些省略的证明附录G 一些计算问题

作者介绍

作者：（以色列）戈德里克（Oded Goldreich） 译者：张薇 韩益亮 杨晓元

编辑推荐

《计算复杂性》由国防工业出版社出版。