计算复杂性

第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 两种...

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